Untitled

unknown
plain_text
5 months ago
3.6 kB
1
Indexable
Never
```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) {
}
}
}
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.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.```