Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.9 kB
1
Indexable
Never
import java.util.Scanner;

public class CleaningRobot {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        for (int t = 1; t <= T; t++) {
            System.out.println("Case #" + t);
            int N = scanner.nextInt();
            int M = scanner.nextInt();

            int[][] room = new int[N][M];
            int startX = 0, startY = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    room[i][j] = scanner.nextInt();
                    if (room[i][j] == 3) {
                        startX = i;
                        startY = j;
                    }
                }
            }

            int result = cleanRoom(room, startX, startY, 0);

            System.out.println(result == Integer.MAX_VALUE ? -1 : result);
        }
    }

    private static int cleanRoom(int[][] room, int x, int y, int dirtyCount) {
        if (x < 0 || x >= room.length || y < 0 || y >= room[0].length || room[x][y] == 2) {
            return Integer.MAX_VALUE;
        }

        if (dirtyCount == 0) {
            return 0;
        }

        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        int minMoves = Integer.MAX_VALUE;

        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX >= 0 && newX < room.length && newY >= 0 && newY < room[0].length && room[newX][newY] == 1) {
                room[newX][newY] = 0;
                int moves = cleanRoom(room, newX, newY, dirtyCount - 1);
                room[newX][newY] = 1;

                if (moves != Integer.MAX_VALUE) {
                    minMoves = Math.min(minMoves, 1 + moves);
                }
            }
        }

        return minMoves;
    }
}