Untitled

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);
    }
}