魔板
本题是bfs的最小步数模型,这种模型的难点在于如何表示每一个状态,本题选择用string来代表状态,用unordered_map来表示pre和dist数组。本题使用了get和set的思想,能方便的处理导出的字符串。还学会使用stl内置的queue。
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<stdio.h>
using namespace std;
char g[2][4];
unordered_map<string, pair<char, string>> pre;
unordered_map<string, int> dist;
int n;
string get() {
string s;
for (int i = 0; i < 4; i++)s += g[0][i];
for (int i = 3; i >=0; i--)s += g[1][i];//注意是反过来的
return s;
}
void set(string s) {
for (int i = 0; i < 4; i++)g[0][i] = s[i];
for (int i = 7, j = 0; j < 4; i--, j++) g[1][j] = s[i];
}
string move0(string s) {
reverse(s.begin(), s.end());
return s;
}
string move1(string s) {
set(s);
char t1 = g[0][3], t2 = g[1][3];
for(int i = 3; i >= 1; i--) {
g[0][i] = g[0][i - 1];
g[1][i] = g[1][i - 1];
}
g[0][0] = t1;
g[1][0] = t2;
return get();
}
string move2(string s) {
set(s);
char t = g[0][1];
g[0][1] = g[1][1];
g[1][1] = g[1][2];
g[1][2] = g[0][2];
g[0][2] = t;
return get();
}
int bfs(string start, string end) {
if (start == end)return 0;
queue<string> q;
q.push(start);
dist[start] = 0;
while (!q.empty()) {
string t = q.front();
q.pop();
string m[3];
m[0] = move0(t);
m[1] = move1(t);
m[2] = move2(t);
for (int i = 0; i < 3; i++) {
if (!dist.count(m[i])) {
dist[m[i]] = dist[t] + 1;
pre[m[i]] = { 'A' + i,t };
if (m[i] == end)return dist[m[i]];
q.push(m[i]);
}
}
}
return -1;
}
int main() {
int x;
string start, end;
for (int i = 0; i < 8; i++) {
cin >> x;
end += char('0' + x);
start += char('1' + i);
}
int ans = bfs(start, end);
cout << ans << endl;
string res;
while (end != start) {
res += pre[end].first;
end = pre[end].second;
}
reverse(res.begin(), res.end());
if(ans>0) cout << res;
return 0;
}