317. Shortest Distance from All Buildings

BFS - O(kmn) - O(mn)

Mistakes

1. what if a building is not reachable
2. don't forget you can't pass a building either, e.g. [[1,0,1,0,1]] => -1

=> using another matrix called reach, to remember how many times one 0 position updated

public class Solution {
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;

        int n = grid.length;
        int m = grid[0].length;

        int[][] dist = new int[n][m];
        int[][] reach = new int[n][m];
        int count = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    count++;
                    //do bfs and update the value of 0 position in dist matrix
                    bfsHelper(grid, dist, reach, i, j);
                }
            }
        }

        int result = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 0 && reach[i][j] == count && dist[i][j] > 0) {
                    result = (result == -1) ? dist[i][j] : Math.min(result, dist[i][j]);

                }
            }
        }

        return result;
    }

    private void bfsHelper(int[][] grid, int[][] dist, int[][] reach, int i, int j) {
        int n = grid.length;
        int m = grid[0].length;

        boolean[][] visited = new boolean[n][m];
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(i * m + j);
        visited[i][j] = true;

        int distance = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            distance++;

            for (int k = 0; k < size; ++k) {
                int pos = queue.poll();
                int x = pos / m;
                int y = pos % m;

                //up
                if (x - 1 >= 0 && grid[x - 1][y] == 0 && !visited[x - 1][y]) {
                    dist[x - 1][y] += distance;
                    visited[x - 1][y] = true;
                    reach[x - 1][y] += 1;
                    queue.offer((x - 1) * m + y);
                }

                //down
                if (x + 1 < n && grid[x + 1][y] == 0 && !visited[x + 1][y]) {
                    dist[x + 1][y] += distance;
                    visited[x + 1][y] = true;
                    reach[x + 1][y] += 1;
                    queue.offer((x + 1) * m + y);
                }

                //left
                if (y - 1 >= 0 && grid[x][y - 1] == 0 && !visited[x][y - 1]) {
                    dist[x][y - 1] += distance;
                    visited[x][y - 1] = true;
                    reach[x][y - 1] += 1;
                    queue.offer(x * m + y - 1);
                }

                //right
                if (y + 1 < m && grid[x][y + 1] == 0 && !visited[x][y + 1]) {
                    dist[x][y + 1] += distance;
                    visited[x][y + 1] = true;
                    reach[x][y + 1] += 1;
                    queue.offer(x * m + y + 1);
                }
            }
        }
    }
}

Version II - get rid of visited matrix

https://discuss.leetcode.com/topic/32391/share-a-java-implement

• use one for loop first to remember all buildings position, and then change 1 or 2 to a negative number
• loop through all buildings and update positive positions