AcWing 1107. 魔板
原题链接
简单
作者:
no_one
,
2022-06-20 13:43:23
,
所有人可见
,
阅读 242
// 魔鬼--还是来分析代码吧
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
char g[2][4]; // 储存每一次变化
unordered_map<string, pair<char, string>> pre; // 储存每一次扩展的操作ABC以及结果
unordered_map<string, int> dist;
void set(string state) // 将state 转化成两行矩阵形式
{
for (int i = 0; i < 4; i ++ ) g[0][i] = state[i];
for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i];
}
string get() // 将两行矩阵转换成一行字符串形式
{
string res;
for (int i = 0; i < 4; i ++ ) res += g[0][i];
for (int i = 3; i >= 0; i -- ) res += g[1][i];
return res;
}
string move0(string state)// 操作A
{
set(state);
for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]);
return get();
}
string move1(string state) // 操作B
{
set(state);
int v0 = g[0][3], v1 = g[1][3];
for (int i = 3; i >= 0; i -- )
{
g[0][i] = g[0][i - 1];
g[1][i] = g[1][i - 1];
}
g[0][0] = v0, g[1][0] = v1;
return get();
}
string move2(string state) // 操作C
{
set(state);
int v = g[0][1];
g[0][1] = g[1][1];
g[1][1] = g[1][2];
g[1][2] = g[0][2];
g[0][2] = v;
return get();
}
int bfs(string start, string end) // 正常bfs流程
{
if (start == end) return 0;
queue<string> q;
q.push(start);
dist[start] = 0;
while (!q.empty())
{
auto 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 ++ ) // 按操作位ABC 的顺序扩展 确保是最大字典顺序。
if (!dist.count(m[i])) // 如果没被搜过
{
dist[m[i]] = dist[t] + 1; // 更新距离
pre[m[i]] = {'A' + i, t}; // 储存操作以及结果
q.push(m[i]);
if (m[i] == end) return dist[end];
}
}
return -1;
}
int main()
{
int x;
string start, end;
for (int i = 0; i < 8; i ++ )
{
cin >> x;
end += char(x + '0'); // 将读入的特殊序列变成字符串形式
}
for (int i = 1; i <= 8; i ++ ) start += char('0' + i); // 初始化为12345678
int step = bfs(start, end); // 储存距离
cout << step << endl; // 输出距离
string res;
while (end != start)
{
res += pre[end].first; // 更新答案操作
end = pre[end].second; // 让end变成他的前驱
}
reverse(res.begin(), res.end()); // 因为是从end到start 所以需要反序
if (step > 0) cout << res << endl;
return 0;
}