317. Shortest Distance from All Buildings
Hard
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | #define N 100 class Solution { public: int shortestDistance(vector<vector<int>>& grid) { int m = grid.size(); if(m==0) return 0; int n = grid[0].size(); if(n==0) return 0; int nb = 0;//count the number of buildings for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]==1){ nb++; } } } int ret = INT_MAX; bool found = false;//is true of there exists a valid place which can reach all buildings //check every cell if it is not an obstacle, grid[i][j]==0 or 1 //if grid[i][j]==0, this is an potential valid place //if grid[i][j]==1, check if we can reach all other buildings from [i][j]. If not, ie., there exists another buildings [i', j'] //such that grid[i'][j']==1 and [i, j] cannot reach [i', j'], thus, there mush not exist an valid place which can reach all buildings. for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]==2) continue;//cannot pass through an obstacle bool visited[N][N] = {false}; queue<vector<int>> que; int cnt = 0, dist = 0; vector<int> cor={i, j, 0};//row id, column id, current steps que.push(cor); visited[i][j] = true; while(!que.empty()){ int x = que.front()[0]; int y = que.front()[1]; int step = que.front()[2]; que.pop(); if(grid[x][y]==1){//found an buildings which can be reached from [i, j] in "step" steps cnt++; dist += step; } //continue bfs if 1) current place is empty; 2) current place is the original place if(grid[x][y]==0||(i==x && j==y)){ if(x-1>=0 && grid[x-1][y]<2 && !visited[x-1][y]){vector<int> v = {x-1, y, step+1}; que.push(v); visited[x-1][y] = true;}; if(x+1<m && grid[x+1][y]<2 && !visited[x+1][y]){vector<int> v = {x+1, y, step+1}; que.push(v); visited[x+1][y] = true;}; if(y-1>=0 && grid[x][y-1]<2 && !visited[x][y-1]){vector<int> v = {x, y-1, step+1}; que.push(v); visited[x][y-1] = true;}; if(y+1<n && grid[x][y+1]<2 && !visited[x][y+1]){vector<int> v = {x, y+1, step+1}; que.push(v); visited[x][y+1] = true;}; } } //[i, j] is a buildings and it cannot reach all other buildings. Return -1. if(grid[i][j]==1 && cnt<nb) return -1; //[i, j] is an empty place and it can reach all buildings. if(cnt==nb && grid[i][j]==0){ found = true; ret = min(ret, dist); } } } return found?ret:-1; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | public class Solution { public int shortestDistance(int[][] grid) { if (grid == null || grid[0].length == 0) return 0; final int[] shift = new int[] {0, 1, 0, -1, 0}; int row = grid.length, 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[][] isVisited = 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] + shift[k + 1]; if (nextRow >= 0 && nextRow < row && nextCol >= 0 && nextCol < col && grid[nextRow][nextCol] == 0 && !isVisited[nextRow][nextCol]) { //The shortest distance from [nextRow][nextCol] to thic building // is 'level'. distance[nextRow][nextCol] += level; reach[nextRow][nextCol]++; isVisited[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; } } |
