Untitled

 avatar
unknown
plain_text
2 years ago
3.6 kB
5
Indexable
Here is an example of how you could write the code for this problem using Java, BFS algorithm and backtracking:

```java
import java.util.*;

class Main {
    static int[][] room;
    static int n, m;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static List<int[]> dirtyTiles = new ArrayList<>();
    static int minMoves = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 1; i <= t; i++) {
            n = sc.nextInt();
            m = sc.nextInt();
            room = new int[n][m];
            dirtyTiles.clear();
            minMoves = Integer.MAX_VALUE;
            int robotX = -1;
            int robotY = -1;
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    room[j][k] = sc.nextInt();
                    if (room[j][k] == 3) {
                        robotX = j;
                        robotY = k;
                    } else if (room[j][k] == 1) {
                        dirtyTiles.add(new int[]{j, k});
                    }
                }
            }
            bfs(robotX, robotY);
            System.out.println("Case #" + i);
            System.out.println(minMoves == Integer.MAX_VALUE ? -1 : minMoves);
        }
    }

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        boolean[][] visited = new boolean[n][m];
        visited[x][y] = true;
        int moves = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] currPos = queue.poll();
                if (room[currPos[0]][currPos[1]] == 1) {
                    room[currPos[0]][currPos[1]] = 0;
                    backtracking(0, moves);
                    room[currPos[0]][currPos[1]] = 1;
                }
                for (int j = 0; j < dx.length; j++) {
                    int newX = currPos[0] + dx[j];
                    int newY = currPos[1] + dy[j];
                    if (newX >= 0 && newX < n && newY >= 0 && newY < m && !visited[newX][newY] && room[newX][newY] != 2) {
                        visited[newX][newY] = true;
                        queue.offer(new int[]{newX, newY});
                    }
                }
            }
            moves++;
        }
    }

    public static void backtracking(int index, int moves) {
        if (index == dirtyTiles.size()) {
            minMoves = Math.min(minMoves, moves);
            return;
        }
        for (int i = index; i < dirtyTiles.size(); i++) {
            int[] currTile = dirtyTiles.get(i);
            swap(dirtyTiles, index, i);
            bfs(currTile[0], currTile[1]);
            swap(dirtyTiles, index, i);
        }
    }

    public static void swap(List<int[]> list, int i, int j) {
        int[] temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }
}
```

This code uses a BFS algorithm to find the minimum number of moves to reach each dirty tile and a backtracking algorithm to find the optimal order to visit all dirty tiles. The `bfs` method takes the current position of the robot and finds the minimum number of moves to reach each dirty tile. The `backtracking` method tries all possible orders of visiting the dirty tiles and updates the minimum number of moves.

I hope this helps! Let me know if you have any questions or need further clarification.
Editor is loading...