Eight poj1077 广度优先搜索

最新推荐文章于 2021-10-09 23:49:15 发布
最新推荐文章于 2021-10-09 23:49:15 发布
阅读量885 收藏
点赞数
分类专栏： 搜索

http://poj.org/problem?id=1077

这个题在poj用朴素的算法就可以了。

在hdu上需要用双向广搜才可以。

首先贴一个单向广搜。

#include <iostream>
#include <bitset>
using namespace std;

int nGoalStatus;//目标状态

/*声明了一个含有9!个位的bitset对象,位的顺序从0到31,缺省情况下所有的位都被初始化为0 */
bitset<362880> Flags; //节点是否标记

char szResult[400000];//结果
char szMoves[400000];//移动步骤 u/d/r/l
int anFather[400000];//父节点指针
int MyQueue[400000];//状态队列，状态总数362880
int nQHead,nQTail;
char sz4Moves[]="udrl";//四种动作

template<class T>
unsigned int GetPermutationNum(T *first,T *permutation,int len){
//permutation编号从0开始算，[first,first+len)里面存放着第0号permutation,排列的每个元素都不一样，返回排列的编号
	unsigned int factorial[21]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,1932053504,1278945280,2004310016,2004189184,4006445056,3396534272,109641728,2192834560};
	bool used[21] = {0};
	int perInt[21]; //要转换成[0,len-1]的整数的排列
	for(int i=0;i<len;++i)
		for( int j=0; j<len;++j){
			if(*(permutation+i) == *(first+j)){
				perInt[i]=j;
				break;
			}
		}
		unsigned int num=0;
		for( int i=0;i<len;++i){
			unsigned int n=0;
			for( int j=0;j<perInt[i];++j){
				if(!used[j]) 
					++n;
			}
			num+=n*factorial[len-i-1];
			used[perInt[i]]=true;
		}
		return num;
}

template <class T>
void GenPermutationByNum(T *first,T *permutation,int len,unsigned int No){ //根据排列编号，生成排列
//[first,first+len) 里面放着第0号 permutation,，排列的每个元素都不一样
	unsigned int factorial[21] ={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,1932053504,1278945280,2004310016,2004189184,4006445056,3396534272,109641728,2192834560};
	bool used[21]={0};
	int perInt[21]; //要转换成 [0,len-1] 的整数的排列
	for(int i=0;i<len;++i){
		unsigned int tmp;
		int n=0;
		int j;
		for(j=0;j<len;++j){
			if(!used[j]){
				if(factorial[len-i-1]>= No+1)
					break;
				else No-=factorial[len-i-1];
			}
		}
		perInt[i]=j;
		used[j]=true;
	}
	for(int i=0;i<len;++i) 
		*(permutation+i)=*(first+perInt[i]);
}

int StrStatusTointStatus(const char *strStatus){
	return GetPermutationNum("012345678",strStatus,9);
}

void IntStatusToStrStatus(int n,char *StrStatus){
	GenPermutationByNum((char *)"012345678",StrStatus,9,n);
}

int NewStatus(int nStatus,char cMove){
//求从nStatus经过cMove移动后得到的新状态。若移动不可行则返回-1
	char szTmp[20];
	int nZeroPos;
	IntStatusToStrStatus(nStatus,szTmp);
	int i;
	for (i=0;i<9;i++){
		if (szTmp[i]=='0'){
			nZeroPos=i;
			break;
		}
	}//返回空格的位置
	switch(cMove){
	case 'u':
		if (nZeroPos-3<0)
			return -1;
		//空格在第一行
		else{
			szTmp[nZeroPos]=szTmp[nZeroPos-3];
			szTmp[nZeroPos-3]='0';
		}
		break;
	case 'd':
		if (nZeroPos+3>8)
			return -1;
		else {
			szTmp[nZeroPos]=szTmp[nZeroPos+3];
			szTmp[nZeroPos+3]='0';
		}
		break;
	case 'l':
		if(nZeroPos%3==0)
			return -1;
		else {
			szTmp[nZeroPos]=szTmp[nZeroPos-1];
			szTmp[nZeroPos-1]='0';
		}
		break;
	case 'r':
		if (nZeroPos%3==2)
			return -1;
		else {
			szTmp[nZeroPos]=szTmp[nZeroPos+1];
			szTmp[nZeroPos+1]='0';
		}
	}
	return StrStatusTointStatus(szTmp);
}

