这是一个典型的BFS基础题目。关于这道题目,我想记录的并不是如何写BFS,而是如何判断题目需要使用BFS求解。同时,类比另外的两种搜索方式进行的思考。
总而言之,今天分析的主题是:BFS与DFS与迭代加深三种搜索方式的异同点。(下文中,对于其他的搜索方式一概不论。)
先说这道题目吧。最开始审题的时候,有几点引起了我的关注:
1、“已知九宫的初态和终态”: 说明这是搜索问题
2、“最少经过多少步”: 这可以排除DFS,只有BFS与迭代加深可以办到
3、“如果无论多少步都无法到达,则输出-1”:这是我的疑惑点????????
之所以有第三个的疑惑,是因为我曾经认为全局的9!种可能都是可以推到出来的。但是我错了(lll¬ω¬)
经过我的考虑,我一开始写了一个迭代加深搜索,但是我没有办法解决-1的输出问题。代码如下:
1 #include<cstring> 2 #include<cstdio> 3 using namespace std; 4 int maxd; 5 bool okdir[9][4];//[位置][方向]=是否可行 6 int todir[4]={1,-1,3,-3}; 7 char b[10];//初始状态 8 const int dx[]={0,0,1,-1}; 9 const int dy[]={1,-1,0,0}; 10 bool solved=false; 11 int vis[9]; 12 /* 13 这里借鉴了紫书里的相似题目 14 使用了ID映射法来降维和操作 15 */ 16 int initial()//初始化okdir 17 { 18 for(int i=0;i<9;i++) 19 { 20 int x=i/3,y=i%3; 21 for(int k=0;k<4;k++) 22 { 23 int px=x+dx[k],py=y+dy[k]; 24 if(px>=0&&py>=0&&px<3&&py<3)okdir[i][k]=true; 25 else okdir[i][k]=false; 26 } 27 } 28 return 0; 29 } 30 31 char aim[10];//目标状态 32 int diff(char* A) 33 { 34 int num=-1;//如果存在n处不同,那么最好可以走n-1步就能完成 35 for(int i=0;i<9;i++) 36 { 37 if(A[i]!=aim[i])num++; 38 } 39 //printf("%s ",A); 40 return num; 41 } 42 43 bool bfs(char* A,int point,int nowstep)//point是空格所在的以一维位置坐标 44 { 45 int p=diff(A); 46 if(p==-1){solved=true;return true;} 47 if(p+nowstep>maxd)return false; 48 // 49 for(int i=0;i<4;i++) 50 { 51 if(!okdir[point][i])continue; 52 int aimpoint=point+todir[i]; 53 A[point]=A[aimpoint]; 54 A[aimpoint]='.'; 55 //printf("psdd->%s ",A); 56 if(dfs(A,aimpoint,nowstep+1))return true; 57 A[aimpoint]=A[point]; 58 A[point]='.'; 59 }//对每一个方向进行调试 60 /*这里产生了巨大的重复,因为没有记录遍历过的状态 61 这一点在最开始没有考虑到实在是不熟练导致的!! 62 */ 63 return false; 64 } 65 66 int main() 67 { 68 initial(); 69 scanf("%s",b); 70 b[9]='