题解 P1379 【八数码难题】

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$ 位数就可以了。

代码

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