Lintcode 912: Best Meeting Point

https://www.lintcode.com/problem/best-meeting-point/description

Notes

This question can be viewed as a follow up of this question Leetcode 462. Minimum Moves to Equal Array Elements II.

The only difference is that the current question is a 2D case, instead of 1D.

So we just can separate it into two 1Ds. Why can we do this?

Because we need to calculate the Manhattan distance, which is the linear sum of 2 directions.

Once we record the x and y coordinates separately, we can treat it as Leetcode 462.

Leetcode 462 can be solved by binary search for a "u" shape sorted list.

The argument is listed below:

Let say the answer is in the range of [left, right].

Define mid = left + (right - left) / 2;

If dis(mid) < dis(mid-1), then the answer should be in [mid, right];
else, it should be in [left, mid-1].

See the code below:

class Solution {
public:
    int minTotalDistance(vector<vector<int>> &grid) {
        int res = 0;
        if(!grid.size() || !grid.front().size()) return res;
        int m = grid.size(), n = grid.front().size();
        vector<int> xs, ys;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                if(grid[i][j] == 1) {
                    xs.push_back(i);
                    ys.push_back(j);
                }
            }
        }
        int x = f1(xs, 0, m-1), y = f1(ys, 0, n-1);
        return cal(xs, x) + cal(ys, y);
    }

private:
    int f1(vector<int>& vs, int x, int y) {
        if(x==y) return x;
        if(x+1 == y) {
            return cal(vs, x) < cal(vs, y) ? x : y;
        }
        int mid = x + (y - x) / 2;
        if(cal(vs, mid) < cal(vs, mid-1)) return f1(vs, mid, y);
        return f1(vs, x, mid-1);
    }
    int cal(vector<int>& vs, int v) {
        int res = 0;
        for(auto &a : vs) res += abs(a - v);
        return res;
    }
};

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