AcWing 1107. 魔板
原题链接
简单
作者:
王小强
,
2021-02-06 12:13:21
,
所有人可见
,
阅读 472
BFS Algorithm
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;
const string start = "12345678";
string goal;
unordered_map<string, pair<string, int>> parents;
// 交换上下两行
string a(string state) {
std::reverse(begin(state), end(state));
return state;
}
// 将最右边的一列插入到最左边
string b(const string_view state) {
string s;
s += state[3];
s += state[0];
s += state[1];
s += state[2];
s += state[5];
s += state[6];
s += state[7];
s += state[4];
return s;
}
string c(const string_view state) {
string s;
s += state[0];
s += state[6];
s += state[1];
s += state[3];
s += state[4];
s += state[2];
s += state[5];
s += state[7];
return s;
}
// 魔板中央对的4个数作顺时针旋转
string change_state(int op, const string state) {
switch (op) {
case 0: return a(state); // 交换上下两行
case 1: return b(state); // 将最右边的一列插入到最左边
case 2: return c(state); // 魔板中央对的4个数作顺时针旋转
}
}
int bfs() {
queue<string> q{{start}};
unordered_set<string> seen{start};
int steps = 0;
while (not q.empty()) {
size_t sz = q.size();
while (sz--) {
const auto cur_state = q.front(); q.pop();
if (cur_state == goal) return steps;
for (int i = 0; i < 3; ++i) {
string new_state = change_state(i, cur_state);
if (!seen.emplace(new_state).second) continue;
q.emplace(new_state);
parents[new_state] = {cur_state, i};
}
}
++steps;
}
return -1;
}
int main(void) {
int x;
for (int i = 0; i < 8; ++i) {
cin >> x;
goal += x + '0';
}
int steps = bfs();
cout << steps << endl;
if (steps > 0) {
vector<char> v;
string cur = goal;
while (cur != start) {
v.emplace_back(parents.at(cur).second + 'A');
cur = parents.at(cur).first;
}
std::reverse(begin(v), end(v));
for (const auto& x : v) printf("%c", x);
}
return 0;
}