这题我思考了很久,但是终究没有做出来,原因是思考方向不对,我想的是通过模拟样例找到最小交换次数的规律,从而得出某种算法的模型,然而行不通。
这题其实和走迷宫差不多,就是每条路都试一遍,枚举所有的可能性,因为是找最小的交换次数,所以可以用bfs。难点在于如何表示每种状态,状态即3*3格子里数的分布情况,可以将其压缩成一维的字符串,用一维二维坐标转换实现,状态之间转移的次数用哈希表记录。
#include <bits/stdc++.h>
using namespace std;
int bfs(string start)
{
unordered_map<string, int> d;
d[start] = 0;
queue<string> q;
q.push(start);
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
string end = "12345678x";
while(q.size())
{
auto t = q.front();
q.pop();
int distance = d[t];
if (t == end) return d[t];
int k = t.find('x');
int x = k / 3, y = k % 3;
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)
{
swap(t[k], t[a * 3 + b]);
if (!d.count(t)) // 如果再次到达该状态则跳过,相当于图中已访问的结点
{
q.push(t);
d[t] = distance + 1;
}
swap(t[k], t[a * 3 + b]);
}
}
}
return -1;
}
int main()
{
char s[2];
string start = "";
for (int i = 0; i < 9; i ++ )
{
cin >> s;
start += *s;
}
cout << bfs(start) << endl;
return 0;
}