题目描述
在一个 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
现在,给你一个初始网格,请你求出得到正确排列至少需要进行多少次交换。
样例
2 3 4 1 5 x 7 6 8
19
思路:bfs又叫宽度优先搜索,注意初始情况、队列存储的状态、结果如何存储,可能状态比较多,全局记得开大一点避免段错误,由于是最优路径只能走一次,那么要判断是否可以走到且没有被走到,走到后更新下一次的状态,可以记录上一次的状态,并将下次的状态存入队列当中,当状态改变时是否恢复现场。
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef pair<int,int>PI;
const int N=10;
string g;
PI pre[N][N];
string q[1000000];
void bfs()
{
int hh,tt;
hh=tt=0;
unordered_map<string,int>hash;
int n=g.find('x');
pre[n/3][n%3]={-1,-1};
hash[g]=0;
q[hh]=g;
string end="12345678x";
while(hh<=tt)
{
string t=q[hh++];
int d=hash[t];
n=t.find('x');
if(t==end)
{
cout<<d<<endl;
return ;
}
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
for(int i=0;i<4;i++)
{
int x=dx[i]+n/3;
int y=dy[i]+n%3;
if(x>=0&&x<3&&y>=0&&y<3)
{
swap(t[x*3+y],t[n]);
if(!hash.count(t))
{
pre[x][y]={n/3,n%3};
hash[t]=d+1;
q[++tt]=t;
}
swap(t[x*3+y],t[n]);
}
}
}
cout<<-1<<endl;
return ;
}
int main()
{
char a[2];
for(int i=0;i<9;i++)
{
cin>>a;
g+=*a;
}
bfs();
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla