Why cannot directly start BFS from empty space instead of building


  • 0
    L

    I browsed some of the answers, and most of them are using the similar fashion of traversing the grid and then if there is a building, find all of the shortest distance for all of the available space to this building.
    I understand it is working, but I prefer the way that while traversing the grid, instead of starting from a building, why cannot we just calculate the distance of all buildings to one space? I tried that, but the OJ gave me a TLE.
    I am confused, since the lower bounds of this two ways are both O(m^2n^2), so it might be because the average time complexity is different, but that depends on the test dataset, if there are more buildings than space, than starting from building will be slower, while if there are more spaces, than my solution will faster.
    Can someone confirm it with me?

    I also attached my algo here:

     public int shortestDistance(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        
        int bcount = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    bcount++;
                }
            }
        }
        
        int min = 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) {
                    int d = bfs(i, j, grid, bcount, min);
                    if (d > 0) {
                        min = Math.min(min, d);
                    }
                }
            }
        }
        
        if (min == Integer.MAX_VALUE) { return -1; }
        return min;
    }
    
    private int bfs(int row, int col, int[][] grid, int bcount, int currentMin) {
          Set<List<Integer>> visited = new HashSet<>();
            List<int[]> level = new LinkedList<>();
            
            level.add(new int[]{row, col});
            visited.add(Arrays.asList(row, col));
            
            int[][] directions = new int[][]{
                {1, 0},
                {-1, 0},
                {0, 1},
                {0, -1},
            };
            
            int sum = 0;
            int count = 0;
            int l = 1;
            while (level.size() > 0) {
                Iterator<int[]> it = level.iterator();
                List<int[]> nlevel = new LinkedList<>();
                while (it.hasNext()) {
                    int[] node = it.next();
                    for (int[] d : directions) {
                        int nx = d[0] + node[0];
                        int ny = d[1] + node[1];
                        
                        if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length) {
                            continue;
                        }
                        if (visited.contains(Arrays.asList(nx, ny))) {
                            continue;
                        }
                        visited.add(Arrays.asList(nx, ny));
                        
                        if (grid[nx][ny] == 2) {
                            continue;
                        }
                        if (grid[nx][ny] == 1) {
                            sum += l;
                            if (sum > currentMin) {
                                return -1;
                            }
                            count++;
                            continue;
                        }
                        nlevel.add(new int[]{nx, ny});
                    }
                }
                level = nlevel;
                l++;
            }
            
            if (count < bcount) {
                return -1;
            }
            
            return sum;
    }

  • 0
    L

    I replaced the visited structure with a boolean array, it passed the test sets, though still very slow, taking over 400 secs.


  • 0
    D

    I believe the test cases on leetcode have more spaces than buildings so starting from spaces take more time. Mine implementation took 800+ ms when starting from spaces.


  • 0

    You can start from empty spots. Theoretically, it should be almost the same to starting from buildings. The reason this method is slower is that this problem should contain more empty spots than buildings for testing since you need paths from one spot to one building. More building means more obstacles and higher chance to return -1.


Log in to reply
 

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