AcWing 845. 八数码
原题链接
中等
作者:
王小强
,
2021-02-01 16:21:28
,
所有人可见
,
阅读 294
现代化的BFS模版代码! BY THE WAY
这题和 LEETCODE 773 解题思络一模一样!
#include <bits/stdc++.h>
// #include <iostream>
// #include <unordered_set>
// #include <queue>
using namespace std;
const string goal = "12345678x";
static constexpr int dirs[] = {0, -1, 0, 1, 0}; // directions
// breadth frist search
int bfs(string start) {
queue<string> q{{start}};
unordered_set<string> seen{start};
int steps = 0;
while (not q.empty()) {
++steps;
size_t sz = q.size();
while (sz--) {
const string s = q.front(); q.pop();
int p = s.find('x'); // p == position
int y = p / 3, x = p % 3; // 一维坐标转两二维坐标 ...
for (int i = 0; i < 4; i++) {
int nx = x + dirs[i], ny = y + dirs[i + 1]; // nx == new_x == neighbor_x. ny 同理
if (nx < 0 || ny < 0 || nx >= 3 || ny >= 3) continue;
int pp = ny * 3 + nx; // 两维坐标再转回一维坐标
string t = s; // copy
swap(t[p], t[pp]);
if (t == goal) return steps;
if (seen.count(t)) continue; // visited
q.emplace(t);
seen.emplace(t);
}
}
}
return -1;
}
string start;
char c;
int main(void) {
for (int i = 0; i < 9; ++i) {
cin >> c;
start += c;
}
// corner case 老外的题目可能会阴险
if (start == goal) {
cout << 0 << endl;
return 0;
}
cout << bfs(start) << endl;
return 0;
}