题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int bfs(string start)
{
string end="12345678x";
queue<string> q;
unordered_map<string,int> m;
q.push(start);
m[start]=0;
while(q.size())
{
auto t=q.front();
q.pop();
if(t==end) return m[t];
int dis=m[t];
int k=t.find('x');
int x=k/3,y=k%3;
for(int i=0;i<4;i++)
{
int xx=dx[i]+x,yy=dy[i]+y;
if(xx>=0 && xx<3&&yy>=0&&yy<3)
{
swap(t[k],t[3*xx+yy]);
if(m.count(t)==0)
{
m[t]=dis+1;
q.push(t);
}
swap(t[k],t[3*xx+yy]);
}
}
}
return -1;
}
int main()
{
string start;
for(int i=0;i<9;i++)
{
char num;
cin>>num;
start+=num;
}
cout<<bfs(start)<<endl;
return 0;
}