八数码(手写队列版)

#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;

const int N = 1000;
string q[N * N];
int hh, tt = -1;

int bfs(string st) {
    unordered_map<string, int> d;
    d[st] = 0;
    q[ ++ tt] = st;

    string end = "12345678x";
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};

    while ( hh <= tt) {
        string t = q[hh ++];

        if (t == end) return d[t];

        int dis = d[t];
        int k = t.find('x');
        int x = k / 3, y = k % 3;

        for (int i = 0; i < 4; ++ i) {
            int a = x + dx[i];
            int b = y + dy[i];

            if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                swap(t[k], t[a * 3 + b]);

                if (!d.count(t)) {
                    d[t] = dis + 1;
                    q[++ tt] = t;
                }

                swap(t[k], t[a * 3 + b]);
            }
        }
    }

    return -1;
}

int main() {
    string st;
    char op[2];

    for (int i = 0; i < 9; ++ i) {
        scanf("%s", op);
        st += *op;
    }

    printf("%d", bfs(st));

    return 0;
}

八数码(STL队列版)

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

int bfs(string state)
{
    queue<string> q;
    unordered_map<string, int> d;

    q.push(state);
    d[state] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    string end = "12345678x";
    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        if (t == end) return d[t];

        int distance = d[t];
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[a * 3 + b], t[k]);
                if (!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[a * 3 + b], t[k]);
            }
        }
    }

    return -1;
}

int main()
{
    char s[2];

    string state;
    for (int i = 0; i < 9; i ++ )
    {
        cin >> s;
        state += *s;
    }

    cout << bfs(state) << endl;

    return 0;
}

首先在写题中不建议手写队列。
1. 因为手写队列需要确保把每种状态装入数组中，所有就需要考虑大概有多少种情况
2. 比如这道题为例，一共是是$9^8 \times 8$种情况，也就是说数组要开到$10^9$左右
3. 如果数组的所开大小把控不好，使用devc++运行时就会一直不出结果。在debug的时候一时半会很难定位到问题在哪
4. 所以建议直接使用STL,这样可以避免不必要的问题， 如果你能估算出这道题大概的有多少种情况。那就是手写队列吧hhhh