Snakes and Ladders: The Quickest Way Up

  • + 0 comments

    Java solution:

    public static int quickestWayUp(
        List<List<Integer>> ladders, List<List<Integer>> snakes) {
      int[] board = new int[101];
    
      for (int i = 0; i < 101; i++) {
        board[i] = i;
      }
    
      for (List<Integer> ladder : ladders) {
        board[ladder.get(0)] = ladder.get(1);
      }
    
      for (List<Integer> snake : snakes) {
        board[snake.get(0)] = snake.get(1);
      }
    
      Queue<int[]> queue = new LinkedList<>();
      boolean[] visited = new boolean[101];
      queue.offer(new int[] {1, 0});
    
      while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int currentSquare = current[0];
        int currentMove = current[1];
        
        if (currentSquare == 100) {
          return currentMove;
        }
    
        for (int i = currentSquare + 1; i <= currentSquare + 6; i++) {
          if (i <= 100 && !visited[board[i]]) {
            visited[i] = true;
            visited[board[i]] = true;
            queue.offer(new int[] {board[i], currentMove + 1});
            
          }
        }
      }
      return -1;
    }