snakes_and_ladders.md

🔥 100% FAST 🔥 || Simple Fast and Easy || with Explanation

Approach

Initialize the variables n as the size of the board, moves as 0, a queue q and a 2D boolean array visited with all elements as false. Push the value 1 into the queue and mark the element at the last row and first column of the visited array as true. Start a while loop until the queue is not empty. In each iteration, set the size of the queue to a variable size. Run a for loop for i from 0 to size Dequeue the front element of the queue and store it in a variable currBoardVal If currBoardVal is equal to nn, return the value of moves. Run a for loop for diceVal from 1 to 6. If currBoardVal + diceVal is greater than nn, break the loop. Find the coordinates of the element at position currBoardVal + diceVal in the board by calling the findCoordinates function and store it in a vector pos. Set row as the first element of the vector pos and col as the second element of the vector pos. If the element at position row and col in the visited array is false, mark it as true. If the value at the element at position row and col in the board is -1, push currBoardVal + diceVal into the queue. Else, push the value at the element at position row and col in the board into the queue. End the for loop for diceVal. End the for loop for i. Increment the value of moves by 1. End the while loop.

Complexity

Time complexity: O(n^2)

The time complexity of BFS is O(∣V∣+∣E∣), where ∣V∣ is the number of vertices and ∣E∣ is the number of edges. We have ∣V∣=n^2 and ∣E∣<6*n^2 , thus the total time complexity for BFS is O(7n^2)=O(n^2). We also spend some time associating each (row, col) with a label, but this also costs O(n^2), so the overall time complexity is O(n^2).

Space complexity: O(n^2) // we are using visited array of size n*n

import 'dart:collection';

class Solution {
  int snakesAndLadders(List<List<int>> board) {
    int n = board.length;
    int moves = 0;
    Queue<int> q = Queue();
    List<List<bool>> visited =
        List.filled(n, false).map((e) => List.filled(n, false)).toList();
    q.add(1);
    visited[n - 1][0] = true;
    while (q.isNotEmpty) {
      int size = q.length;
      for (int i = 0; i < size; i++) {
        int currBoardVal = q.removeFirst();
        if (currBoardVal == n * n) return moves;
        for (int diceVal = 1; diceVal <= 6; diceVal++) {
          if (currBoardVal + diceVal > n * n) break;
          List<int> pos = findCoordinates(currBoardVal + diceVal, n);
          int row = pos[0];
          int col = pos[1];
          if (visited[row][col] == false) {
            visited[row][col] = true;
            if (board[row][col] == -1) {
              q.add(currBoardVal + diceVal);
            } else {
              q.add(board[row][col]);
            }
          }
        }
      }
      moves++;
    }
    return -1;
  }

  List<int> findCoordinates(int curr, int n) {
    int r = n - (curr - 1) ~/ n - 1;
    int c = (curr - 1) % n;
    if (r % 2 == n % 2) {
      return [r, n - 1 - c];
    } else {
      return [r, c];
    }
  }
}