BFS solution with a distance map


  • 0
    B
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        int[][] dis = new int[m][n];
        boolean[][] noreach = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    bfs(dis, grid, noreach, i, j);
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && !noreach[i][j]) res = Math.min(res, dis[i][j]);
            }
        }
        return res == Integer.MAX_VALUE ? -1: res;
    }
    public void bfs(int[][] dis, int[][] grid, boolean[][] noreach, int i, int j) {
        boolean[][] visit = new boolean[grid.length][grid[0].length];
        pair p = new pair(i, j);
        Queue<pair> q = new LinkedList<pair>();
        q.add(p);
        int value = -1;
        while (!q.isEmpty()) {
            value++;
            int size = q.size();
            for (int k = 0; k < size; k++) {
                p = q.remove();
                int x = p.x;
                int y = p.y;
                dis[x][y] += value;
                if (x-1 >=0 && grid[x-1][y] == 0 && !visit[x-1][y]) {
                    visit[x-1][y] = true;
                    q.add(new pair(x-1, y));
                }
                if (x+1 < grid.length && grid[x+1][y] == 0 && !visit[x+1][y]) {
                    visit[x+1][y] = true;
                    q.add(new pair(x+1, y));
                }
                if (y-1 >=0 && grid[x][y-1] == 0 && !visit[x][y-1]) {
                    visit[x][y-1] = true;
                    q.add(new pair(x, y-1));
                }
                if (y+1 < grid[0].length && grid[x][y+1] == 0 && !visit[x][y+1]) {
                    visit[x][y+1] = true;
                    q.add(new pair(x, y+1));
                }
            }
        }
        for (int x = 0; x < grid.length; x++) {
            for (int y = 0; y < grid[0].length; y++) {
                if (!visit[x][y] && grid[x][y] == 0) noreach[x][y] = true;
            }
        }
    }
    public class pair{
        int x;
        int y;
        public pair(int i, int j) {
            x = i;
            y = j;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.