Monday, December 14, 2015

LeetCode [317] Shortest Distance from All Buildings

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 01 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;
        
        
    }
}

No comments:

Post a Comment