1
class Node {
2
 public:
3
  int row;
4
  int col;
5
  vector<vector<int>> state;
6
};
7

8
class Solution {
9
 public:
10
  int slidingPuzzle(vector<vector<int>> &board) {
11
    vector<vector<int>> target = {{1, 2, 3}, {4, 5, 0}};
12
    queue<Node> q;
13
    int n = 2;
14
    int m = 3;
15
    vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
16

17
    for (int i = 0; i < board.size(); i++)
18
      for (int j = 0; j < board[0].size(); j++) {
19
        if (board[i][j] == 0) {
20
          q.push({i, j, board});
21
          break;
22
        }
23
      }
24

25
    set<vector<vector<int>>> set;
26
    set.insert(q.front().state);
27
    int ladder = 0;
28
    while (!q.empty()) {
29
      int size = q.size();
30
      for (int i = 0; i < size; i++) {
31
        Node curr = q.front();
32
        q.pop();
33
        if (curr.state == target) return ladder;
34

35
        int row = curr.row;
36
        int col = curr.col;
37
        for (auto &x : dir) {
38
          int r = x[0] + row;
39
          int c = x[1] + col;
40

41
          if (r < n && r >= 0 && c < m && c >= 0) {
42
            swap(curr.state[r][c], curr.state[row][col]);
43
            if (set.find(curr.state) == set.end()) {
44
              set.insert(curr.state);
45
              q.push({r, c, curr.state});
46
            }
47
            swap(curr.state[r][c], curr.state[row][col]);
48
          }
49
        }
50
      }
51
      ladder++;
52
    }
53
    return -1;
54
  }
55
};