思路
将每种二维形态的矩阵压缩成一维,用哈希表记录每种形态已经交换的次数。
1、首先找到特殊字符 ‘x’ 在一维形态中的位置,将其转换3*3的二维地址。
变换方式为:假设 ‘x’ 在一维数组中的位置是k 则k = string.find(‘x’)
则 ‘x’ 在二维形态中的坐标为 x = k / n , y = k % n
2、对每个方向进行转移, 对于每次转移, 若符合位置条件, 则交换两个字符。
将二维位置转换为一维的位置 : pos(一维) = x * n + y (x, y为二维坐标)
如果此种状态没有出现过: hash.count(string) == 0, 则将其位置记录一下, 并将其入队列。
3、最后记得恢复现场
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
//最终想要得到的形态ed
string ed = "12345678x";
unordered_map<string,int> mp;
int bfs(string st)
{
queue<string> q;
q.push(st);
//记录初始形态交换的次数为0
mp[st] = 0;
// 对初始形态做BFS
while(q.size())
{
auto t = q.front();
q.pop();
int cnt = mp[t];
//如果已经变换到了最终形态 直接返回变换到该种形态需要的次数
if(t == ed) return cnt;
//找到'x'在一维形态中的位置并将其转换成在二维形态中的位置(x, y)
int k = t.find('x');
int x = k / 3, y = k % 3;
for(int i = 0; i < 4; ++ i ){
int u = x + dx[i];
int v = y + dy[i];
if(u < 3 && u >= 0 && v < 3 && v >= 0 ){
//本质是与四个方向的字符进行交换 交换后t已经变成了新的形态
swap(t[k], t[u * 3 + v]);
//检查交换完后新的形态是否已经通过变换得到过
if(!mp.count(t)){
/*如果没有出现过,记录得到新的形态需要的变换次数为前一个形态需要的变换次数 + 1
如果已经出现过,则不需要记录因为是宽搜所以变换次数一定无法被更新*/
mp[t] = cnt + 1;
q.push(t);
}
//恢复现场
swap(t[k],t[u * 3 + v]);
}
}
}
return -1;
}
int main()
{
//st为初始形态,用一维表示
string st;
for(int i = 0; i < 9; ++ i ){
char c;
cin >> c;
st += c;
}
cout << bfs(st);
return 0;
}
while少打了一个)
感谢指正