IT博客汇 | 317. Shortest Distance from All Buildings

317. Shortest Distance from All Buildings

10k发表于 2024-06-15 00:00:00

Question

You are given an m x n grid grid of values 0, 1, or 2, where:

each 0 marks an empty land that you can pass by freely,
each 1 marks a building that you cannot pass through, and
each 2 marks an obstacle that you cannot pass through.

You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right.

Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example 1:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2).
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal.
So return 7.

Example 2:

Input: grid = [[1,0]]
Output: 1

Example 3:

Input: grid = [[1]]
Output: -1

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0, 1, or 2.
There will be at least one building in the grid.

Algorithm

For each empty cell (grid[i][j]equals 0), start a BFS:
- In the BFS, traverse all 4-directionally adjacent cells that are not blocked or visited and keep track of the distance from the start cell. Each iteration adds 1 to the distance.
- Every time we reach a house, increment houses reached counter housesReached by 1, and increase the total distance distanceSum by the current distance (i.e., the distance from the start cell to the house).
- If housesReached equals totalHouses, then return the total distance.
- Otherwise, the starting cell (and every cell visited during this BFS) cannot reach all of the houses. So set every visited empty land cell equal to 2 so that we do not start a new BFS from that cell and return INT_MAX.
Each time a total distance is returned from a BFS call, update the minimum distance (minDistance).
If it is possible to reach all houses from any empty land cell, then return the minimum distance found. Otherwise, return -1.

The part might be ignore is that there are cases that you cannot visit all the nodes due to the wall. So track down the house visited is necessary

Code

Code1(DFS, not right)

The question said we use Manhattan distance, however, it's not , it uses difference approach where bfs would be better and intuitive to solve this problem.

class Solution {
    public int shortestDistance(int[][] grid) {
        int smallest = Integer.MAX_VALUE;
        int totalHouse = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    totalHouse++;
                }
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    int dis = dfs(grid, new int[]{i, j}, totalHouse);
                    if (dis != 0) smallest = Math.min(smallest, dis);
                }
            }
        }
        return smallest == Integer.MAX_VALUE ? -1 : smallest;
    }
    
    private int dfs(int[][] grid, int[] start, int totalHouse) {
        int total = 0;
        Stack<int[]> stack = new Stack();
        Set<List<Integer>> visited = new HashSet<>();
        stack.push(start);
        visited.add(List.of(start[0], start[1]));
        int houseVisited = 0;
        while (!stack.isEmpty()) {
            int[] node = stack.pop();
            int row = node[0];
            int col = node[1];
            if (grid[row][col] == 1) {
                total += distance(start, node);
                houseVisited++;
            } else if (grid[row][col] == 0) {
                if (row - 1 >= 0 && !visited.contains(List.of(row-1, col))) {
                    stack.push(new int[]{row-1, col});
                    visited.add(List.of(row-1, col));
                }
                if (row + 1 < grid.length && !visited.contains(List.of(row+1, col))) {
                    stack.push(new int[]{row+1, col});
                    visited.add(List.of(row+1, col));
                }
                if (col - 1 >= 0 && !visited.contains(List.of(row, col-1))) {
                    stack.push(new int[]{row, col-1});
                    visited.add(List.of(row, col-1));
                }
                if (col + 1 < grid[0].length && !visited.contains(List.of(row, col+1))) {
                    stack.push(new int[]{row, col+1});
                    visited.add(List.of(row, col+1));
                }
            }
        }
        return houseVisited == totalHouse ? total : 0;
    }
    
    private int distance(int[] p1, int[] p2) {
        return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
    }
}

Code2 (TLE)

The question/OJ will let you fail if you have no optimization for the algorithm.

class Solution {
    public int shortestDistance(int[][] grid) {
        int smallest = Integer.MAX_VALUE;
        int totalHouse = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    totalHouse++;
                }
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    int dis = bfs(grid, new int[]{i, j}, totalHouse);
                    if (dis != 0) smallest = Math.min(smallest, dis);
                }
            }
        }
        return smallest == Integer.MAX_VALUE ? -1 : smallest;
    }
    
    private int bfs(int[][] grid, int[] start, int totalHouse) {
        int total = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        Set<List<Integer>> visited = new HashSet<>();
        visited.add(List.of(start[0], start[1]));
        int houseVisited = 0;
        int step = 0;
        while (!queue.isEmpty() && houseVisited != totalHouse) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] node = queue.poll();
                int row = node[0];
                int col = node[1];
                if (grid[row][col] == 1) {
                    total += step;
                    houseVisited++;
                } else if (grid[row][col] == 0) {
                    if (row - 1 >= 0 && !visited.contains(List.of(row-1, col))) {
                        queue.offer(new int[]{row-1, col});
                        visited.add(List.of(row-1, col));
                    }
                    if (row + 1 < grid.length && !visited.contains(List.of(row+1, col))) {
                        queue.offer(new int[]{row+1, col});
                        visited.add(List.of(row+1, col));
                    }
                    if (col - 1 >= 0 && !visited.contains(List.of(row, col-1))) {
                        queue.offer(new int[]{row, col-1});
                        visited.add(List.of(row, col-1));
                    }
                    if (col + 1 < grid[0].length && !visited.contains(List.of(row, col+1))) {
                        queue.offer(new int[]{row, col+1});
                        visited.add(List.of(row, col+1));
                    }
                }
            }
            step++;
        }
        
        return houseVisited == totalHouse ? total : 0;
    }
}

