
### Problem Statement

###### You are given an n x n integer matrix board where the cells are labeled from 1 to n&sup2; in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

###### You start on square 1 of the board. In each move, starting from square curr, do the following:

- **Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n&sup2;)].**
  - ###### This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
- **If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.**
- **The game ends when you reach the square n&sup2;.**

###### A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n&sup2; do not have a snake or ladder.

###### Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

###### For example, suppose the board is [ [-1,4],[-1,3] ], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

###### Return the least number of moves required to reach the square n&sup2;. If it is not possible to reach the square, return -1.

**INPUT**

- board = **[ [-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1] ]**

**OUTPUT**

- **4**

![Snakes and Ladder](https://assets.leetcode.com/uploads/2018/09/23/snakes.png)

**EXPLANATION**

- In the beginning, you start at square 1 (at row 5, column 0).
- You decide to move to square 2 and must take the ladder to square 15.
- You then decide to move to square 17 and must take the snake to square 13.
- You then decide to move to square 14 and must take the ladder to square 35.
- You then decide to move to square 36, ending the game.
  This is the lowest possible number of moves to reach the last square, so return 4.

**Steps To Solve**

- Think of solution without code

  - The problem reduces to finding the shortest path in a graph.
  - Every vertex of the graph has an edge to next six vertices if next 6 vertices do not have a snake or ladder.
  - If any of the next six vertices has a snake or ladder, then the edge from current vertex goes to the top of the ladder or tail of the snake.
  - Since all edges are of equal weight, we can efficiently find shortest path using Breadth First Search of the graph.
  - Our first step will be to convert the board into a 1D array and then apply BFS.

```js
/**
 * @param {number[][]} board
 * @return {number}
 */
var snakesAndLadders = function (board) {
  let flatten = [];
  let n = board.length;
  flat(board);

  let seen = new Set(); //check visited

  //if its ladder we go to that index
  let start = flatten[0] === -1 ? 0 : flatten[0] - 1;

  let des = n * n - 1;

  let queue = [start];
  let steps = 0;

  while (queue.length) {
    let len = queue.length;

    for (let i = 0; i < len; i++) {
      let data = queue.shift();

      if (data === des) return steps;

      if (seen.has(data)) continue;

      seen.add(data);

      //check for min length
      let maxLength = Math.min(des, data + 6);

      for (let j = data + 1; j <= maxLength; j++) {
        let val = flatten[j] === -1 ? j : flatten[j] - 1;

        if (!seen.has(val)) {
          queue.push(val);
        }
      }
    }

    steps++;
  }

  return -1;

  function flat(board) {
    let flag = false;

    for (let i = board.length - 1; i >= 0; i--) {
      if (!flag) {
        flatten.push(...board[i]);
      } else {
        let reverse = board[i].reverse();
        flatten.push(...reverse);
      }

      flag = flag ? false : true;
    }
  }
};
```

###### Time and Space Complexity

Time Complexity is **O(N\*N)** where N = board.length .
Space complexity in this case is **O(1)**.
