317.Shortest-Distance-from-All-Buildings

317. Shortest Distance from All Buildings

题目地址

https://leetcode.com/problems/shortest-distance-from-all-buildings/

题目描述

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.

Example:
Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

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.
Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

代码

Approach #1 BFS

Time: O(M^2N^2) or O(E*MN) && Space: O(MN)

class Solution {
  public int shortestDistance(int[][] grid) {
        if (grid == null || grid[0].length = 0)        return 0;
    int[] shift = new int[] {0, 1, 0, -1, 0};

    int row = grid.length;
    int col = grid[0].length;
    int[][] distance = new int[row][col];
    int[][] reach = new int[row][col];
    int buildingNum = 0;

    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        if (grid[i][j] == 1) {
          buildingNum++;
          Queue<int[]> myQueue = new LinkedList<int[]>();
          myQueue.offer(new int[]{i, j});
          boolean[][] visited = new boolean[row][col];
          int level = 1;

          while (!myQueue.isEmpty()) {
            int qSize = myQueue.size();
            for (int q = 0; q < qSize; q++) {
              int[] curr = myQueue.poll();

              for (int k = 0; k < 4; k++) {
                int nextRow = curr[0] + shift[k];
                int nextCol = curr[1] + shifit[k+1];

                if (nextRow >= 0 && nextRow < row && nextCol >= 0 && nextCol < col && grid[nextRow][nextCol] == 0 && !visited[nextRow][nextCol]) {
                  distance[nextRow][nextCol] += level;
                  reach[nextRow][nextCol]++;

                  visited[nextRow][nextCol] = true;
                  myQueue.offer(new int[] {nextRow, nextCol});
                }
              }
            }
            level++;
          }

        }
      }
    }

    int shortest = Integer.MAX_VALUE;
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        if (grid[i][j] == 0 && reach[i][j] == buildingNum) {
          shortest = Math.min(shortest, distance[i][j]);
        }
      }
    }

    return shortest == Integer.MAX_VALUE ? -1 : shortest;
  }
}