I am working on Leetcode problem 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;
    }
};

if I keep option1 remove option2 it works,

however when I keep option2 remove option1 it doesn't work!

But these two code block should work the same. I have been trying to figure it out for a couple of hours. So frustrated and no clue

CodePudding user response：

The purpose of option1 and option2 is to generate a new valid board state. In your option1, you follow the following states:

• copy the current board state into a new temporary board instance (e.g., cand vector)
• move the empty tile towards dir
• skip the following step if you already visited the new state before
• insert the new state into the queue

It works perfectly fine, except the memory utilization. That's why you probably tried doing the moves in-place (e.g., in your option2). The steps of your option2 is like this:

• move the empty tile towards dir
• skip the following steps if you already visited the new state before <-- this is where you made the mistake
• insert the new state into the queue
• move back the empty tile to it's original location

You made the mistake in your 2nd step, as you do not undo the change if a newly generated state is already visited. Please check the following code, it will solve your problem:

// 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]);       

CodePudding user response：

The Bug is in here if (visited.count(t)) continue; basically, when visited.count(t) is true you will not undo the swap.