leetcode 296

问题

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: 

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

Output: 6 

Explanation: Given three people living at (0,0), (0,4), and (2,2):
             The point (0,2) is an ideal meeting point, as the total travel distance 
             of 2+2+2=6 is minimal. So return 6.

分析

思路1: 采用BFS对每个参会人员进行深度优先搜索。时间复杂度 $O(m^2n^2)$。（Time Limit Exceeded）

思路2: 可以考虑到这道题和317是不一样的，这个题目中没有障碍物的限制。根据曼哈顿可以将行和列分别进行考虑。先将所有参会人员都降维维一行上，计算出最佳的meeting的列，然后再将所有参会人员将为到一列上，计算出最佳的meeting的行。

代码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
// BFS： Time Limit Exceeded
class Solution {
public:
    vector<vector<int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    int minTotalDistance(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = m==0? 0: grid[0].size();
        if (m == 0 || n == 0)
            return 0;
        
        vector<vector<int>> dist(m, vector<int>(n,0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1)
                    bfs(grid, dist, i, j);
            }
        }
        
        int ans = INT_MAX;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans = min(ans, dist[i][j]);
            }
        }
        return ans;
    }
    void bfs(vector<vector<int>> &grid, vector<vector<int>> &dist, int x, int y) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<bool>> v(m, vector<bool>(n, false));
        
        queue<pair<int,int>> q;
        q.push(make_pair(x,y));
        v[x][y] = true;
        int d = 0;
        while (q.size() != 0) {
            d++;
            int size = q.size();
            while (size--) {
                int x0 = q.front().first;
                int y0 = q.front().second;
                q.pop();
                
                for (vector<int> &dir: dirs) {
                    int x1 = x0 + dir[0];
                    int y1 = y0 + dir[1];
                    if (x1 < 0 || x1 >= m || y1<0 || y1>=n || v[x1][y1] == true)
                        continue;
                    v[x1][y1] = true;
                    dist[x1][y1] += d;
                    q.push(make_pair(x1,y1));
                }
            }
        }
    }
};

代码2

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
// 降维 O(mn)
class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = m==0? 0: grid[0].size();
        if (m == 0 || n == 0)
            return 0;
        
        vector<int> x, y;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1)
                    x.push_back(i);
            }
        }
        
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < m; ++i) {
                if (grid[i][j] == 1)
                    y.push_back(j);
            }
        }
        return getMin(x) + getMin(y);
    }
    int getMin(vector<int> &x) {
        int ret = 0;
        int i = 0, j = x.size()-1;
        while (i < j) {
            ret += x[j--] - x[i++];
        }
        return ret;
    }
};