2018-08-01 12:17:40

# 题解

BFS。将初始状态压入队列，再尝试每一种变换，同时统计移动次数，直到出现目标状态。

## 状态的表示

1. 可以直接作为队列元素类型（当然普通数组封装一个结构体也可以）
2. 方便判重，具体见下文。

# 代码

#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;
}

for (int i = 0; i < StateSize; ++i)
st[i] = getGraph() - '0';
}

int main() {
State 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();
}
}
• star
首页