题目链接

Seven Puzzle Aizu - 0121

思路

bfs不必多说，状态可以用康托展开，也可以直接用map，字符串hash表。

第一次写完超时，优化方法就是从终点跑一边bfs然后把其他状态的答案都记住。

时间复杂度

$$ O(2^8) ? $$

代码

#include <cstdio>
#include <string>
#include <map>
#include <queue>
#include <iostream>

using namespace std;

string g = "01234567";
map<string, int> mmp;
void bfs(string cur) {

    queue<string> que;
    mmp[cur] = 0;
    que.push(cur);
    while (!que.empty()) {
        cur = que.front();
        que.pop();
        for (int i = 0; i < 8; i++) {
            if (cur[i] == '0') {
                if (i <= 3) {
                    string nxt = cur;
                    nxt[i] = cur[i + 4];
                    nxt[i + 4] = cur[i];
                    if (mmp.count(nxt) == 0) {
                        mmp[nxt] = mmp[cur] + 1;
                        que.push(nxt);
                    }
                }
                if (i >= 4) {
                    string nxt = cur;
                    nxt[i] = cur[i - 4];
                    nxt[i - 4] = cur[i];
                    if (mmp.count(nxt) == 0) {
                        mmp[nxt] = mmp[cur] + 1;
                        que.push(nxt);
                    }
                }
                if (i != 0 && i != 4) {
                    string nxt = cur;
                    nxt[i] = cur[i - 1];
                    nxt[i - 1] = cur[i];
                    if (mmp.count(nxt) == 0) {
                        mmp[nxt] = mmp[cur] + 1;
                        que.push(nxt);
                    }
                }
                if (i != 3 && i != 7) {
                    string nxt = cur;
                    nxt[i] = cur[i + 1];
                    nxt[i + 1] = cur[i];
                    if (mmp.count(nxt) == 0) {
                        mmp[nxt] = mmp[cur] + 1;
                        que.push(nxt);
                    }
                }
            }
        }
    }
}

int main() {
    bfs(g);
    string cur;
    int x;
    while (~scanf("%d", &x)) {
        cur = '0' + x;
        for (int i = 1; i <= 7; i++) {
            scanf("%d", &x);// don't forget &
            cur += '0' + x;
        }
        printf("%d\n", mmp[cur]);
    }
    return 0;
}