Lintcode 803: Shortest Distance from All Buildings

https://www.lintcode.com/problem/shortest-distance-from-all-buildings/description

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

Example 1

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation:
In this example, there are 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.

Example 2

Input: [[1,0],[0,0]]
Output: 1
In this example, there is one buildings at (0,0).
1 - 0
|   |
0 - 0
The point (1,0) or (0,1) is an ideal empty land to build a house, as the total travel distance of 1 is minimal. So return 1.

Notes:

This question is labeled as hard in both Leetcode and Lintcode, but actually the idea is pretty straightforward:

1): we can use bfs search for each house, then record the minimum distance results for each "empty" position into a hash map;

2): then we need to go through the hash map, to find the empty position having the minimum sum distances to all the houses.

See the code below:

class Solution {
public:
    /**
     * @param grid: the 2D grid
     * @return: the shortest distance
     */
    int shortestDistance(vector<vector<int>> &grid) {
        // write your code here
        if(!grid.size() || !grid.front().size()) return 0;
        int res = INT_MAX, m = grid.size(), n = grid.front().size(), ct = 0;
        unordered_map<int, vector<int>> mp;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j] == 1) {
                    ++ct;
                    bfs(grid, i, j, mp);
                }
            }
        }
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j] == 0 && mp[i*n+j].size() == ct) {
                    int sum = 0;
                    for(auto &a : mp[i*n+j]) sum += a;
                    res = min(res, sum);
                }
            }
        }
        return res==INT_MAX? -1 : res;
    }

private:
    void bfs(vector<vector<int>>& grid, int i, int j, unordered_map<int, vector<int>>& mp) {
        int m = grid.size(), n = grid.front().size();
        vector<vector<int>> visit(m, vector<int>(n, 0));
        queue<pair<int, int>> q;
        q.push({i, j});
        visit[i][j] = 1;
        vector<int> dirs = {-1, 0, 1, 0, -1};
        int step = 1;
        while(q.size()) {
            int k = q.size();
            for(int i=0; i<k; ++i) {
                auto t = q.front();
                q.pop();
                for(int j=0; j+1<dirs.size(); ++j) {
                    int a = t.first + dirs[j], b = t.second + dirs[j+1];
                    if(a<0 || a>=m || b<0 || b>=n || grid[a][b] != 0 || visit[a][b]) continue;
                    q.push({a, b});
                    visit[a][b] = 1;
           //         cout<<a<<" "<<b<<" "<<step<<endl;
                    mp[a*n+b].push_back(step);
                }
            }
            ++step;
        }
    }
};