bool Bfs(int nStatus){
	int nNewStatus,i;
	Flags.reset();//将所有位置0
	nQHead=0;
	nQTail=1;
	MyQueue[nQHead]=nStatus;
	while (nQHead!=nQTail){//队列不为空
		nStatus=MyQueue[nQHead];
		if (nStatus==nGoalStatus)
			return true;
		for (i=0;i<4;i++){
			nNewStatus=NewStatus(nStatus,sz4Moves[i]);
			if(nNewStatus==-1)
				continue;
			if (Flags[nNewStatus])
				continue;
			Flags.set(nNewStatus,true);
			MyQueue[nQTail]=nNewStatus;
			anFather[nQTail]=nQHead;//记录父节点
			//记录本节点是由父节点经什么动作而来
			szMoves[nQTail]=sz4Moves[i];
			nQTail++;
		}
		nQHead++;
	}
	return false;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	nGoalStatus=StrStatusTointStatus("123456780");
	char szLine[50];
	char szLine2[20];
	while (cin.getline(szLine,48)){
		int i,j;
		//将输入的原始字符串变为九进制字符串
		for (i=0,j=0;szLine[i];i++)
			if(szLine[i]!=' '){
				if(szLine[i]=='x')
					szLine2[j++]='0';
				else szLine2[j++]=szLine[i];
			}
		szLine2[j]='\0';

		/*接下来的步骤用来判断该串是否有解 偶序列和奇序列不能相互转换。只能目标序列和源序列同为奇序列或者偶序列才可能有解决方案。*/
		int sumGoal=0;
		for (i=0;i<8;i++)
			sumGoal+=i-1;
		int sumOri=0;
		for (i=0;i<9;i++){
			if(szLine2[i]=='0')
				continue;
			for(j=0;j<i;j++)
				if(szLine2[j]<szLine2[i]&&szLine2[j]!='0')
					sumOri++;
		}
		if (sumOri%2!=sumGoal%2){
			cout<<"unsolvable"<<endl;
			continue;
		}

		if(Bfs(StrStatusTointStatus(szLine2))){
			int nMoves=0;
			int nPos=nQHead;
			do{ //通过anFather数组找到成功的状态序列，输出相应步骤
				szResult[nMoves++]=szMoves[nPos];
				nPos=anFather[nPos];
			}while (nPos);
			for(i=nMoves-1;i>=0;i--)
				cout<<szResult[i];
			cout<<endl;
		}
		else 
			cout<<"unsolvable"<<endl;
	}
}

然后再 粘一个双向广搜。

下面的代码可以过hdu1043,上面的代码过不去...

#include <iostream>
#include <bitset>
using namespace std;

int nGoalStatus;//目标状态

/*声明了一个含有9!个位的bitset对象,位的顺序从0到31,缺省情况下所有的位都被初始化为0 */
bitset<362880> Flags[2]; //节点是否标记

char szResult[400000];//结果
char szMoves[2][400000];//移动步骤 u/d/r/l
int anFather[2][400000];//父节点指针
int Queue[2][400000];//状态队列，状态总数362880
int QHead[2],QTail[2];
char sz4Moves[]="udrl";//四种动作

int matchingStatus;//双向碰到的那个状态
int matchingQ;//队列matchingQ的对头元素是双向碰到的那个状态

template<class T>
unsigned int GetPermutationNum(T *first,T *permutation,int len){
	//permutation编号从0开始算，[first,first+len)里面存放着第0号permutation,排列的每个元素都不一样，返回排列的编号
	unsigned int factorial[21]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,1932053504,1278945280,2004310016,2004189184,4006445056,3396534272,109641728,2192834560};
	bool used[21] = {0};
	int perInt[21]; //要转换成[0,len-1]的整数的排列
	for(int i=0;i<len;++i)
		for( int j=0; j<len;++j){
			if(*(permutation+i) == *(first+j)){
				perInt[i]=j;
				break;
			}
		}
		unsigned int num=0;
		for( int i=0;i<len;++i){
			unsigned int n=0;
			for( int j=0;j<perInt[i];++j){
				if(!used[j]) 
					++n;
			}
			num+=n*factorial[len-i-1];
			used[perInt[i]]=true;
		}
		return num;
}

