# Untitled unknown
plain_text
5 months ago
3.6 kB
1
Indexable
Never
```Sure! Here is an example of how I would write a program to solve this problem:

```java
import java.util.*;

class Point {
int x, y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}
}

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

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int tc = 1; tc <= t; tc++) {
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 i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
room[i][j] = sc.nextInt();
if (room[i][j] == 3) {
robotX = i;
robotY = j;
} else if (room[i][j] == 1) {
}
}
}
backtracking(robotX, robotY, 0);
System.out.println("Case #" + tc);
System.out.println(minMoves == Integer.MAX_VALUE ? -1 : minMoves);
}
}

public static void backtracking(int x, int y, int moves) {
if (moves >= minMoves) {
return;
}
if (dirtyTiles.isEmpty()) {
minMoves = Math.min(minMoves, moves);
return;
}
for (int i = 0; i < dirtyTiles.size(); i++) {
Point nextTile = dirtyTiles.remove(i);
int dist = bfs(x, y, nextTile.x, nextTile.y);
if (dist != -1) {
backtracking(nextTile.x, nextTile.y, moves + dist);
}
}
}

public static int bfs(int xS, int yS, int xE, int yE) {
boolean[][] visited = new boolean[n][m];
visited[xS][yS] = true;
int moves = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Point currPos = queue.poll();
if (currPos.x == xE && currPos.y == yE) {
return moves;
}
for (int j = 0; j < dx.length; j++) {
int newX = currPos.x + dx[j];
int newY = currPos.y + dy[j];
if (newX >= 0 && newX < n && newY >= 0 && newY < m && !visited[newX][newY] && room[newX][newY] != 2) {
visited[newX][newY] = true;