Sliding Puzzle using BFS

Question

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

Answer 1

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