11ms simple Java soluton that beats 100% with explanation


  • 0
    T
    public class Solution {
        
        public int shortestDistance(int[][] grid) {
    	     
            int[][] d = new int[grid.length][grid[0].length];//sum of distance from all buildings
            int[][] cc = new int[grid.length][grid[0].length];//reachable by how many buildings
            int count = 0;
            //find how many buildings
            for(int i = 0;i<grid.length;i++){
                for(int j = 0;j<grid[0].length;j++){
                    if(grid[i][j] == 1) {
                        count++;
                    }
                }
            }
            
            for(int i = 0;i<grid.length;i++){
                for(int j = 0;j<grid[0].length;j++){
                    if(grid[i][j] == 1) {
                       //bfs each building, keep on updating empty spot's distance value
                        boolean x = bfs(grid, i, j, d, new boolean[grid.length][grid[0].length], count, cc);
                        if(!x)
                            return -1;//if this building can not reach all other buildings return -1
                    }
                }
            }
    
           //find the smallest distance, need be an empty spot, and a spot can be reached by all buildings
            int res = Integer.MAX_VALUE;
            for(int i = 0;i<grid.length;i++){
                for(int j = 0;j<grid[0].length;j++){
                    if(d[i][j] != 0 && cc[i][j] == count)
                        res = Math.min(res, d[i][j]);
                }
            }
            return res == Integer.MAX_VALUE ? -1 : res ;
        }
        
        //nothing much, just bfs, but updates how many building can an empty spot reach, and 
       //if current building can reach all other buildings, otherwise returns false, solution returns -1
        private boolean bfs(int[][]grid, int i, int j, int[][] d, boolean[][] used, int count, int[][] cc) {
            Queue<Integer> is = new LinkedList<>();
            Queue<Integer> js = new LinkedList<>();
            Queue<Integer> ds = new LinkedList<>();
            is.add(i);
            js.add(j);
            ds.add(0);
            used[i][j] = true;
            int[] xx = new int[]{-1,0,1,0};
            int[] yy = new int[]{0,-1,0,1};
            int c = 1;
            int neigh = 0;
            while(!is.isEmpty()){
                int x = is.poll();
                int y = js.poll();
                int dis = ds.poll();
                for(int k =0 ;k<4;k++){
                    int newx = x + xx[k];
                    int newy = y + yy[k];
                    if(newx >=0 && newx < grid.length && newy >=0 && newy<grid[0].length && !used[newx][newy]) {
                        if(grid[newx][newy] == 0) {
                            is.add(newx);
                            js.add(newy);
                            ds.add(dis+1);
                            used[newx][newy] = true;
                            d[newx][newy] += dis+1;
                            cc[newx][newy]++;
                            neigh++;
                        } else if(grid[newx][newy] == 1) {
                            c++;
                            used[newx][newy] = true;
                        }
                    } 
                }
            }
            
            return c == count && neigh > 0;
        }
    }

  • 0
    X

    Great Solution!
    But I believe this variable is not useful:

    int neigh = 0;
    

  • 0
    T

    it is useful for cases like

    1 0
    1 1
    

    it detects that the corner 1 can reach all other buildings ,but it doesn't have a ”neigh“ (thus actually not reachable)
    so it's an invalid case.


  • 0
    X

    Thanks for your explanation!


Log in to reply
 

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