当前位置: 首页 > 编程日记 > 正文

BFS之三(单向bfs和康托压缩)

//poj 1077 Eight

#include
<iostream> //单向bfs和康托压缩
#include<string>
using namespace std;

bool visited[1000000];
int fac[]={1,1,2,6,24,120,720,5040,40320,362880}; //9!表

int cantor(int arr[])
{
int temp,num=1; //当排列为1 2 3 4 5 6 7 8 9时康托值等于1
for(int i=0;i<9;++i)
{
temp
=0;
for(int j=i+1;j<9;++j)
if(arr[j]<arr[i])
temp
++;
num
+=fac[8-i]*temp;
}
return num;
}
void to_arr(int list[],int num)
{
int i;
for(i=0;i<9;++i)
list[i]
=0;
i
=8;
while(num)
{
list[i
--]=num%10;
num
/=10;
}
}
int to_num(int list[])
{
int n=0;
for(int i=0;i<9;++i)
n
=n*10+list[i];
return n;
}
struct node
{
char ch;
int pre; //通过pre记录路径,这样就不需开个string记录之前所走过的全部路径
int num; //通过num与arr相互转换,这样就不需开个数组记录当前的状态
int sub;
};
node table[
1000000];
//程序的空间开销是3348K,但单向bfs的运行时间会较多


