1.历届试题 九宫重排
九宫格数字的移动，其实是由空格移动造成的，所以，站在空格的角度上，将空格当作运动的点，有四种运动方向：前后左右。以前迷宫问题， 就是起点走到终点，深度搜索（队列），最先到达终点时的步数，就是最短路径；九宫重排问题一样，用字符串表示九宫格的状态，遍历的过程中，当 到达的状态和目标状态一致时结束，但是怎么避免老是走重复的路呢（排重）？那就需要将过程中的状态全部记录下来，每走到新的状态，比较一下先前是否出现过，若出现过，就停止走这条路，即不让这一状态入队列即可。将先前的状态放入set容器可以很快速知道是否出现过。
第一次 TLE 运行超时了，60分;
第二次 TLE 运行超时了，80分， 将操作（1）、（2）交换位置，要986ms，说明没有在根源上减少时间。
第三次，100昏，将结构体增加‘.‘（空格）的坐标，省去每次找坐标的时间。
1 #include<stdio.h> 2 #include<set> 3 #include<queue> 4 #include<string.h> 5 #include<string> 6 using namespace std; 7 struct node 8 { 9 int step,pos_x,pos_y; 10 char str[15]; 11 }; 12 char str1[15],str2[15];//初始状态、目标状态 13 int D[4][2]= {-1,0,1,0,0,-1,0,1}; 14 set<string> Set;//定义一个string类型的set容器,存放九宫格的状态 15 queue<node> que;//定义一个队列，存放行走过程中的状态,每一个node包含达到此状态的步数step、和当时的状态 16 int blank_pos(char *str) //空格的位置 17 { 18 int l=strlen(str); 19 for(int i=0; i<l; i++) 20 { 21 if(str[i]==‘.‘) 22 return i; 23 } 24 } 25 int bfs() 26 { 27 char next_str[15]; 28 node n,new_node; 29 int pos,pos_x,pos_y,next_x,next_y,next_pos; 30 while(!que.empty()) 31 { 32 n=que.front();//队首出队 33 que.pop(); 34 for(int i=0; i<4; i++) //空格往四个方向行走 35 { 36 strcpy(next_str,n.str);//将来next_str要在n.str的基础上改动，但是n.str一直不能动，因为是四个方向共用的 37 next_x=n.pos_x+D[i][0]; 38 next_y=n.pos_y+D[i][1]; 39 if(next_x>=0&&next_x<=2&&next_y>=0&&next_y<=2) //将要走的那一步符合要求 40 { 41 //将接下来的状态表示出来（空格上的’0‘ 变为 (next_x，next_y)上的字符，(next_x，next_y)变成空格；查看set里是否有这个状态，若有就不走这一步，避免重复） 42 pos=n.pos_x*3+n.pos_y; 43 next_pos=next_x*3+next_y;//新空格位置 44 next_str[next_pos]=‘.‘; 45 next_str[pos]=n.str[next_pos]; 46 //判重 47 if(Set.find(next_str)==Set.end()) //表示没有找到重的 48 { 49 new_node.step=n.step+1; 50 //（1）查看着个状态是不是目标状态 51 if(!strcmp(next_str,str2)) //即得到了目标状态 52 { 53 return new_node.step; 54 } 55 //（2）将新的状态记录在队列和Set里 56 strcpy(new_node.str,next_str); 57 new_node.pos_x=next_x; 58 new_node.pos_y=next_y; 59 que.push(new_node); 60 Set.insert(next_str); 61 } 62 } 63 } 64 } 65 return -1; 66 } 67 int main() 68 { 69 //输入 70 node n; 71 int min,pos; 72 scanf("%s",str1); 73 scanf("%s",str2);//目标 74 if(!strcmp(str1,str2)) //即得到了目标状态 75 { 76 printf("%d",0); 77 } 78 else 79 { 80 //初始状态放入队列和set容器 81 pos=blank_pos(str1);//找‘.‘的位置 82 n.pos_x=pos/3; 83 n.pos_y=pos%3; 84 n.step=0; 85 strcpy(n.str,str1); 86 que.push(n); 87 Set.insert(n.str); 88 min=bfs();//广搜，找出最少步骤 89 printf("%d",min); 90 } 91 return 0; 92 }
2.历届试题 青蛙跳杯子
青蛙跳杯子，感觉和九宫重排很相似，虽然是青蛙在跳，但是可以看成空杯子在跳，有6种跳法：往左一个、往右一个，往左两个、往右两个，往左三个、往右三个。诶等一下！！会不会不只一个空杯子？、这样就不行了，不管了，就先当所有案例的都只有一个空杯子，两个的话，就2*6种跳法？后来提交代码后，发现只用考虑一个空杯子。
<c++代码>
1 include<stdio.h> 2 #include<set> 3 #include<string> 4 #include<string.h> 5 #include<queue> 6 using namespace std; 7 struct node{ 8 int step; 9 char str[20]; 10 }; 11 int D[6]={-1,1,-2,2,-3,3}; 12 int len;//杯子个数 13 char str1[20],str2[20];//初始状态、目标状态 14 set<string> Set;//用Set存放跳的过程中的状态 15 queue<node> que;//node每一次跳跃之后的状态和已经跳跃的步数 16 int blank_pos(char *str) //空格的位置 17 { 18 for(int i=0; i<strlen(str); i++) 19 { 20 if(str[i]==‘*‘) 21 return i; 22 } 23 } 24 int bfs() 25 { 26 char next_str[20]; 27 node n,new_node; 28 int pos,next_pos; 29 while(!que.empty()) 30 { 31 n=que.front();//队首出队 32 //printf("%s\n",n.str); 33 que.pop(); 34 //得出‘*‘的位置 35 pos=blank_pos(n.str); 36 for(int i=0; i<6; i++) //*有五种跳法 37 { 38 strcpy(next_str,n.str);//将来next_str要在n.str的基础上改动，但是n.str一直不能动，因为是四个方向共用的 39 next_pos=pos+D[i]; 40 if(next_pos>=0&&next_pos<len) //将要走的那一步符合要求 41 { 42 //将接下来的状态表示出来（‘*‘变为 next_pos上的字符，next_pos上的字符变成‘*‘；查看set里是否有这个状态，若有就不走这一步，避免重复） 43 44 next_str[next_pos]=‘*‘; 45 next_str[pos]=n.str[next_pos]; 46 //判重 47 if(Set.find(next_str)==Set.end()) //表示没有找到重的 48 { 49 //将新的状态记录在队列和Set里 50 strcpy(new_node.str,next_str); 51 new_node.step=n.step+1; 52 que.push(new_node); 53 Set.insert(next_str); 54 //查看着个状态是不是目标状态 55 if(!strcmp(next_str,str2)) //即得到了目标状态 56 { 57 return new_node.step; 58 } 59 } 60 } 61 } 62 } 63 return -1; 64 } 65 int main(){ 66 node n; 67 int min; 68 scanf("%s",str1); 69 scanf("%s",str2);//目标 70 len=strlen(str1); 71 if(!strcmp(str1,str2)) //即得到了目标状态 72 { 73 printf("%d",0); 74 } 75 else 76 { 77 //初始状态放入队列和set容器 78 n.step=0; 79 strcpy(n.str,str1); 80 que.push(n); 81 Set.insert(n.str); 82 min=bfs();//广搜，找出最少步骤 83 printf("%d",min); 84 } 85 return 0; 86 }
原文：https://www.cnblogs.com/li-yaoyao/p/10547359.html
