题目描述
在一个3×3的网格中,1~8这8个数字和一个“x”恰好不重不漏地分布在这3×3的网格中。
例如:
1 2 3
x 4 6
7 5 8
在游戏过程中,可以把“x”与其上、下、左、右四个方向之一的数字交换(如果存在)。
我们的目的是通过交换,使得网格变为如下排列(称为正确排列):
1 2 3
4 5 6
7 8 x
例如,示例中图形就可以通过让“x”先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下:
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
现在,给你一个初始网格,请你求出得到正确排列至少需要进行多少次交换。
算法:宽度优先搜索
时间复杂度:$N!$
C++代码
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>
#include<iostream>
using namespace std;
string ter="12345678x";
string str;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int bfs(string s)
{
unordered_map<string,int>d;
d[s]=0;
queue<string>q;
q.push(s);
while(q.size()){
auto t=q.front();
q.pop();
if(t==ter)return d[t];
int k=t.find('x');
int x=k/3,y=k%3;
int distance=d[t];
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)continue;
swap(t[k],t[a*3+b]);
if(!d.count(t)){
d[t]=distance+1;
q.push(t);
}
swap(t[k],t[a*3+b]);
}
}
return -1;
}
int main()
{
char s[2];
while(scanf("%s",s)!=-1)str+=*s;
cout<<bfs(str)<<endl;
return 0;
}