[Leetcode 317] Shortest Distance

class Solution {
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }
        
        
        //预处理. 对每个一个0点，求其 1）能被多少个building所连通  2）每个能连通到它的building到其的距离之和
        //然后扫描整个board，对每个0点（能够被所有building都连通的0点）都判断一次，找到distanceSum最小的那个0点，那个distanceSum就是结果
        //预处理如何做？？？  扫描整个board，从每一个building出发，用BFS，对每一个0点记录预处理中的2个值
        //预处理过程中，从build出发，BFS完成后，看是不是剩下的N-1个building都能够连通。如果connectedBuildingNumber != buildingNumer, 那么不是所有的building都连通。直接返回-1
        
        //1. Get all building count
        int totalBuilding = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    totalBuilding ++;
                }
            }
        }
        
        //2. BFS: start from each building, and traverse all possible to connect empty places, 
        // calculate how many building can connect to it, and distanceSum from all buildings
        
        // for each empty place, get the following two value
        int[][] connectedByBuildings = new int[grid.length][grid[0].length];
        int[][] distanceSum = new int[grid.length][grid[0].length];
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    if (!generateDatas (grid, connectedByBuildings, distanceSum, totalBuilding, i, j)) {
                        return -1;
                    }
                }
            }
        }
        
        //3. get the shortest distance
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0 && connectedByBuildings[i][j] == totalBuilding) {
                    result = Math.min (result, distanceSum[i][j]);
                }
            }
        }
        
        return result == Integer.MAX_VALUE ? -1 : result;
        
    }
    
    public boolean generateDatas (int[][] grid, 
                                  int[][] connectedByBuildings, 
                                  int[][] distanceSum, 
                                  int totalBuilding, int startRow, int startCol) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        visited [startRow][startCol] = true;
        
        Queue<int[]> queue1 = new LinkedList<> ();
        Queue<int[]> queue2 = new LinkedList<> ();
        queue1.offer (new int[] {startRow, startCol});
        
        int distance = 0;
        int visitedBuilding = 1;
        
        while (!queue1.isEmpty ()) {
            int[] node = queue1.poll ();
            int row = node[0];
            int col = node[1];
            
            if (grid[row][col] == 0) {
                connectedByBuildings[row][col] ++;
                distanceSum[row][col] += distance;
            }
 
            int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
            
            for (int[] direction : directions) {
                int nextRow = row + direction[0];
                int nextCol = col + direction[1];
                
                if (nextRow >= 0 && nextRow < grid.length && nextCol >= 0 && nextCol < grid[0].length && !visited[nextRow][nextCol]) {
                    visited[nextRow][nextCol] = true;
                    
                    if (grid[nextRow][nextCol] == 0) {
                        queue2.offer (new int[] {nextRow, nextCol});
                    } else if (grid[nextRow][nextCol] == 1) {
                        visitedBuilding ++;
                    }
                    
                }
            }
            
            if (queue1.isEmpty ()) {
                distance ++;
                queue1 = queue2;
                queue2 = new LinkedList<> ();
            }
        }
        
        //System.out.println (visitedBuilding);
        return visitedBuilding == totalBuilding;
    }
}