Untitled
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...