BFS
简单的 $bfs$,代码稍微有一点麻烦,主要在存储、判重和变换上。
采用结构体存储
struct Step {
string status, vary;
int step;
};
status 表示当前状态
vary 表示当前变换(由此可以节省从后向前推的过程)
step 表示当前步数
采用哈希表判重 unordered_map <string, int> mp;
三种简单的变换
可先用数组存起来,再变换,再转化为string。
第一种变换
for (int i = 0; i < 4; ++i) swap(a[0][i], a[1][i]);
第二种变换
for (int i = 0; i < 3; ++i) swap(a[0][3 - i], a[0][2 - i]), swap(a[1][3 - i], a[1][2 - i]);
// 最后一列向前交换三遍
第三种变换
int x = a[0][1];
a[0][1] = a[1][1];
a[1][1] = a[1][2];
a[1][2] = a[0][2];
a[0][2] = x;
// 按照顺势针覆盖即可
C++ 代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
string str = "";
struct Step {
string status, vary;
int step;
};
unordered_map <string, int> mp;
Step bfs()
{
queue <Step> q;
q.push({"12345678", "", 0});
while (!q.empty()) {
Step t = q.front();
q.pop();
if (t.status == str) {
return t;
}
for (int k = 0; k < 3; ++k) {
Step next;
int a[2][4];
for (int i = 0; i < 4; ++i) a[0][i] = t.status[i] - '0';
for (int i = 0; i < 4; ++i) a[1][3 - i] = t.status[4 + i] - '0'; // 1 2 3 4 5 6 7 8
if (k == 0) {
for (int i = 0; i < 4; ++i) swap(a[0][i], a[1][i]);
next.vary = t.vary + 'A';
}
if (k == 1) {
for (int i = 0; i < 3; ++i) swap(a[0][3 - i], a[0][2 - i]), swap(a[1][3 - i], a[1][2 - i]);
next.vary = t.vary + 'B';
}
if (k == 2) {
int x = a[0][1];
a[0][1] = a[1][1];
a[1][1] = a[1][2];
a[1][2] = a[0][2];
a[0][2] = x;
next.vary = t.vary + 'C';
}
for (int i = 0; i < 4; ++i) next.status += a[0][i] + '0';
for (int i = 0; i < 4; ++i) next.status += a[1][3 - i] + '0';
next.step = t.step + 1;
if (!mp[next.status]) {
q.push(next);
mp[next.status] = next.step;
}
}
}
}
int main()
{
int x;
while (cin >> x) str += x + '0'; // 目标状态
Step t = bfs();
cout << t.step << endl;
if (t.step) {
cout << t.vary << endl;
}
return 0;
}