Princess - NDDCoder

Fork

Mê cung là ma trận NxN (N <= 200). Trong một ô có một trong 3 giá trị sau:
 - 0 nếu ô đó có bẫy
 - 1 nếu ô đó an toàn
 - 2 nếu ô đó có công chúa
Duy nhất chỉ có 1 ô có giá trị 2, là nơi công chúa đang bị giam giữ.
Hoàng tử đang ở ô (0, 0). Lối thoát ở ô (N-1, N-1). Hoàng tử không được di chuyển vào các ô có cạm bẫy và chỉ có thể di chuyển từ ô này sang ô khác nếu 2 ô có chung cạnh.
Hãy giúp hoàng tử tìm đường đi ngắn nhất để giải cứu công chúa.
Ví dụ:
1 0 1 1 0
1 0 0 0 0
1 1 2 1 1
1 1 1 0 1
1 0 1 0 1
Cần ít nhất 8 bước để cứu công chúa ra khỏi mê cung và in ra 8.

1 0 1 1 0
1 0 0 0 0 
1 1 2 1 1
1 1 0 0 0 
1 1 1 1 1
Cần ít nhất 10 bước để cứu công chúa. 4 bước đi từ ô (0, 0) đến ô có công chúa (2, 2) và 6 bước từ công chúa đến ô cuối cùng (4, 4). In ra 10

1 1 0 2 1 1
0 1 0 1 0 1
0 1 0 1 0 1
0 0 0 1 0 1
0 0 0 1 0 1
1 1 1 1 0 1
Không có đường đi in ra -1.

Input: dòng đầu tiên ghi số lượng test case t (t <= 10).
Các dòng tiếp theo lần lượt đưa ra các test case từ 1 đến t.
Mỗi test case gồm:
    - dòng đầu là số N (N <= 200)
    - N dòng tiếp theo là ma trận NxN mô tả mê cung.
Output: gồm t dòng, mỗi dòng tương ứng với output của mỗi test case: in ra số bước ít cách giải cứu nhất. Nếu không tồn tại in ra -1.

input:
2
5
1 0 1 1 0
1 0 0 0 0
1 1 2 1 1
1 1 1 0 1
1 0 1 0 1
6
1 1 0 2 1 1
0 1 0 1 0 1
0 1 0 1 0 1
0 0 0 1 0 1
0 0 0 1 0 1
1 1 1 1 0 1
output:
8
-1

import java.util.Scanner;

public class RescuePrincess {
    static int[][] maze = new int[201][201];
    static int[][] dist = new int[201][201];
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int N;

static boolean inBounds(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }

static int bfs(int sx, int sy, int ex, int ey) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dist[i][j] = -1;
            }
        }

int[][] queue = new int[N * N][2];
        int front = 0, rear = 0;
        queue[rear][0] = sx;
        queue[rear][1] = sy;
        dist[sx][sy] = 0;
        rear++;

while (front < rear) {
            int x = queue[front][0];
            int y = queue[front][1];
            front++;

for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (inBounds(nx, ny) && maze[nx][ny] != 0 && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    queue[rear][0] = nx;
                    queue[rear][1] = ny;
                    rear++;
                }
            }
        }
        return dist[ex][ey];
    }

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int test = 0; test < t; test++) {
            N = sc.nextInt();
            int princessX = -1, princessY = -1;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    maze[i][j] = sc.nextInt();
                    if (maze[i][j] == 2) {
                        princessX = i;
                        princessY = j;
                        maze[i][j] = 1; // biến ô chứa công chúa thành 1 để có thể đi vào được
                    }
                }
            }

int d1 = bfs(0, 0, princessX, princessY);
            int d2 = bfs(princessX, princessY, N - 1, N - 1);

if (d1 == -1 || d2 == -1) System.out.println(-1);
            else System.out.println(d1 + d2);
        }
    }
}