2022秋招备战！每天写至少一篇Leetcode里Hard难度题目的题解

773. 滑动谜题

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.

一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

示例：

输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成
输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板
输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]
输入：board = [[3,2,4],[1,5,0]]
输出：14

提示：

• board 是一个如上所述的 2 x 3 的数组.
• board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.

压缩成字符串后进行BFS+优化分类讨论

一道非常经典的题。

本题的状态固定成2X3后，用字符串进行保存可以视为常数。

将字符串放为queue里进行简单BFS即可，出人意料的简单。

有以下4种情况考虑:

1. 如果不是右侧的2个滑板，则可以往右边移动。
2. 如果不是左侧的2个滑板，则可以往左边移动。
3. 如果在第一行，则可以往下移动。
4. 如果在第二行，则可以向上移动。

可以写出非常丑陋的4个情况的硬核代码。

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        unordered_set<string> visited;
        string state;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                state += board[i][j] + '0';
            }
        }
        queue<pair<string,int>>q;
        q.emplace(state,0);
        visited.insert(state);
        while (!q.empty()) {
            auto cur = q.front(); q.pop();  
            if (cur.first == "123450") return cur.second;                  
            int i  = (int)cur.first.find("0");
            if (i != 5 && i != 2) {
                auto curState = cur.first;
                swap(curState[i], curState[i+1]);
                if (visited.find(curState) == visited.end()) {
                    q.emplace(curState, cur.second + 1);
                    visited.insert(curState);
                }
            }

            if (i != 0 && i != 3) {
                auto curState = cur.first;
                swap(curState[i], curState[i - 1]);
                if (visited.find(curState) == visited.end()) {
                    q.emplace(curState, cur.second + 1);
                    visited.insert(curState);
                }
            }

            if (i < 3) {
                auto curState = cur.first;
                swap(curState[i], curState[i + 3]);
                    if (visited.find(curState) == visited.end()) {
                        q.emplace(curState, cur.second + 1);
                        visited.insert(curState);
                    }
                }
                if (i >= 3) {
                    auto curState = cur.first;
                    swap(curState[i], curState[i - 3]);
                    if (visited.find(curState) == visited.end()) {
                        q.emplace(curState, cur.second + 1);
                        visited.insert(curState);
                    }
                }
            }
        return -1;
    }
};

如何简化中间的分类讨论?

我们可以发现我们只需要讨论空缺的部分会被哪个数字填充即可。

我们以0，也就是空缺的部分为基准点，得到0在字符串中的位置。

int i = (int)cur.first.find("0");

接下来我们对当前状态的每个位置进行讨论，也就是0-5，6种情况。

如果当前位置为0，则无需讨论。直接continue，因为是空缺

如果当前数字和空缺的位置处在同一列，则可以交换2个数字的位置。

k % 3 == i % 3

如果当前数字和空缺的位置在同一行切相邻，也可以交换2个数字的位置

abs(k - i) <= 1 && k/3 == i/3

优化后的代码：

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        unordered_set<string> visited;
        string state;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                state += board[i][j] + '0';
            }
        }
        queue<pair<string,int>>q;
        q.emplace(state, 0);
        visited.insert(state);
        while (!q.empty()) {
            auto cur = q.front(); q.pop();  
            if (cur.first == "123450") return cur.second;                  
            int i  = (int)cur.first.find("0");
            for (int k = 0; k < 6; k++) {
                if (k == i) continue;
                if (k % 3 == i % 3 || (abs(k - i) <= 1 && k/3 == i/3)){
                    auto curState = cur.first;
                    swap(curState[i], curState[k]);
                    if (visited.find(curState) == visited.end()) {
                        q.emplace(curState, cur.second + 1);
                        visited.insert(curState);
                    }

                }
            }
        }
        return -1;
    }
};