Shortest Distance from All Buildings

Given a 2D grid, each cell is either a wall 2, an house 1 or empty 0 (the number zero, one, two), find a place to build a post office so that the sum of the distance from the post office to all the houses is smallest.

Return the smallest sum of distance. Return -1 if it is not possible.

BFS

Time Complexity

思路

First, we need to clarify if it must has a place that can access to every house in matrix.

If it is not, we can improve our code by checking after each BFS, if there is still 0 in the grid and still hasn't visited, if there is, it means these 0 can't be the post office. Then we can turn these 0 into 2 as walls. So we don't need to count these 0 into cost any more.

Put all 1 into queue do BFS. We need to keep a global matrix called cost and add the distance from each 1 by doing BFS.

Each 1 need a new matrix for checking visited but we can keep only one matrix here to save space.

At last, checking cost matrix to find the min distance.

代码

public int shortestDistance(int[][] grid) {    // Write your code here    //corner case    if(grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;        int rows = grid.length, cols = grid[0].length;    int[][] directions = new int[][]{
   {-1,0},{1,0},{0,1},{0,-1}};    int[][] cost = new int[rows][cols];        for(int i = 0; i < rows; i++){        for(int j = 0; j < cols; j++){            if(grid[i][j] == 1){                bfs(grid, cost, i, j, rows, cols, directions);            }        }    }        int minDis = Integer.MAX_VALUE;    for(int i = 0; i < rows; i++){        for(int j = 0; j < cols; j++){            if(grid[i][j] == 0 && cost[i][j] != 0){                minDis = Math.min(cost[i][j], minDis);            }        }    }    return minDis == Integer.MAX_VALUE ? -1 : minDis;}        private void bfs(int[][] grid, int[][] cost, int i, int j, int rows, int cols, int[][] directions){        Queue
    
      queue = new LinkedList
     
      ();        queue.offer(new int[]{i, j});        boolean[][] visited = new boolean[rows][cols];        visited[i][j] = true;        int distance = 1;                while(!queue.isEmpty()){            int size = queue.size();            for(int k = 0; k < size; k++){                int[] cur = queue.poll();                for(int[] dir : directions){                    int x = cur[0] + dir[0];                    int y = cur[1] + dir[1];                                        if(x >= 0 && x < rows && y >= 0 && y < cols && visited[x][y] == false && grid[x][y] == 0){                            queue.offer(new int[]{x, y});                            visited[x][y] = true;                            cost[x][y] += distance;                    }                }            }            distance ++;        }                for(int r = 0; r < rows; r++){            for(int c = 0; c < cols; c++){                if(grid[r][c] == 0 && visited[r][c] == false){                    grid[r][c] = 2;                }            }        }    }