Snakes and Ladders

요구사항 정리

보드의 왼쪽 하단(예 : )에서 시작하여 각 행의 방향을 번갈아 가며 셀에 Boustrophedon 스타일 로 레이블 이 지정된 n x n정수 행렬이 제공됩니다 .board1n2board[n - 1][0]

1당신은 보드의 사각형에서 시작합니다 . 각 이동에서 square부터 시작하여 curr다음을 수행합니다.

next범위 내 라벨이 있는 대상 사각형을 선택합니다 . [curr + 1, min(curr + 6, n2)]
이 선택은 표준 6면 주사위 굴림 의 결과를 시뮬레이션합니다 . 즉, 보드 크기에 관계없이 항상 최대 6개의 목적지가 있습니다.
next뱀이나 사다리가 있으면 해당 뱀이나 사다리가 있는 곳으로 이동 해야 합니다 . 그렇지 않으면 으로 이동합니다 next.
광장에 도달하면 게임이 종료됩니다 .n2
r행 과 열의 보드 사각형에는 c뱀이나 사다리가 있습니다 board[r][c] != -1. 그 뱀이나 사다리의 목적지는 입니다 board[r][c]. 사각형 1이며 뱀이나 사다리가 없습니다.n2

이동당 최대 한 번만 뱀이나 사다리를 가져갈 수 있습니다. 뱀이나 사다리의 목적지가 다른 뱀이나 사다리의 시작인 경우 다음 뱀이나 사다리를 따라가지 않습니다 .

예를 들어, 보드가 이고 [[-1,4],[-1,3]]첫 번째 이동 시 목적지 사각형이 이라고 가정합니다 2. 당신은 사각형으로 사다리를 따라가지만 3, 다음 사다리를 따라가지는 않습니다4 .
정사각형에 도달하는 데 필요한 최소 이동 횟수를 반환합니다 . 광장에 도달할 수 없는 경우 를 반환합니다 .n2-1

import java.util.*;

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int target = n * n;

        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(1); // Start from square 1
        visited.add(1);

        int moves = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int square = queue.poll();
                if (square == target) {
                    return moves;
                }

                for (int j = 1; j <= 6; j++) {
                    int nextSquare = square + j;
                    if (nextSquare <= target) {
                        int[] coordinates = getCoordinates(nextSquare, n);
                        int row = coordinates[0];
                        int col = coordinates[1];

                        int destination = board[row][col] == -1 ? nextSquare : board[row][col];

                        if (!visited.contains(destination)) {
                            queue.offer(destination);
                            visited.add(destination);
                        }
                    }
                }
            }
            moves++;
        }

        return -1; // If it's not possible to reach the square n^2
    }

    private int[] getCoordinates(int square, int n) {
        int row = (square - 1) / n;
        int col = (square - 1) % n;
        if (row % 2 == 1) {
            col = n - 1 - col;
        }
        row = n - 1 - row;
        return new int[]{row, col};
    }
}