题目描述
bfs模板,主要是字符串一维变换成二维
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
string ans = "12345678x";
string s;
int h[] = {-1 , 0 , 1 , 0};
int z[] = {0 , 1 , 0 , -1};
queue<string> q;
unordered_map<string , string> mp;
void bfs()
{
q.push(s);
int flag = 0;
while(!q.empty())
{
auto it = q.front();
q.pop();
string dist = mp[it];
if(it == ans)
{
cout << dist <<endl;
flag = 1;
break;
}
for(int i = 0 ; i < 4 ; i++)
{
int f = it.find('x');
int hx = f / 3 + h[i];
int zy = f % 3 + z[i];
if(hx >= 0 && zy >= 0 && hx < 3 && zy < 3)
{
swap(it[f] , it[hx * 3 + zy]);
if(mp[it] == "")
{
int k = (hx * 3 + zy) - f;
if(k == 1) mp[it] = dist + 'r';
else if(k == -1) mp[it] = dist + 'l';
else if(k == 3) mp[it] = dist + 'd';
else if(k == -3) mp[it] = dist + 'u';
q.push(it);
}
swap(it[f] , it[hx * 3 + zy]);
}
}
}
if(flag == 0) cout << "unsolvable" << endl;
}
int main()
{
for(int i = 0 ; i < 9 ; i++)
{
char x;
cin >> x;
s += x;
}
bfs();
return 0;
}