template <class T>
void GenPermutationByNum(T *first,T *permutation,int len,unsigned int No){ //根据排列编号，生成排列
	//[first,first+len) 里面放着第0号 permutation,，排列的每个元素都不一样
	unsigned int factorial[21] ={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,1932053504,1278945280,2004310016,2004189184,4006445056,3396534272,109641728,2192834560};
	bool used[21]={0};
	int perInt[21]; //要转换成 [0,len-1] 的整数的排列
	for(int i=0;i<len;++i){
		unsigned int tmp;
		int n=0;
		int j;
		for(j=0;j<len;++j){
			if(!used[j]){
				if(factorial[len-i-1]>= No+1)
					break;
				else No-=factorial[len-i-1];
			}
		}
		perInt[i]=j;
		used[j]=true;
	}
	for(int i=0;i<len;++i) 
		*(permutation+i)=*(first+perInt[i]);
}

int StrStatusTointStatus(const char *strStatus){
	return GetPermutationNum("012345678",strStatus,9);
}

void IntStatusToStrStatus(int n,char *StrStatus){
	GenPermutationByNum((char *)"012345678",StrStatus,9,n);
}

int NewStatus(int nStatus,char cMove){
	//求从nStatus经过cMove移动后得到的新状态。若移动不可行则返回-1
	char szTmp[20];
	int nZeroPos;
	IntStatusToStrStatus(nStatus,szTmp);
	int i;
	for (i=0;i<9;i++){
		if (szTmp[i]=='0'){
			nZeroPos=i;
			break;
		}
	}//返回空格的位置
	switch(cMove){
	case 'u':
		if (nZeroPos-3<0)
			return -1;
		//空格在第一行
		else{
			szTmp[nZeroPos]=szTmp[nZeroPos-3];
			szTmp[nZeroPos-3]='0';
		}
		break;
	case 'd':
		if (nZeroPos+3>8)
			return -1;
		else {
			szTmp[nZeroPos]=szTmp[nZeroPos+3];
			szTmp[nZeroPos+3]='0';
		}
		break;
	case 'l':
		if(nZeroPos%3==0)
			return -1;
		else {
			szTmp[nZeroPos]=szTmp[nZeroPos-1];
			szTmp[nZeroPos-1]='0';
		}
		break;
	case 'r':
		if (nZeroPos%3==2)
			return -1;
		else {
			szTmp[nZeroPos]=szTmp[nZeroPos+1];
			szTmp[nZeroPos+1]='0';
		}
	}
	return StrStatusTointStatus(szTmp);
}

char ReverseMove(char c){
	switch(c){
	case 'u':
		return 'd';
	case 'l':
		return 'r';
	case 'r':
		return 'l';
	case  'd':
		return 'u';
	}
	return 0;
}

bool DBfs(int nStatus){
	int nNewStatus;
	int i;
	for (i=0;i<2;i++){
		Flags[i].reset();
		QHead[i]=0;
		QTail[i]=1;
	}
	Queue[0][0]=nStatus;
	Queue[1][0]=nGoalStatus;
	Flags[0][nStatus]=1;
	Flags[1][nGoalStatus]=1;
	
	while (QHead[0]!=QTail[0]&&QHead[1]!=QTail[1]){
		int qNo;
		if(QHead[0]==QTail[0])
			qNo=1;
		else if(QHead[1]==QTail[1])
			qNo=0;
		else{
			if (QHead[0]-QTail[0]>QHead[1]-QTail[1])
				qNo=0;
			else qNo=1; 
		}
		int vqNo=1-qNo;
		nStatus=Queue[qNo][QHead[qNo]];
		if (Flags[vqNo][nStatus]==1){//取出的元素曾在另一队列出现过
			matchingStatus=nStatus;
			matchingQ=qNo;
			return true;
		}
		else {
			for (i=0;i<4;i++){
				nNewStatus=NewStatus(nStatus,sz4Moves[i]);
				if (nNewStatus==-1)
					continue;
				if (Flags[qNo][nNewStatus])
					continue;
				Flags[qNo][nNewStatus]=1;
				Queue[qNo][QTail[qNo]]=nNewStatus;
				anFather[qNo][QTail[qNo]]=QHead[qNo];
				szMoves[qNo][QTail[qNo]]=sz4Moves[i];
				QTail[qNo]++;
			}
			QHead[qNo]++;
		}
	}
	return false;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	nGoalStatus=StrStatusTointStatus("123456780");
	char szLine[50];
	char szLine2[20];
	while (cin.getline(szLine,48)){
		int i,j;
		//将输入的原始字符串变为九进制字符串
		for (i=0,j=0;szLine[i];i++)
			if(szLine[i]!=' '){
				if(szLine[i]=='x')
					szLine2[j++]='0';
				else szLine2[j++]=szLine[i];
			}
			szLine2[j]='\0';

			/*接下来的步骤用来判断该串是否有解 偶序列和奇序列不能相互转换。只能目标序列和源序列同为奇序列或者偶序列才可能有解决方案。*/  
			int sumGoal=0;
			for (i=0;i<8;i++)
				sumGoal+=i-1;
			int sumOri=0;
			for (i=0;i<9;i++){
				if(szLine2[i]=='0')
					continue;
				for(j=0;j<i;j++)
					if(szLine2[j]<szLine2[i]&&szLine2[j]!='0')
						sumOri++;
			}
			if (sumOri%2!=sumGoal%2){
				cout<<"unsolvable"<<endl;
				continue;
			}

			if(DBfs(StrStatusTointStatus(szLine2))){
				int nMoves=0;
				int Pos,i;
				if (matchingQ==0)
					Pos=QHead[0];
				else {
					for (i=0;i<QTail[0];i++)
						if (Queue[0][i]==matchingStatus){
							Pos=i;
							break;
						}
				}
				do {
					if (Pos){
						szResult[nMoves++]=szMoves[0][Pos];
						Pos=anFather[0][Pos];
					}
				}while (Pos);
				reverse(szResult,szResult+nMoves);

				if (matchingQ==0){
					for (i=0;i<QTail[1];i++)
						if (Queue[1][i]==matchingStatus){
							Pos=i;
							break;
						}
				}
				else Pos=QHead[1];

				do {
					if (Pos){
						szResult[nMoves++]=ReverseMove(szMoves[1][Pos]);
						Pos=anFather[1][Pos];
					}
				}while(Pos);
				for (i=0;i<nMoves;i++)
					cout<<szResult[i];
				cout<<endl;
			}
			else 
				cout<<"unsolvable"<<endl;
	}
	return 0;
}


搜索专题突破POJ1077 POJ1324 POJ2046 HDU2485 HDU1560 HDU1667 POJ3134 POJ1915 HDU1401 HDU1430 HDU2691
Luowaterbi的博客
08-18 448
POJ1077Eight 八数码问题，就是手机上那个智能拼图的小游戏感觉很小的时候在诺基亚上玩过。只有一个块可以上下左右移动，问能否拼好。 IDA*搜索。估值函数就是目前拼图的曼哈顿距离。这是最理想化的情况，就是只经过曼哈顿距离，所有拼图回到自己位置。因为每次只能改变一个拼图的位置。所以最少就是曼哈顿距离。 估值函数的选取，就是去想最最理想的情况需要多少步达到目标。一般最理想都是实现不了，需...
八数码 poj1077 Eight（A*、IDA*)
冰
03-13 2595
八数码主要参考：刘亚宁学长的八数码八境界 等 A*主要参考：百度百科，初识A*算法，深入A*算法 等 IDA*主要参考：http://blog.csdn.net/urecvbnkuhbh_54245df/article/details/5856756，http://blog.csdn.net/nomad2/article/details/6562140 等 人工智能课的作业，借此研究下八数码
HDU---1043 POJ 1077 Eight 八数码问题 广度优先搜索 康拓展开
sgh666666的博客
07-28 209
问题：很经典的搜索，给定一个3*3的方格，里面放1-8个数字，有一个空格，空位可以与相邻的数字可以移到空格中，问给定一个状态，怎么移动到一个特定的状态（比如1-8顺序存放）。 康拓展开记录当前的状态，BFS即可。 HDU 1043是让给定多组状态，怎么还原成1-8顺序存放，可以倒叙BFS，打标出所有状态， POJ 1077是一组数据，直接正向搜索即可。 思考：A*怎么解决这道题...
尾递归是个什么鬼
weixin_30443895的博客
10-24 837
了解尾递归之前，先了解一下尾调用。 在计算机科学里，尾调用是指一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。这种情形下该调用位置为尾位置。（摘自维基百科） 以上的解释来自维基百科。介绍了什么叫尾调用。例如： function foo(data) { a(data); return b(data); } ...
POJ1077八数码
loveSiri的博客
03-03 1189
POJ1077:八数码问题(Eight) POJ1077查看 文章目录POJ1077:八数码问题(Eight)@[toc]**解题思路**基础知识铺垫广度优先搜索BFS+康托展开广度优先搜索BFS+set二分查找双向广搜DBFS+set二分查找启发式算法+堆+普通标记数组更多策略 解题思路 求步数最少的解时候用广搜 状态的表示问题 若以字符串的形式表示，需要10字节，且检查是否达到目标状...
组合数个数的代码实现
weixin_53475254的博客
10-09 427
组合数公式 代码实现 明确数据类型 首先要先明确运算的数据类型。排列组合数是一组数字总共有多少种排列组合，所以运算的结果一定是整数。 记C(m, n)为从n个数中选取m个数，这些数无序有多少种不同的选法 记A(m, n)为从n个数中选取m个数，且这些数是有序的有多少种不同的选法 求解方法1：先求出分子分母如何做除法 public class Main { public static int arrayNumber(int m, int n){ if (m == 0) return
解密15拼图：从POJ 1077 Eight探讨解题策略
解决这个问题通常涉及深度优先搜索（DFS）或广度优先搜索（BFS）等图搜索算法，结合剪枝技巧以减少不必要的搜索。也可以使用位运算和哈希表来优化空间效率，存储已访问过的状态，防止重复计算。在编程实现时，还需要...
POJ 搜索题
03-21 3027
一些好题目 POJ 1190 – 生日蛋糕(基础，好题) http://acm.pku.edu.cn/JudgeOnline/problem?id=1190 题意：略 解法：dfs，题偏简单，但做出来还是有些感觉的 POJ 1376 – Robot(基础) http://acm.pku.edu.cn/JudgeOnline/problem?id=1376 题意：略 解法：bfs
精选POJ算法题目解析及代码参考
5. **镜子迷宫.cpp**：这个文件很可能是与迷宫生成和求解算法有关的代码，通常涉及深度优先搜索（DFS）和广度优先搜索（BFS）策略。 6. **The Primes.cpp**：此文件包含生成或分析素数的算法。素数是大于1的自然数...
新手必犯错误之溢出
weixin_45972337的博客
03-09 635
关于溢出问题之一二 今天刷题很不幸遇到溢出的问题，相信点进来看文章的你也是，那么我们来重温一下溢出的问题，希望能给你帮助。 直接上图，直面对比int （整型）、long long（长整型）和double（双精度）的取值范围。上图前，大致给出范围以有助记忆： int：-2 * 109 ~ 2 * 109 ; long long: -9 * 1018 ~ 9 * 1018 ; double :-2 *...
scala学习时的一些问题
sssahhhh的博客
01-01 392
关于阶乘 对于Int类型，14的阶乘会溢出，13 的不会 1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 11 39916800 12 479001600 13 1932053504 14 1278945280 StdIn.readInt() 在idea Scala WorkSheet直接运行会出错 java.i...
c语言运行结果错误得分吗,计算中心
weixin_29158047的博客
05-17 825
1输出格式与题目要求不一致系统自动评分采用的方法主要是黑盒测试，在特定的输入下检查输出结果是否正确。计算机显然没有也很难做到人工阅卷那么灵活，因而对输出格式有一定的要求，有可能程序算法是对的但输出格式不符合要求而导致计算机无法识别而失分，因此程序的输出一定要按照题目的要求进行。遇到得分不符合预期时，建议检查程序输出的格式是否与题目要求一致，最好使用题目中提供的编程素材、避免无谓的失分——这也是系...
LeetCode刷题笔记 [70] 爬楼梯
AaronDew的博客
02-24 613
2019-02-23 15:32:02 [70] 爬楼梯 C语言中并没有提供阶乘函数，自己实现很简单，阶乘英文为multiplyNumbers. 原本打算用递归阶乘暴力解决，虽然在本地VScode可以ac，但是在线编译器无法通过，显示 runtime error: signed integer overflow: 2004189184 * 6 cannot be represented i...
C语言:连续阶乘计算
ellenm9的博客
02-23 1627
阶乘计算 算法思路 1、依靠循环来实现累乘计算； 2、res*=n; //阶乘计算 #include<stdio.h> int main() { int i; int n; int res=1; printf("请输入一个整数："); while(scanf("%d",&n)>0){ for(i=1;i<=n;i++){ res*=...
大整数阶乘的运算（可以计算1000！） .
weixin_33882452的博客
10-16 302
由于阶乘运算的增长速度特别快（比2^n的增长速度快），对于较小整数的阶乘运算采用简单的递规算法可以实现，但是对于大整数的乘法（比如1000！），则传统的递规算法就失去了作用。由于本人的水平不高，用下列拙劣的方式实现，请高人多多指教。具体如下：定义一个很长的数组，用数组的每一项表示计算结果的每一位。例如，7！＝5040，a[1000]，则a[0]＝0，a[1]=4,a[2]=0,a[3]=5。程...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值