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.

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.

题目来自leetcode，好难...

分析：

这道题目需要准备3个container

vector<vector<int> > values
用来存放每个空格起步的情况下，到达所有房子需要多少步

vector<vector<int> > nums
某个特定的格子可以走到多少个房子，如果走不到所有房子，当然不考虑

vector<pair<int, int> > buindlings
来存储房子们的位置，

具体的过程是这样的，假设开始的时候我们的矩阵是这样：

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

而这时候的value矩阵应该是这样的：

0 - ? - X - ? - 0
|   |   |   |   |
? - ? - ? - ? - ?
|   |   |   |   |
? - ? - 0 - ? - ?

当你bfs过左上角的房子之后，你的矩阵会变成这样

0 - 1 - X - 1 - 0
|   |   |   |   |
1 - 2 - 3 - 2 - 1
|   |   |   |   |
2 - 3 - 0 - 3 - 2

当你bfs过右上角的房子之后，你的矩阵会变成这样

0 - 6 - X - 6 - 0
|   |   |   |   |
6 - 6 - 6 - 6 - 6
|   |   |   |   |
0 - 0 - 1 - 0 - 0

当你bfs过最后一个房子之后，你得到的矩阵是这样

0 - 9 - X - 9 - 0
|   |   |   |   |
9 - 8 - 7 - 8 - 9
|   |   |   |   |
10- 9 - 0 - 9 - 10

这个矩阵的每个元素记录着如果从当前坐标出发，走到所有房子需要的步数总和，最后找到最小值就可以了。

解法：

class Solution {
public:
    bool bfs(int first, 
                int second, 
                int m, 
                int n, 
                vector<pair<int, int> > &buildings, 
                vector<vector<int> > &values, 
                vector<vector<int> > &nums, 
                vector<vector<int> > &grid) {
        queue<pair<int, int> > Q;
        vector<vector<bool> > visited(m, vector<bool>(n, false) );
        Q.push(make_pair(first, second) );
        int depth = 0;
        while (!Q.empty() ) {
            int size = Q.size();
            for (int s = 0; s < size; s++) {
                pair<int, int> temp = Q.front();
                Q.pop();
                int i = temp.first;
                int j = temp.second;
                if (values[i][j] == INT_MAX) {
                    values[i][j] = depth;
                } else {
                    values[i][j] += depth;
                }
                nums[i][j] += 1;

                if (i - 1 >= 0 && visited[i - 1][j] == false) {
                    visited[i - 1][j] = true;
                    if (grid[i - 1][j] == 0) {
                        Q.push(make_pair(i - 1, j) );
                    }
                }
                if (i + 1 < m && visited[i + 1][j] == false) {
                    visited[i + 1][j] = true;
                    if (grid[i + 1][j] == 0) {
                        Q.push(make_pair(i + 1, j) );
                    }
                }
                if (j - 1 >= 0 && visited[i][j - 1] == false) {
                    visited[i][j - 1] = true;
                    if (grid[i][j - 1] == 0) {
                        Q.push(make_pair(i, j - 1) );
                    }
                }
                if (j + 1 < n && visited[i][j + 1] == false) {
                    visited[i][j + 1] = true;
                    if (grid[i][j + 1] == 0) {
                        Q.push(make_pair(i, j + 1) );
                    }
                }
            }
            depth++;
        }
        for (int i = 0; i < buildings.size(); i++) {
            if (visited[buildings[i].first][buildings[i].second] == false) {
                return false;
            }
        }
        return true;
    }

    int shortestDistance(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return -1;
        }
        int m = grid.size();
        int n = grid[0].size();
        vector<pair<int, int> > buildings;
        vector<vector<int> > values(m, vector<int>(n, INT_MAX) );
        vector<vector<int> > nums(m, vector<int>(n, 0) );
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    buildings.push_back(make_pair(i, j) );
                }
            }
        }
        for (int i = 0; i < buildings.size(); i++) {
            int first = buildings[i].first;
            int second = buildings[i].second;
            if (!bfs(first, second, m, n, buildings, values, nums, grid) ) {
                return -1;
            }
        }
        int minDis = INT_MAX;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && nums[i][j] == buildings.size() ) {
                    minDis = values[i][j] > minDis ? minDis : values[i][j];
                }
            }
        }
        return (minDis == INT_MAX) ? -1 : minDis;
    }
};