题目描述
blablabla
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
unordered_map[HTML_REMOVED] dist;
string sr;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int bfs()
{
string et=”12345678x”;
queue[HTML_REMOVED] q;
q.push(sr);
dist[sr]=0;
while(q.size())
{
auto t=q.front();
q.pop();
if(t==et)
return dist[t];
int dis=dist[t];
int k=t.find(‘x’);
int x=k/3;
int y=k%3;
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0&&nx<3&&ny>=0&&ny<3)
{
swap(t[k],t[nx3+ny]);
if(!dist.count(t))
{
q.push(t);
dist[t]=dis+1;
}
swap(t[k],t[nx3+ny]);
}
}
}
return -1;
}
int main()
{
for(int i=1;i<=9;i++)
{
char x;
cin>>x;
sr+=x;
}
cout<<bfs();
return 0;
}
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla