LeetCode(909) -- Snakes and Ladders

Problem

Solution

BFS

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 0);
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        
        while (!queue.isEmpty()) {
            int s = queue.remove();
            if (s == n * n) {
                return map.get(s);
            }
            for (int s2 = s + 1; s2 <= Math.min(s + 6, n * n); s2++) {
                int rc = get(s2, n);
                int r = rc / n, c = rc % n;
                int s2Final = board[r][c] == -1 ? s2 : board[r][c];
                if (!map.containsKey(s2Final)) {
                    map.put(s2Final, map.get(s) + 1);
                    queue.add(s2Final);
                }
            }
        }
        return -1;
    }
    
    private int get(int s, int n) {
        int quotient = (s - 1) / n;
        int remainder = (s - 1) % n;
        int row = n - 1 - quotient;
        int col = row % 2 != n % 2 ? remainder : n - 1 - remainder;
        return row * n + col;
    }
}