Untitled

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 caseNum = 1; caseNum <= T; caseNum++) {
            int N = scanner.nextInt();
            int M = scanner.nextInt();
            int[][] room = new int[N][M];

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

            int result = minMovesToClean(N, M, room);

            System.out.println("Case #" + caseNum);
            System.out.println(result);
        }

        scanner.close();
    }

    private static int minMovesToClean(int N, int M, int[][] room) {
        int[][] dirtyTiles = new int[N * M][2];
        int dirtyCount = 0;
        int[] robotPos = new int[2];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (room[i][j] == 1) {
                    dirtyTiles[dirtyCount][0] = i;
                    dirtyTiles[dirtyCount][1] = j;
                    dirtyCount++;
                } else if (room[i][j] == 3) {
                    robotPos[0] = i;
                    robotPos[1] = j;
                }
            }
        }

        return backtracking(robotPos[0], robotPos[1], 0, dirtyCount, room, dirtyTiles);
    }

    private static int backtracking(int x, int y, int cleanedTiles, int dirtyCount, int[][] room, int[][] dirtyTiles) {
        if (cleanedTiles == dirtyCount) {
            return 0;
        }

        int minMoves = Integer.MAX_VALUE;

        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        for (int[] dir : directions) {
            int nx = x + dir[0];
            int ny = y + dir[1];

            if (isValidMove(nx, ny, room)) {
                int originalValue = room[nx][ny];
                room[nx][ny] = 3; // Move the robot
                int moves = backtracking(nx, ny, cleanedTiles + 1, dirtyCount, room, dirtyTiles);
                room[nx][ny] = originalValue; // Backtrack
                if (moves != -1) {
                    minMoves = Math.min(minMoves, 1 + moves);
                }
            }
        }

        return (minMoves == Integer.MAX_VALUE) ? -1 : minMoves;
    }

    private static boolean isValidMove(int x, int y, int[][] room) {
        return x >= 0 && x < room.length && y >= 0 && y < room[0].length && room[x][y] != 2;
    }
}