Very short code of BFS of buildings together


  • 0
    O

    My plan is to do BFS for every building together, so that the first BFS point that are reach by all buildings, I can return the accumulated cost and avoid all the useless work searching for other empty points. But I met an issue that the returned value sometimes larger than the expected answer by 1. Don't know why. So I decided not to return when all-reach BFS points are found and wait for the whole BFS to complete. Anyone who get the idea to improve the solution please give your valuable suggestion.

    On the other hand, do BFS for all the building together has the disadvantage of finding "return -1" very late. that is to say, if there's a building that is impossible to reach other buildings, the code can only find it once the whole BFS is complete.

    Anyway I think my code is short and clear and worthy to share.

    public class Solution {
        public int shortestDistance(int[][] g) {
            int h = g.length, w = g[0].length, n = 0, ans = Integer.MAX_VALUE;
            int[][] cost = new int[h][w];   // cost - cost of all buildings to reach [i,j]
            int[][]   nv = new int[h][w];   // nv - number of buildings to that visited (reached) [i,j]
            Queue<Qnode> q = new LinkedList();
            
            for (int i = 0; i < h; i++) // count buildings and build initial queue
                for (int j = 0; j < w; j++)
                    if (g[i][j] == 1) q.offer(new Qnode(i, j, n++, 0));
            
            boolean[][][] v = new boolean[h][w][n]; // mark whether visited by i th building
            while (!q.isEmpty()) {
                Qnode cur = q.poll();
                for (int[] d : dir) {
                    int y = cur.i + d[0], x = cur.j + d[1];
                    if (x >= 0 && x < w && y >= 0 && y < h && g[y][x] == 0 && !v[y][x][cur.id]) {
                        cost[y][x] += cur.dist + 1;
                        v[y][x][cur.id] = true;
                        if (++nv[y][x] == n && cost[y][x] < ans) ans = cost[y][x];
                        q.offer(new Qnode(y, x, cur.id, cur.dist + 1));
                    }
                }
            }
      
            return ans < Integer.MAX_VALUE ? ans : -1;
        }
        
        private class Qnode {
            int i, j;       // this building travels (BFS) to position (i, j) 
            int id, dist;   // id - building index number, dist - distance of (i, j) to the buildings initial position
            
            public Qnode(int y, int x, int idx, int d) {
                i = y; j = x; id = idx; dist = d;
            }
        }
        
        private static final int[][] dir = {{0, 1},{1, 0},{0, -1},{-1, 0}};
    }
    

    // 65ms


Log in to reply
 

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