Untitled
unknown
plain_text
2 years ago
2.2 kB
5
Indexable
import java.util.LinkedList; import java.util.Queue; public class ShortestPathWithBattery { static class Point { int x, y, battery; public Point(int x, int y, int battery) { this.x = x; this.y = y; this.battery = battery; } } public static int shortestPathWithBattery(int[][] matrix, int startX, int startY, int endX, int endY) { int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1}; int n = matrix.length; boolean[][][] visited = new boolean[n][n][n * n]; // [x][y][battery] Queue<Point> queue = new LinkedList<>(); queue.offer(new Point(startX, startY, 0)); visited[startX][startY][0] = true; while (!queue.isEmpty()) { Point current = queue.poll(); if (current.x == endX && current.y == endY) { return current.battery; } for (int i = 0; i < 4; i++) { int newX = current.x + dx[i]; int newY = current.y + dy[i]; if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] != 1) { int newBattery = current.battery - 1; if (matrix[newX][newY] > 1) { // Charging station newBattery = n * n; } if (newBattery >= 0 && !visited[newX][newY][newBattery]) { queue.offer(new Point(newX, newY, newBattery)); visited[newX][newY][newBattery] = true; } } } } return -1; // No path found } public static void main(String[] args) { int[][] matrix = { {0, 1, 0, 0, 2}, {0, 0, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 1, 0} }; int startX = 0; int startY = 0; int endX = 3; int endY = 3; int shortestBattery = shortestPathWithBattery(matrix, startX, startY, endX, endY); System.out.println("Shortest path with battery: " + shortestBattery); } }
Editor is loading...