使用 BFS 的滑动拼图

Question

我正在研究 Leetcode 问题 https://leetcode.com/problems/sliding-puzzle/

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int res = 0;
        set<vector<vector<int>>> visited;
        queue<pair<vector<vector<int>>, vector<int>>> q;
        vector<vector<int>> correct{{1, 2, 3}, {4, 5, 0}};
        vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) q.push({board, {i, j}});
            }
        }
        while (!q.empty()) {
            for (int i = q.size() - 1; i >= 0; --i) {
                vector<vector<int>> t = q.front().first; 
                auto zero = q.front().second; q.pop();
 
                if (t == correct) return res;
                visited.insert(t);
                for (auto dir : dirs) 
                {
                    int x = zero[0] + dir[0], y = zero[1] + dir[1];
                    if (x < 0 || x >= 2 || y < 0 || y >= 3) continue;
                    
                    /* option1 
                    vector<vector<int>> cand = t;
                    swap(cand[zero[0]][zero[1]], cand[x][y]);
                    if (visited.count(cand)) continue;
                    q.push({cand, {x, y}});
                    */


                    /* option2
                    swap(t[zero[0]][zero[1]], t[x][y]);  
                     if (visited.count(t)) continue;
                    q.push({t, {x, y}});
                     swap(t[zero[0]][zero[1]], t[x][y]);
                    */        
                }
            }
            ++res;
        }
        return -1;
    }
};

如果我保留 option1 删除 option2 它有效，

但是当我保留 option2 删除 option1 它不起作用！

但这两个代码块应该是一样的。几个小时以来，我一直在努力弄明白。很沮丧，没有头绪

Answer 1

option1 和 option2 的目的是生成新的有效板状态。在您的 option1 中，您遵循以下状态：

将当前棋盘状态复制到新的临时棋盘实例中（例如，cand向量）
将空方格移向 dir
如果您之前已经访问过新状态，请跳过以下步骤
将新状态插入队列

它工作得很好，除了内存利用率。这就是为什么您可能尝试就地进行移动（例如，在您的 option2 中）。你的option2的步骤是这样的：

将空方格移向 dir
如果您之前已经访问过新状态，请跳过以下步骤<-- 这是您犯错的地方
将新状态插入队列
将空方块移回原来的位置

您在第 2 步中犯了错误，因为如果已经访问了新生成的状态，您没有撤消更改。请检查以下代码，它将解决您的问题：

// option2
swap(t[zero[0]][zero[1]], t[x][y]);  
if (!visited.count(t)) q.push({t, {x, y}});
swap(t[zero[0]][zero[1]], t[x][y]);

Answer 2

Bug 在这里 if (visited.count(t)) continue; 基本上，当 visited.count(t) is true 你不会撤消交换。

使用 BFS 的滑动拼图

Sliding Puzzle using BFS

algorithm

swap

vector

breadth-first-search