题解 P1379 【八数码难题】
STLGirlfriend
2018-08-01 12:17:40
# 题解
BFS。将初始状态压入队列，再尝试每一种变换，同时统计移动次数，直到出现目标状态。
## 状态的表示
这里使用 C++11 的新特性 `std::array<int, 9>` 来表示状态，为什么不使用普通数组的原因：
1. 可以直接作为队列元素类型~~（当然普通数组封装一个结构体也可以）~~。
2. 方便判重，具体见下文。
## 判重
这里使用一个 `std::unordered_set< std::array<int, 9> >` 来判重，现在 `std::array` 的好处就体现出来了：**可以直接作为集合类型**！
当然哈希函数还是要自己写，不过也不难，把状态压成一个 $9$ 位数就可以了。
# 代码
```c++
#include <cstdio>
#include <cctype>
#include <array>
#include <queue>
#include <unordered_set>
const int StateSize = 9;
const int Line = 3;
const int Row = 3;
typedef std::array<int, StateSize> State;
const State Goal = {1, 2, 3, 8, 0, 4, 7, 6, 5};
const int DirSize = 4;
const int Dx[DirSize] = {0, 1, 0, -1};
const int Dy[DirSize] = {1, 0, -1, 0};
struct Node {
State st;
int dist;
Node(const State &st, const int &dist = 0) : st(st), dist(dist) {}
};
struct StateHash {
size_t operator()(const State &s) const {
size_t v = 0;
for (int x : s)
v = v * 10 + x;
return v;
}
};
char getGraph() {
char c;
while (!isgraph(c = getchar()));
return c;
}
void readState(State &st) {
for (int i = 0; i < StateSize; ++i)
st[i] = getGraph() - '0';
}
int main() {
State st;
readState(st);
std::queue<Node> Q;
std::unordered_set<State, StateHash> S;
Q.push(Node(st));
S.insert(st);
while (!Q.empty()) {
Node &node = Q.front();
State &st = node.st;
if (st == Goal) {
printf("%d\n", node.dist);
break;
}
int z;
for (z = 0; z < StateSize; ++z) {
if (!st[z]) {
break;
}
}
int x = z / Line, y = z % Row;
for (int i = 0; i < DirSize; ++i) {
int _x = x + Dx[i], _y = y + Dy[i];
int _z = _x * Line + _y;
if (_x >= 0 && _x < Line && _y >= 0 && _y < Row) {
State _st = st;
_st[_z] = st[z];
_st[z] = st[_z];
if (!S.count(_st)) {
S.insert(_st);
Q.push(Node(_st, node.dist + 1));
}
}
}
Q.pop();
}
}
```