1
class Solution {
2
 public:
3
  int snakesAndLadders(vector<vector<int>> &board) {
4
    unordered_map<int, int> mp;
5
    int n = board.size();
6
    for (int i = n - 1; i >= 0; i--) {
7
      for (int j = 0; j < n; j++) {
8
        if (board[i][j] != -1) {
9
          int val;
10
          if ((n - i) % 2 != 0)
11
            val = (n - i - 1) * n + j + 1;
12
          else
13
            val = (n - i - 1) * n + n - j;
14
          mp[val] = board[i][j];
15
        }
16
      }
17
    }
18
    queue<pair<int, int>> q;
19
    vector<int> visited(n * n + 1, false);
20
    q.push({1, 0});
21
    while (!q.empty()) {
22
      int node = q.front().first;
23
      int moves = q.front().second;
24
      q.pop();
25
      if (node == n * n) return moves;
26
      if (visited[node]) continue;
27
      visited[node] = true;
28
      for (int k = 1; k <= 6; k++) {
29
        if (node + k > n * n) continue;
30
        int x = node + k;
31
        if (mp.find(x) != mp.end()) x = mp[x];
32
        q.push({x, moves + 1});
33
      }
34
    }
35
    return -1;
36
  }
37
};