1
class Solution {
2
  // what if we have changed the dice number, or changing the starting index or changing the ending
3
  // index
4
  // so i have covered all possible ways in which this question can be asked
5

6
  // bfs tip:- for better bfs, we can use marking first and then inserting it in the queue which
7
  // works faster then removing first and then checking
8
  public int[] getans(int dice, HashMap<Integer, Integer> map, int si, int ei) {
9
    // if si==ei just directly return
10
    if (si == ei) return new int[] {0, 0, 0};
11
    LinkedList<int[]> que = new LinkedList<>();
12
    que.addLast(new int[] {si, 0, 0});
13
    int level = 0;
14
    // to stop visiting cells again
15
    boolean[] vis = new boolean[ei + 1];
16
    vis[si] = true;
17
    // starting bfs
18
    while (que.size() != 0) {
19
      int size = que.size();
20
      while (size-- > 0) {
21
        int[] rem = que.removeFirst();
22
        int idx = rem[0];
23
        int lad = rem[1];
24
        int sna = rem[2];
25
        for (int i = 1; i <= dice; i++) {
26
          int x = i + rem[0]; // checking all the steps
27
          if (x <= ei) { // valid points
28
            if (map.containsKey(x)) { // this means that we have encountered a snake or a ladder
29
              if (map.containsKey(x)) {
30
                int val = map.get(x);
31
                if (val == ei) return new int[] {level + 1, lad + 1, sna};
32
                if (!vis[val]) {
33
                  vis[val] = true;
34
                  // if val>x this means we have a ladder and if less, then it is a snake
35
                  que.addLast(
36
                      val > x ? new int[] {val, lad + 1, sna} : new int[] {val, lad, sna + 1});
37
                }
38
              }
39
            } else {
40
              // if it is not present in map, then it is a normal cell, so just insert it directly
41
              if (x == ei) return new int[] {level + 1, lad, sna};
42
              if (!vis[x]) {
43
                vis[x] = true;
44
                que.addLast(new int[] {x, lad, sna});
45
              }
46
            }
47
          }
48
        }
49
      }
50
      level++;
51
    }
52
    return new int[] {-1, 0, 0};
53
  }
54

55
  public int snakesAndLadders(int[][] board) {
56
    HashMap<Integer, Integer> map = new HashMap<>();
57
    int count = 1;
58
    int n = board.length;
59
    boolean flag = true;
60
    // traversing the board in the board game fashion and checking if the count that is representing
61
    // the cell number, if we encounter something other then -1, then it can be a snake or it can be
62
    // a ladder and mapping that cell index (i.e count to that number)
63
    for (int i = n - 1; i >= 0; i--) {
64
      // traversing in the order of the board
65
      if (flag) {
66
        for (int j = 0; j < n; j++) {
67
          if (board[i][j] != -1) {
68
            map.put(count, board[i][j]);
69
          }
70
          count++;
71
          flag = false;
72
        }
73
      } else {
74
        // reversing the direction
75
        for (int j = n - 1; j >= 0; j--) {
76
          if (board[i][j] != -1) {
77
            map.put(count, board[i][j]);
78
          }
79
          flag = true;
80
          count++;
81
        }
82
      }
83
    }
84
    // if snake on destination then just return -1;
85
    if (board[0][0] != -1) return -1;
86
    // we only want the minimum steps, but for more conceptual approach for this question, {minm
87
    // steps,ladders used, snakes used}
88
    int[] ans = getans(6, map, 1, n * n);
89
    ;
90
    return ans[0];
91
  }
92
}