BFS method with pruning, JAVA, Good performance


  • 0
    /*
         * Aim: 
         * Among all empty lands accessible by all buildings, find the one which has the smallest sum of distances   
         * Two subproblems, calculate distance and accessibility.
         * 
         * Method: 
         * For each building in the grid, use BFS to update its distance to all empty lands accessible from it.
         * Maintain a "map" matrix to save the sum of distances from all buildings to a certain empty land. 
         * e.g. the distance between buildingA and empty spot(x, y) is disA, the distance between
         * buildingB and empty spot(x, y) is disB. Then, map[x, y] = disA + disB;
         * The smallest travel distance is the smallest value in the map which is accessible by all buildings.
         *
         * Improvement: inspired by @StefanPochmann's idea :"Instead, I walk only onto the cells that were reachable from all previous buildings. From the first building I only walk onto cells where grid is 0, and make them -1. From the second building I only walk onto cells where grid is -1, and I make them -2. And so on."
         * When updating the ith building's distance to all empty spaces, consider only positions which are accessible by all the previous i-1 buildings.
         *
         * Sum up :
         * n is the entry number of input matrix.
         * Time O(n2) : Space O(n)
         * 
         * real performance: 11ms
         */
    public class Solution {
        public int shortestDistance(int[][] grid) {
            int height = grid.length;
            int width = grid[0].length;
            int[][] map = new int[height][width];
            int b_cnt = 0;
            int[] steps = {1, 0, -1, 0, 1};
            for (int i = 0; i < height; i ++) {
                for (int j = 0; j < width; j ++) {
                    if (grid[i][j] == 1) {
                        if (!BFS(b_cnt, grid, map, new boolean[height][width], i, j, steps) {
                            return -1;
                        }
                        b_cnt --;
                    }
                }
            }
            int Shortest = Integer.MAX_VALUE;
            for (int i = 0; i < height; i ++) {
                for (int j = 0; j < width; j ++) {
                    if (grid[i][j] == b_cnt && Shortest > map[i][j]) {
                        Shortest = map[i][j];
                    }
                }
            }
            return Shortest == Integer.MAX_VALUE ? -1 : Shortest;
        }
        
        public boolean BFS(int b_cnt, int[][] grid, int[][] map, boolean[][] visited, int row, int col, int[] steps) {
            int distance = 1;
            List<Integer> curr = new ArrayList<>();
            curr.add(row);curr.add(col);
            boolean valid = false;
            while (!curr.isEmpty()) {
                List<Integer> next = new ArrayList<>();
                int size = curr.size();
                for (int i = 0; i < size; i += 2) {
                    int r = curr.get(i);
                    int c = curr.get(i + 1);
                    for (int k = 1; k < steps.length; k ++) {
                        int x = r + steps[k - 1];
                        int y = c + steps[k];
                        if (x >= 0 && x <  map.length && y >= 0 && y < map[0].length && !visited[x][y] && grid[x][y] == b_cnt) {
                            valid = true;
                            visited[x][y] = true;
                            grid[x][y] --;
                            map[x][y] += distance;
                            next.add(x);next.add(y);
                        }
                    }
                }
                curr = next;
                distance ++;
            }
            return valid;
        }
    }
    
    

Log in to reply
 

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