[LeetCode][BFS] 317. Shortest Di

Problem

More LeetCode Discussions
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.
For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

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.

Solution

找出所有的1，然后依次对他们BFS，然后得到一张dis的表格，canReach用来追踪有多少个1可以到达这个点，只有canReach[i][j] == points.size()说明所有的1都可以到达。

struct QType {
  pair<int, int> p;
  int step;
};

class Solution {
private:
    vector<vector<int>> canReach;
    vector<vector<int>> dis;
    vector<pair<int, int>> points;
    vector<vector<bool>> canUse;
    int steps[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public:
    void bfs(vector<vector<int>> &grid, pair<int, int> p) {
        queue<QType> q;
        QType node;
        node.p = p;
        node.step = 0;
        for(int i = 0; i < canUse.size(); i++) {
            for(int j = 0; j < canUse[i].size(); j++) {
                canUse[i][j] = true;
            }
        }
        canUse[p.first][p.second] = false;
        q.push(node);
        
        while (!q.empty()) {
            QType node = q.front();
            q.pop();
            for(int i = 0; i < 4; i++) {
                int newX = node.p.first + steps[i][0];
                int newY = node.p.second + steps[i][1];
                int step = node.step + 1;
                if (0 <= newX && newX < canUse.size() && 0 <= newY && newY < canUse[0].size() && canUse[newX][newY] && 
                grid[newX][newY] == 0) {
                    QType node;
                    pair<int, int> p;
                    p.first = newX;
                    p.second = newY;
                    node.p = p;
                    node.step = step;
                    q.push(node);
                    canUse[newX][newY] = false;
                    dis[newX][newY] += step;
                    canReach[newX][newY]++;
                }
            }
        }
    }
    
    int shortestDistance(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return -1;
        }
        
        canReach.resize(grid.size());
        dis.resize(grid.size());
        canUse.resize(grid.size());
        
        for(int i = 0; i < dis.size(); i++) {
            canReach[i].resize(grid[0].size());
            dis[i].resize(grid[0].size());
            canUse[i].resize(grid[0].size());
        }
        
        for(int i = 0; i < dis.size(); i++) {
            for(int j = 0; j < dis[i].size(); j++) {
                dis[i][j] = canReach[i][j] = 0;
            }
        }
        
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == 1) {
                    pair<int, int> p;
                    p.first = i;
                    p.second = j;
                    points.push_back(p);
                }
            }
        }
        
        for(int i = 0; i < points.size(); i++) {
            bfs(grid, points[i]);
        }
        
        int minDist = -1;
        for(int i = 0; i < canReach.size(); i++) {
            for(int j = 0; j < canReach[i].size(); j++) {
                if (canReach[i][j] == points.size()) {
                    if (minDist == -1) {
                        minDist = dis[i][j];
                    } else {
                        minDist = min(minDist, dis[i][j]);
                    }
                }
            }
        }
        
        return minDist;
    }
};