AcWing 845. 八数码 C++
原题链接
中等
作者:
LaChimere
,
2021-05-24 16:10:10
,
所有人可见
,
阅读 228
C++
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
bool legal(int x, int y) {
return x >= 0 && x < 3 && y >= 0 && y < 3;
}
int bfs(string start) {
string end = "12345678x";
queue<string> q;
unordered_map<string, int> dist;
int dx[]{-1, 1, 0, 0}, dy[]{0, 0, -1, 1};
q.push(start);
dist[start] = 0;
while (!q.empty()) {
auto s = q.front();
q.pop();
int d = dist[s];
if (s == end) {
return d;
}
int xPos = s.find('x');
int x = xPos/3, y = xPos%3;
for (int i = 0; i < 4; ++i) {
int nx = x+dx[i], ny = y+dy[i];
if (!legal(nx, ny)) {
continue;
}
int nxPos = 3*nx + ny;
swap(s[xPos], s[nxPos]);
if (dist.find(s) == dist.end()) {
dist[s] = d + 1;
q.push(s);
}
swap(s[nxPos], s[xPos]);
}
}
return -1;
}
int main() {
string start;
for (int i = 0; i < 9; ++i) {
char c;
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}