Shortest distance from all buildings

similar questions: walls and gates.

This question seems to be an easy, however, test case is huge and always got TLE.

1. First thing need to clarify, land numbers compared to building numbers. it determines start doing BFS from land or buildings.

2. How many states a cell can have ?

    0: land can pass.
    1: buildings.
    -1: obstacles.
   

3. Target function: Sum of distance(land,building) is minimum.

4. Traps:
   • This graph may doesn't exist a land connected to all buildings(which I failed to test at first).
   • If you find a building can't connect to each other, simply return, otherwise error
   • Check minimum should satisfy all cells have reached here.

Algorithm Description.

Step 1: count number of buildings.

Step 2: for each building, run BFS traversal, identify each land distance to this building. record it. and make land counter++(which means one building have bee

An optimization:
by the time traversal, when could also check if this building connected to other buildings, if can't connected to each other, which means no free land can connected all buildings together.

Step 3: for all valid free lands, select the one with minimum cost. what is a valid free land?

         counterMap[freeland] == numberOfBuildings.

Implementation

Time Complexity: O(n) * O(mn) Space: O(mn)

boolean bfs(int[][] countMap, int[][] grid, int startX, int startY, int[][] cost, int buildingNum) {

         int[][] dirs = {{-1,0}, {0,1}, {1,0}, {0,-1}};
         boolean[][] v = new boolean[grid.length][grid[0].length];
         Queue<Pair> q = new LinkedList<>();
         q.offer(new Pair(startX,startY));
         int countBuildings = 0;
         int level = 0;
         while (!q.isEmpty()) {
             int size = q.size();
             level++;
             for(int i = 0; i < size; i++) {
                   Pair cur = q.poll();
                   for(int [] dir : dirs) {
                         int di = dir[0] + cur.i;
                         int dj = dir[1] + cur.j;
                         if (isInBound(di,dj) && !v[di][dj]) {
                             //a freeland 
                             if (grid[di][dj] == 0) {
                                 cost[di][dj] += level;
                                 //mark this freeland can reach one building
                                 countMap[di][dj]++;
                                 q.offer(new Pair(di,dj));
                             }
                             //a building
                             else if (grid[di][dj] == 1) {
                                 //mark we reach one building
                                 countBuildings++;
                             }
                             v[di][dj] = true;
                         }
                   }
             }
         }
         return countBuildings == buildingNum;
   }