题目链接：http://lx.lanqiao.cn/problem.page?gpid=T42
题意：中文题诶～
思路：bfs
将没种九宫格的状态看作一个状态节点，那么只需求起始节点到目标节点的最短路径即可，可以用bfs解决。
代码：
1 #include <iostream> 2 #include <string> 3 #include <string.h> 4 #include <queue> 5 #include <map> 6 #define MAXN 9 7 using namespace std; 8 9 struct node{ 10 int matrix[MAXN];//**存储当前九宫格状态 11 int v; 12 bool operator <(const node &r) const{//**后面用map标记,map是有序对，需要重载比较运算符 13 for(int i=0; i<MAXN; i++){ 14 if(matrix[i]!=r.matrix[i]){ 15 return matrix[i]<r.matrix[i]; 16 } 17 } 18 return r.matrix[0]<matrix[0]; 19 } 20 }; 21 22 const int dir[4][2]={0, 1, 0, -1, 1, 0, -1, 0};//记录方向 23 map<node, bool> mp;//标记节点 24 25 bool is_ok(node q, node e){//判断是否达到目标状态 26 for(int i=0; i<9; i++){ 27 if(q.matrix[i]!=e.matrix[i]){ 28 return false; 29 } 30 } 31 return true; 32 } 33 34 void scan(string str, node &r){//将输入字符串转化为状态数组 35 for(int i=0; i<9; i++){ 36 int x=str[i]-'0'; 37 if(x>=0&&x<=9){ 38 r.matrix[i]=x; 39 }else{ 40 r.matrix[i]=0; 41 r.v=i; 42 } 43 } 44 } 45 46 int bfs(node s, node e){//bfs开始状态与目标状态的最短距离 47 int ans=0; 48 queue<node> q; 49 q.push(s); 50 mp[s]=true; 51 if(is_ok(s, e)){//达到目标状态 52 return ans; 53 } 54 int gg[MAXN]; 55 while(!q.empty()){//搜索目标状态 56 int q_size=q.size(); 57 while(q_size--){ 58 node now=q.front(), cc; 59 q.pop(); 60 int x=now.v/3, y=now.v%3; 61 for(int i=0; i<4; i++){ 62 int fx=x+dir[i][0]; 63 int fy=y+dir[i][1]; 64 if(fx>=0&&fx<3&&fy>=0&&fy<3){ 65 int v=fx*3+fy; 66 memcpy(gg, now.matrix, sizeof(now.matrix)); 67 swap(gg[v], gg[now.v]); 68 memcpy(cc.matrix, gg, sizeof(gg)); 69 cc.v=v; 70 if(mp[cc]) continue; 71 if(is_ok(cc, e)){//判断是否达到目标状态 72 return ans+1; 73 } 74 mp[cc]=true;//标记 75 q.push(cc);//入队 76 } 77 } 78 } 79 ans++; 80 } 81 return -1; 82 } 83 84 int main(void){ 85 string str1, str2; 86 int x; 87 node s, e; 88 cin >> str1 >> str2; 89 scan(str1, s); 90 scan(str2, e); 91 int ans=bfs(s, e); 92 cout << ans << endl; 93 return 0; 94 }
如果步数比较多的话，可以用数组模拟队列
代码：
1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 5 typedef int State[9]; //定义状态类 6 const int MAXN=1e6+10; 7 const int hashsize=1e6+3; 8 State st[MAXN], goal; //状态数组 9 int dist[MAXN]; //距离数组 10 int head[hashsize], next[hashsize]; 11 12 const int dx[]={-1, 1, 0, 0}; 13 const int dy[]={0, 0, -1, 1}; 14 15 int hash(State& s){//hash一下，标记节点 16 int v=0; 17 for(int i=0; i<9; i++){ 18 v=v*10+s[i]; 19 } 20 return v%hashsize; 21 } 22 23 int try_to_insert(int s){ 24 int h=hash(st[s]); 25 int u=head[h]; 26 while(u){ 27 if(memcmp(st[s], st[u], sizeof(st[s]))==0){ 28 return 0; 29 } 30 u=next[u]; 31 } 32 next[s]=head[h]; 33 head[h]=s; 34 return 1; 35 } 36 37 void init() { 38 memset(head, 0, sizeof(head)); 39 } 40 41 int bfs(void){ //返回目标状态在st数组的下标 42 init(); //初始化 43 int front=1, rear=2; //从1开始 44 while(front<rear){ 45 State& s=st[front]; 46 if(memcmp(goal, s, sizeof(s))==0){ //找到目标状态 47 return front; 48 } 49 int z; 50 for(z=0; z<9; z++){ 51 if(!s[z]){ // 找到0的位置 52 break; 53 } 54 } 55 int x=z/3, y=z%3; 56 for(int i=0; i<4; i++){ 57 int fx=x+dx[i], fy=y+dy[i]; 58 int fz=fx*3+fy; 59 if(fx>=0&&fx<3&&fy>=0&&fy<3){ //如果移动合法 60 State& t=st[rear]; 61 memcpy(&t, &s, sizeof(s));//扩展新节点 62 t[fz]=s[z]; 63 t[z]=s[fz]; 64 dist[rear]=dist[front]+1; //更新新节点的距离 65 if(try_to_insert(rear)){ //如果成功插入查找表，更新队尾指针 66 rear++; 67 } 68 } 69 } 70 front++; //扩展完毕后再修改队首指针 71 } 72 return 0; 73 } 74 75 int main(void){ 76 string str1, str2; 77 cin >> str1 >> str2; 78 for(int i=0; i<9; i++){ 79 if(str1[i]=='.'){ 80 st[1][i]=0; 81 }else{ 82 st[1][i]=str1[i]-'0'; 83 } 84 } 85 for(int i=0; i<9; i++){ 86 if(str2[i]=='.'){ 87 goal[i]=0; 88 }else{ 89 goal[i]=str2[i]-'0'; 90 } 91 } 92 int ans=bfs(); 93 if(ans>0){ 94 cout << dist[ans] << endl; 95 }else{ 96 cout << -1 << endl; 97 } 98 return 0; 99 }