Snakes and Ladders

1package pkg5leetcode.interview150;2 3/** LC 909 Snakes and Ladders */4import java.util.*;5 6public class interview150_LC909SnakesAndLadders {7  static int snakesAndLadders(int[][] board) {8    int n = board.length, target = n * n;9    int[] dist = new int[target + 1];10    Arrays.fill(dist, -1);11    Queue<Integer> q = new ArrayDeque<>();12    dist[1] = 0; q.add(1);13    while (!q.isEmpty()) {14      int cur = q.poll();15      if (cur == target) return dist[cur];16      for (int next = cur + 1; next <= Math.min(cur + 6, target); next++) {17        int[] rc = idx(next, n);18        int dest = board[rc[0]][rc[1]] > 0 ? board[rc[0]][rc[1]] : next;19        if (dist[dest] == -1) { dist[dest] = dist[cur] + 1; q.add(dest); }20      }21    }22    return -1;23  }24 25  static int[] idx(int sq, int n) {26    int r = (sq - 1) / n, c = (sq - 1) % n;27    if (r % 2 == 1) c = n - 1 - c;28    return new int[]{n - 1 - r, c};29  }30 31  public static void main(String[] args) {32    int[][] b = {{-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}};33    System.out.println(snakesAndLadders(b));34  }35}