int move[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char pos[4]={'d','r','u','l'};

int main()
{
int arr[9];
char ch;
for(int i=0;i<9;++i)
{
cin
>>ch;
if(ch=='x')
arr[i]
=9,table[0].sub=i;
else
arr[i]
=int(ch-48);
}
table[
0].pre=-1;table[0].num=to_num(arr);
visited[cantor(arr)]
=1;
int head=0,rear=0;

while(head<=rear)
{
to_arr(arr,table[head].num);
if(cantor(arr)==1) //当排列为1 2 3 4 5 6 7 8 9时康托值等于1
{
string str;
int i=head;
while(i!=0)
{
str.insert(str.begin(),table[i].ch);
i
=table[i].pre;
}
cout
<<str<<endl;

return 0;
}
int x,y,tx,ty;
x
=table[head].sub/3;y=table[head].sub%3;

for(int i=0;i<4;++i)
{
tx
=x+move[i][0];ty=y+move[i][1];
if(tx>=0&&tx<3&&ty>=0&&ty<3)
{
swap(arr[x
*3+y],arr[tx*3+ty]);
if(visited[cantor(arr)]==0)
{
++rear;
table[rear].num
=to_num(arr);
table[rear].ch
=pos[i];
table[rear].pre
=head;
table[rear].sub
=tx*3+ty;
visited[cantor(arr)]
=1;
}
swap(arr[x
*3+y],arr[tx*3+ty]);
}
}
head
++;
}
cout
<<"unsolvable\n";
return 0;
}

转载于:https://www.cnblogs.com/mjc467621163/archive/2011/08/22/2149138.html

相关文章:

[JavaWeb基础] 007.Struts2的配置和简单使用

1.框架简介 采用Struts能开发出基于MVC(Model-View-Controller)设计模式的应用构架&#xff0c;用于快速开发Java Web应用。Struts实现的重点在C(Controller)&#xff0c;包括ActionServlet/RequestProcessor和我们定制的Action,也为V(View)提供了一系列定制标签&#xff08;C…

使用Rust + Electron开发跨平台桌面应用 ( 一 )

前言 近段时间学习了Rust&#xff0c;一直想着做点什么东西深入学习&#xff0c;因为是刚学习&#xff0c;很多地方都不熟悉&#xff0c;所以也就不能拿它来做编译器这些&#xff0c;至于web开发&#xff0c;实际上我并不建议拿这个来学习一门语言&#xff0c;大概有几个方面&a…

7软件质量与测试规范

软件质量与测试规范 前言标准/规范产品质量模型总结前言 标准和规范可以指导测试工作的方向。 标准/规范 软件质量与测试标准分为国际标准、国家标准、行业标准、企业(机构)规范、项目规范等。下一层标准需要在上一层标准的框架下做扩展或补充。比如行业标准首先要满足国家…

UVa 679 - Dropping Balls

称号&#xff1a;有一个完整的二叉树&#xff0c;每个节点是一个开关&#xff0c;最初的全封闭&#xff0c;球从顶点丢弃。 每次通过开关球将将其状态反转。现在先问k球落到d当层交换机经过号。分析&#xff1a;进制编码。经过模拟几次能够看出&#xff0c;球会让开关形成连续二…

【原创】StreamInsight查询系列(六)——基本查询操作之分组聚合

上篇博文介绍了StreamInsight基础查询操作中的用户自定义聚合部分。这篇文章将主要介绍如何在StreamInsight查询中使用分组聚合。 测试数据准备 为了方便测试查询&#xff0c;我们首先准备一个静态的测试数据源&#xff1a;var weatherData new[] {new { Timestamp new DateT…

生态环境部:提升5.5亿居民饮用水环境安全保障水平

资料图&#xff1a;备用水源。于从文 摄 中新网1月30日电 据生态环境部网站消息&#xff0c;生态环境部牵头扎实推进饮用水水源地环境保护专项行动&#xff0c;成效显著。截至2018年12月31日&#xff0c;除9个问题因冬季施工难度大或实际工程量大等因素仍在整治外&#xff0c;…

8单元测试的必要性

单元测试的必要性 前言单元测试堪比汽车零件检测总结前言 积土成山,风雨兴焉。 单元测试堪比汽车零件检测 据估计,一般轿车约由1万个不可拆解的独立零部件组装而成。结构极其复杂的特制汽车,,如F1赛车等,其独立零部件的数量可达到2万个之多。可以设想下,如果汽车组装企业…

朴素高精度乘法的常数优化

2015年辽宁省赛热身赛有一道高精度乘法 传送门&#xff1a;NEUOJ 1574 A*B 1574: A * B 时间限制: 10 Sec 内存限制: 128 MB题目描述 Calculate $a \times b$. 输入 Your program will be tested on one or more test cases. In each test case, two integer $a$, $b$ ($0\le …

计算机专业今后的发展方向

计算机专业毕业后&#xff0c;大致的工作方向是软、硬、网、图 四大类&#xff0c;尤其以软件、网络为现今的首选 。从岗位上分&#xff0c;又可以分为技术道路、营销道路两大方向。 if 你选择硬件技术&#xff0c;then 从现在开始&#xff0c;牢记&#xff1a;天道酬勤&#x…

新警达尼亚尔·迪力木拉提的春运一天

新春佳节临近&#xff0c;乌鲁木齐铁路公安处民警坚守一线&#xff0c;保障旅客安全乘车。达尼亚尔迪力木拉提&#xff0c;今年26岁&#xff0c;新疆伊犁州伊宁市人&#xff0c;毕业于大连理工大学。2017年通过国家公务员考试入警为乌鲁木齐铁路公安局乌鲁木齐公安处见习民警&a…

9 单元测试中不得不知的概念

单元测试中不得不知的概念 前言软件单元及单元测试驱动函数和桩函数总结前言 做单元测试,如果不弄清楚什么是单元,那十八般武器也无的放矢了。可能在单元测试中听到最多的就是驱动函数、桩函数和逻辑覆盖,本专题就讲讲关于单元测试中那些不得不知的概念。关于逻辑覆盖,涉及…

php JSON数据格式化输出方法

php 的json_encode能把数组转换为json格式的字符串。字符串没有缩进&#xff0c;中文会转为unicode编码&#xff0c;例如\u975a\u4ed4。人阅读比较困难。现在这个方法在json_encode的基础上再进行一次美化处理。使人能方便阅读内容。 1. 使用 json_encode 输出 1 <?php2 3 …

转:C#中的abstract与virtual

C#中的abstract与virtual2008-03-14 14:01【abstract】 abstract 修饰符可以和类、方法、属性、索引器及事件一起使用。在类声明中使用 abstract 修饰符以指示类只能是其他类的基类。 抽象类具有以下特性&#xff1a; 抽象类不能实例化。 抽象类可以包含抽象方法和抽象访问器。…

从零开始单排学设计模式「UML类图」定级赛

阅读本文大概需要 3.5 分钟。本篇是设计模式系列的开篇&#xff0c;虽然之前也写过相应的文章&#xff0c;但是因为种种原因后来断掉了&#xff0c;而且发现之前写的内容也很渣&#xff0c;不够系统。所以现在打算重写&#xff0c;加上距离现在也有一段时间了&#xff0c;也算是…

10 单元测试使命

单元测试的使命前言单元测试要完成的内容总结前言 不同级别的测试的侧重点是不同的&#xff0c;单元测试也有它的使命所在。 单元测试要完成的内容 单元测试的重点主要包括验证功能的正确性、检查局部数据结构正确性、检查临界数据处理正确性、检查模块接口正确性和验证单元容…

MVVM test

示例代码 public class RegisterUserViewModel{public UserInfo userInfo { get; set; }public ICommand ClickCommand { get; set; }public RegisterUserViewModel(){userInfo new UserInfo();userInfo.Age 25;this.ClickCommand new DelegateCommand<object>(OnClic…

[SCOI2009]生日礼物

这道题很容易看出是一道单调队列题。 首先我们根据珠子的位置排序。 然后按顺序枚举一个个珠子。 如果该种珠子没有出现过标记上它的位置&#xff0c;如果出现过修改并打上当前位置。当所有珠子都出现后&#xff0c;将当前位置减去打标记位置最小的一个即为当前解。 可以证明正…

.Net(c#) 通过 Fortran 动态链接库,实现混合编程

c# 与 Fortran 混合编程解决方案主要有两种&#xff1a;1. 进程级的交互&#xff1a;在 Fortran 中编译为控制台程序&#xff0c;.Net 调用&#xff08;System.Diagnostics.Process&#xff09;&#xff0c;然后使用 Process 的 StandardOutput 属性读取控制台输出内容&#xf…

11关于集成测试

集成测试的必要性 前言集成测试集成测试模式和方法总结前言 差之毫厘,失之千里。 集成测试 单元测试的目的是确认软件单元能够满足所规定的要求,将一些单元按一定的要求合成在一起就组成了集合体。集成测试的目的是确认集合体能够正确地满足所规定的要求,集成后的各软件单…

Maven 手动添加第三方依赖包及编译打包和java命令行编译JAVA文件并使用jar命令打包...

一&#xff0c;实例:新建了一个Maven项目,在eclipse中通过 build path –> configure path….将依赖包添加到工程中后&#xff0c;eclipse不报错了。但是用Maven命令 mvn clean compile 时出错如下&#xff1a; 原因是在eclipse中添加了 exteneral jar后&#xff0c;还需要在…

Codeforces Educational round 58

Ediv2 58 随手AK.jpgD 裸的虚树&#xff0c;在这里就不写了 E 傻逼贪心&#xff1f;这个题过的比$B$都多.jpg #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <cstdlib> #include <queue> #includ…

VC 单文档程序 隐藏程序及任务栏图标

1 在APP类InitInstance()里 注释掉&#xff1a; m_pMainWnd->ShowWindow(SW_SHOW); 2 CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)里加 AfxGetApp()->m_nCmdShow SW_HIDE; 3 隐藏任务栏图标&#xff1a; ModifyStyleEx(WS_EX_APPWINDOW,WS_EX_TOOLWINDOW…

12 集成测试方法之大棒集成方法

大棒集成方法大棒集成方法总结大棒集成方法 大棒集成方法先是对每一个子模块进行测试&#xff08;单元测试阶段&#xff09;&#xff0c;然后将所有模块一次性的全部集成起来进行集成测试。如图&#xff0c;先分别对A、B、C、D、E、F、G模块进行单元测试&#xff0c;然后按照设…

phonegap+emberjs+python手机店发展,html5实现本地车类别~

商城开发项目&#xff0c;现在需要做出APP&#xff0c;无奈出场前android但不是很精通。最后选择phonegap实现app。 由于之前办理购物车分为登陆和登陆后两种情况&#xff0c;登录前必须充分利用本地存储。而基于phonegap本地存储的发展是使用Html5的localstorage功能实现。特分…

世上最伟大的十个公式,1+1=2排名第七,质能方程排名第五

英国科学期刊《物理世界》曾让读者投票评选了“最伟大的公式”&#xff0c;最终榜上有名的十个公式既有无人不知的112&#xff0c;又有著名的Emc2&#xff1b;既有简单的-圆周公式&#xff0c;又有复杂的欧拉公式…… 从什么时候起我们开始厌恶数学&#xff1f;这些东西原本如此…

20位程序员关于求职的疑问,以及我给出的参考答案

作者&#xff1a;陆小凤首发&#xff1a;公众号【程序员江湖】阅读本文大概需要 6 分钟。前几天发了一条朋友圈对于求职小伙伴们提出的问题&#xff0c;我进行了收集整理&#xff0c;统一反馈。也许这20个问题也是你们遇到的问题&#xff0c;所以趁着年前赶紧把它发出来。以下2…

14 集成测试方法之自底向上集成方法

自底向上集成方法前言自底向上集成方法前言 集成测试方法没有好坏之分&#xff0c;只有哪个更适合。 自底向上集成方法 自底向上集成方法是从调用的底层开始逐级的向上集成&#xff0c;每测试完一个族群就将其挂到上一层的模块上。这种集成方法的特点是不需要写桩函数&#x…

JavaScript Document

document:文档对象 document.getElementById();//根据ID获取元素对象 document.getElementsByTagName();//根据标签名获取元素对象数组 document.getElementsByClassName();//根据类名获取元素对象数组 document.getElementsByName();//根据名字获取元素对象数组 document.crea…

effective C++ 读书笔记(11-28)

1: RAII 资源获得时机便是初始化时机 典型应用&#xff1a; 智能指针&#xff01; 2&#xff1a; 为什么 auto_ptr 指针复制之后 原指针就会变成NULL &#xff1a; 多分指针指向它 会被析构多次 delete 函数会多次调用 3&#xff1a; 我要再次留心 stl容器的数据结构 与 特性…

15 三明治集成方法和混合策略集成方法

三明治集成方法和混合策略集成方法 前言三明治集成方法混合策略集成方法总结前言 关于集成测试方法今天我们再学习两个方法,三明治集成方法和混合策略集成方法。 三明治集成方法 采用三明治方法的优点是:它将自顶向下和自底向上的集成方法有机地结合起来,不需要写桩函数,…