Dijkstra.java

import java.util.PriorityQueue;

public class Dijkstra {
    static final int ROWS = 20;
    static final int COLS = 20;
    static final int INF = 99999;

    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, -1, 1};

    boolean[][] path;
    boolean[][] visited;

    public boolean[][] run(int[][] cells, int startR, int startC, int endR, int endC) {
        int[][] dist  = new int[ROWS][COLS];
        int[][] prevR = new int[ROWS][COLS];
        int[][] prevC = new int[ROWS][COLS];
        boolean[][] vis = new boolean[ROWS][COLS];
        path    = new boolean[ROWS][COLS];
        visited = new boolean[ROWS][COLS];

        for (int i = 0; i < ROWS; i++)
            for (int j = 0; j < COLS; j++) {
                dist[i][j]  = INF;
                prevR[i][j] = prevC[i][j] = -1;
            }

        dist[startR][startC] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, startR, startC});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], r = curr[1], c = curr[2];

            if (vis[r][c]) continue;
            vis[r][c] = true;
            visited[r][c] = true;

            if (r == endR && c == endC) break;

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nc >= 0 && nr < ROWS && nc < COLS
                        && !vis[nr][nc] && cells[nr][nc] != 1) {
                    if (d + 1 < dist[nr][nc]) {
                        dist[nr][nc] = d + 1;
                        prevR[nr][nc] = r;
                        prevC[nr][nc] = c;
                        pq.offer(new int[]{d + 1, nr, nc});
                    }
                }
            }
        }

        if (prevR[endR][endC] == -1 && !(endR == startR && endC == startC)) 
            return null; // no path

        int r = endR, c = endC;
        while (r != -1 && c != -1) {
            path[r][c] = true;
            int pr = prevR[r][c];
            int pc = prevC[r][c];
            r = pr; c = pc;
        }

        return path;
    }
}