题目描述

解题思路

本题若直接在3*3网格中思考较为困难，可以转换为一维的字符串，在一维字符串中考虑较为简单，要注意本题中两个字符交换位置时只能是x和另外字符交换，本题另外一个难点在于如何维护一个距离数组用于表示交换的次数（可用map，代码中会有注释）

代码如下

#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int> dist;//维护一个从开始状态到结束状态的转换次数
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//上下左右移动的数轴，dx是左右移动，dy是上下移动
string s1="12345678x";//最终状态，用于和中间状态进行比较int bfs(string s)
{queue<string> q;q.push(s);dist[s]=0;//刚开始是转换次数为0while(q.size()){string f=q.front();q.pop();int distance = dist[f];//将这个状态的转换次数存起来，因为下面会交换元素位置if(f==s1) return distance;int k=f.find('x');int x=k/3,y=k%3;//将s中的元素的一维位置转换为3*3的位置元素for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(a>=0&&a<3&&b>=0&&b<3){swap(f[k],f[a*3+b]);//再将3*3中的位置转换为s中的一维位置if(!dist.count(f)){dist[f] = distance+1;q.push(f);}swap(f[k],f[a*3+b]);//转换完之后要再转回来}}}return -1;
}int main()
{string s;char c;for(int i=0;i<3;i++)for(int j=0;j<3;j++){cin>>c;s+=c;}cout<<bfs(s)<<endl;return 0;
}