python/TangDou/AcWing/BFS/845_unordered_map.cpp

#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
string ed = "12345678x";

unordered_map<string, int> d;

int bfs(string s) {
    queue<string> q;
    q.push(s);
    d[s] = 0;

    while (q.size()) {
        auto u = q.front();
        q.pop();
        
        if (u == ed) return d[u];
        int k = u.find('x');
        int x = k / 3, y = k % 3; // 一维变二维,准备变更，判断变更后会不会出界

        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 0 || tx > 2 || ty < 0 || ty > 2) continue;

            string c = u;               // 抄出来c
            swap(c[k], c[tx * 3 + ty]); // 在c上进行变更，二维变一维
            if (!d.count(c)) {          // 这个状态没到达过
                d[c] = d[u] + 1;        // 记录是第几步到达
                q.push(c);
            }
        }
    }
    return -1;
}

int main() {
    string s;
    char c;
    for (int i = 1; i <= 9; i++) { // 输入的是9个字符，每两个中间有空格
        cin >> c;
        s += c;
    }
    cout << bfs(s) << endl;
    return 0;
}