LeetCode 773 Sliding Puzzle

概述

https://leetcode.com/problems/sliding-puzzle/

这是一道 Hard 题。

宽度优先搜索

醉了，两个 bug：

1. 序列化那里多乘了一个 10，打印结果才发现的；
2. for 循环里，没有用 c.first，而是用错成了 board。。。

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        unordered_map<int, bool> visited;
        queue<pair<vector<vector<int>>, vector<int>>> q;
        int bi, bj;
        for (int i = 0; i < board.size(); i ++) {
            for (int j = 0; j < board[0].size(); j ++) {
                if (board[i][j] == 0) {
                    bi = i;
                    bj = j;
                    break;
                }
            }
        }
        q.push({board, {bi, bj}});
        visited[board2int(board)] = true;
        int target = 123450;
        int step = 0;
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i ++) {
                auto c = q.front(); q.pop();
                if (board2int(c.first) == target) return step;
                int bi = c.second[0];
                int bj = c.second[1];
                if (bi != 0) {
                    auto temp = c.first;
                    temp[bi][bj] = temp[bi-1][bj];
                    temp[bi-1][bj] = 0;
                    if (!visited[board2int(temp)]) {
                        visited[board2int(temp)] = true;
                        q.push({temp, {bi-1, bj}});
                    } 
                }
                if (bi != 1) {
                    auto temp = c.first;
                    temp[bi][bj] = temp[bi+1][bj];
                    temp[bi+1][bj] = 0;
                    if (!visited[board2int(temp)]) {
                        visited[board2int(temp)] = true;
                        q.push({temp, {bi+1, bj}});
                    }                    
                }
                if (bj != 0) {
                    auto temp = c.first;
                    temp[bi][bj] = temp[bi][bj-1];
                    temp[bi][bj-1] = 0;
                    if (!visited[board2int(temp)]) {
                        visited[board2int(temp)] = true;
                        q.push({temp, {bi, bj-1}});
                    }                       
                }
                if (bj != 2) {
                    auto temp = c.first;
                    temp[bi][bj] = temp[bi][bj+1];
                    temp[bi][bj+1] = 0;
                    if (!visited[board2int(temp)]) {
                        visited[board2int(temp)] = true;
                        q.push({temp, {bi, bj+1}});
                    } 
                }                
            }
            step ++;
        }
        return -1;
    }
    
    int board2int(vector<vector<int>>& board) {
        int res = 0;
        for (int i = 0; i < board.size(); i ++) {
            for (int j = 0; j < board[0].size(); j ++) {
                res += board[i][j];
                res *= 10;
            }
        }
        res /= 10;
        return res;
    }
};

Links: leetcode-773-sliding-puzzle

未经允许，禁止转载，本文源站链接：https://iamazing.cn/