773. Sliding Puzzle

bfs O(r*c*(r*c)!) time O(r*c*(r*c)!) space
这道题也可以用A*算法

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int res = 0, m = board.size(), n = board[0].size();
        string target = "123450", start;
        for (const auto &v : board) {
            for (char c : v) {
                start += '0' + c; // 得到初始状态的board
            }
        }
        vector<vector<int>> next{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}}; // 当0在每个位置时的下一步能去哪
        unordered_set<string> visited{start}; // 用字符串来保存状态
        queue<string> q{{start}};
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto cur = q.front(); q.pop();
                if (cur == target) return res;
                int zero_idx = cur.find("0");
                for (int v : next[zero_idx]) { // 查表来枚举所有可能产生的下个board状态
                    swap(cur[v], cur[zero_idx]);
                    if (!visited.count(cur)) {
                        visited.insert(cur);
                        q.push(cur);
                    }
                    swap(cur[v], cur[zero_idx]);
                }
            }
            ++res;
        }
        return -1;
    }
};

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int res = 0, m = board.size(), n = board[0].size();
        string target = "123450", start;
        vector<vector<int>> next{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}}; // 当0在每个位置时的下一步能去哪
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                start += '0' + board[i][j]; // 得到初始状态的board
            }
        }
        unordered_set<string> visited{start}; // 用字符串来保存状态
        queue<string> q{{start}};
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                string cur = q.front(); q.pop();
                if (cur == target) return res;
                int zero_idx = cur.find("0");
                for (int v : next[zero_idx]) { // 查表来枚举所有可能产生的下个board状态
                    string cand = cur;
                    swap(cand[v], cand[zero_idx]);
                    if (visited.count(cand)) continue;
                    visited.insert(cand);
                    q.push(cand);
                }
            }
            ++res;
        }
        return -1;
    }
};

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        auto hash = [](const vector<vector<int>> &b) {
            int res = 0;
            for (const auto &v : b) {
                for (int x : v) {
                    res = res * 10 + x;
                }
            }
            return res;
        };
        unordered_set<vector<vector<int>>, decltype(hash)> m(33, hash); // 必须要提供初始桶的个数！！
        queue<vector<vector<int>>> q;
        q.push(board);
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        int res = 0;
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                auto b = q.front(); q.pop();
                if (hash(b) == 123450) return res;
                if (m.count(b)) continue;
                m.insert(b);
                auto v = find(b);
                for (int j = 0; j < 4; ++j) {
                    auto t = v;
                    t[0] += dr[j];
                    t[1] += dc[j];
                    if (t[0] < 0 || t[0] > 1 || t[1] < 0 || t[1] > 2) continue;
                    swap(b[v[0]][v[1]], b[t[0]][t[1]]);
                    q.push(b);
                    swap(b[v[0]][v[1]], b[t[0]][t[1]]);
                }
            }
            ++res;
        }
        return -1;
    }

    vector<int> find(const vector<vector<int>> &b) {
        for (int r = 0; r < 2; ++r) {
            for (int c = 0; c < 3; ++c) {
                if (b[r][c] == 0) return {r, c};
            }
        }
    }
};