Leetcode – 滑动谜题

这是我参与更文挑战的第 26 天，活动详情查看更文挑战

题目描述

在一个 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 是一个如上所述的 3 x 3 的数组.
• board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.

解题思路

我们可以使用广度优先搜索，找出从初始状态 board 到目标状态 [[1,2,3],[4,5,0]] 的最小交换次数。

具体地，我们在一开始将 (board,0) 加入队列，并使用该队列进行广度优先搜索。在搜索的过程中，设当前搜索到的状态为 status，操作的次数为 step，我们可以枚举 status 通过一次操作得到的状态。设其中的某个状态为 next_status，如果其没有被搜索过，我们就将 (next_status,step+1) 加入队列。如果搜索到了 target，我们就返回其对应的操作次数。

在搜索的过程中，我们需要一个哈希表存储所有搜索到的状态，避免重复搜索。

如果搜索完成后，我们仍没有搜索到 [[1,2,3],[4,5,0]]，说明我们无法解开谜板，返回 −1

代码

C++代码

class Solution {
private:
    vector<vector<int>> neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};

public:
    int slidingPuzzle(vector<vector<int>>& board) {
        // 枚举 status 通过一次交换操作得到的状态
        auto get = [&](string& status) -> vector<string> {
            vector<string> ret;
            int x = status.find('0');
            for (int y: neighbors[x]) {
                swap(status[x], status[y]);
                ret.push_back(status);
                swap(status[x], status[y]);
            }
            return ret;
        };

        string initial;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 3; ++j) {
                initial += char(board[i][j] + '0');
            }
        }
        if (initial == "123450") {
            return 0;
        }

        queue<pair<string, int>> q;
        q.emplace(initial, 0);
        unordered_set<string> seen = {initial};

        while (!q.empty()) {
            auto [status, step] = q.front();
            q.pop();
            for (auto&& next_status: get(status)) {
                if (!seen.count(next_status)) {
                    if (next_status == "123450") {
                        return step + 1;
                    }
                    q.emplace(next_status, step + 1);
                    seen.insert(move(next_status));
                }
            }
        }

        return -1;
    }
};
复制代码