Code3

I don't understand why the similar code above can be TLE..

class Solution {
    private int bfs(int[][] grid, int row, int col, int totalHouses) {
        // Next four directions.
        int dirs[][] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        int rows = grid.length;
        int cols = grid[0].length;
        int distanceSum = 0;
        int housesReached = 0;
        
        // Queue to do a bfs, starting from (row, col) cell.
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{ row, col });
        
        // Keep track of visited cells.
        boolean[][] vis = new boolean[rows][cols];
        vis[row][col] = true;

        int steps = 0;
        while (!q.isEmpty() && housesReached != totalHouses) {
            for (int i = q.size(); i > 0; --i) {
                int[] curr = q.poll();
                row = curr[0];
                col = curr[1];
                
                // If this cell is a house, then add the distance from source to this cell
                // and we go past from this cell.
                if (grid[row][col] == 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }
                
                // This cell was empty cell, hence traverse the next cells which is not a blockage.
                for (int[] dir : dirs) {
                    int nextRow = row + dir[0]; 
                    int nextCol = col + dir[1];
                    if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols) {
                        if (!vis[nextRow][nextCol] && grid[nextRow][nextCol] != 2) {
                            vis[nextRow][nextCol] = true;
                            q.offer(new int[]{ nextRow, nextCol });
                        }
                    }
                }
            }
            
            // After traversing one level of cells, increment the steps by 1 to reach to next level.
            steps++;
        }

        // If we did not reach all houses, then any cell visited also cannot reach all houses.
        // Set all cells visted to 2 so we do not check them again and return MAX_VALUE.
        if (housesReached != totalHouses) {
            for (row = 0; row < rows; row++) {
                for (col = 0; col < cols; col++) {
                    if (grid[row][col] == 0 && vis[row][col]) {
                        grid[row][col] = 2;
                    }
                }
            }
            return Integer.MAX_VALUE;
        }
        
        // If we have reached all houses then return the total distance calculated.
        return distanceSum;
    }
    
    public int shortestDistance(int[][] grid) {
        int minDistance = Integer.MAX_VALUE;
        int rows = grid.length; 
        int cols = grid[0].length;
        int totalHouses = 0;
        
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] == 1) {
                    totalHouses++;
                }
            }
        }
        
        // Find the min distance sum for each empty cell.
        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] == 0) {
                    minDistance = Math.min(minDistance, bfs(grid, row, col, totalHouses));
                }
            }
        }
        
        // If it is impossible to reach all houses from any empty cell, then return -1.
        if (minDistance == Integer.MAX_VALUE) {
            return -1;
        }
        
        return minDistance;
    }
};

Code4

Then I check the code and change the visited things to use a array which is more simple and time efficiency then it passed!

class Solution {
    public int shortestDistance(int[][] grid) {
        int smallest = Integer.MAX_VALUE;
        int totalHouse = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    totalHouse++;
                }
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    int dis = bfs(grid, new int[]{i, j}, totalHouse);
                    if (dis != 0) smallest = Math.min(smallest, dis);
                }
            }
        }
        return smallest == Integer.MAX_VALUE ? -1 : smallest;
    }
    
    private int bfs(int[][] grid, int[] start, int totalHouse) {
        int total = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        visited[start[0]][start[1]] = true;
        int houseVisited = 0;
        int step = 0;
        while (!queue.isEmpty() && houseVisited != totalHouse) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] node = queue.poll();
                int row = node[0];
                int col = node[1];
                if (grid[row][col] == 1) {
                    total += step;
                    houseVisited++;
                } else if (grid[row][col] == 0) {
                    if (row - 1 >= 0 && !visited[row-1][col]) {
                        queue.offer(new int[]{row-1, col});
                        visited[row-1][col] = true;
                    }
                    if (row + 1 < grid.length && !visited[row+1][col]) {
                        queue.offer(new int[]{row+1, col});
                        visited[row+1][col] = true;
                    }
                    if (col - 1 >= 0 && !visited[row][col-1]) {
                        queue.offer(new int[]{row, col-1});
                        visited[row][col-1] = true;
                    }
                    if (col + 1 < grid[0].length && !visited[row][col+1]) {
                        queue.offer(new int[]{row, col+1});
                        visited[row][col+1] = true;
                    }
                }
            }
            step++;
        }
        
        if (houseVisited != totalHouse) {
            for (int row = 0; row < grid.length; row++) {
                for (int col = 0; col < grid[0].length; col++) {
                    if (grid[row][col] == 0 && visited[row][col]) {
                        grid[row][col] = 2;
                    }
                }
            }
            return Integer.MAX_VALUE;
        }
        
        return houseVisited == totalHouse ? total : 0;
    }
}