Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/296.html
Given an m x n
binary grid grid
where each 1
marks the home of one friend, return the minimal total travel distance.
The total travel distance is the sum of the distances between the houses of the friends and the meeting point.
The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|
.
Example 1:
Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]] Output: 6 Explanation: Given three friends 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.
Example 2:
Input: grid = [[1,1]] Output: 1
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j]
is either0
or1
.- There will be at least two friends in the
grid
.
Algorithm
First look at the situation where there are two points A and B in one dimension.
______A_____P_______B_______
It can be found that as long as the meeting is that the location P is in the interval [A, B]
, no matter where it is, the sum of the distances is the distance between A and B. If P is not between [A, B]
, then the sum of the distances is Will be greater than the distance between A and B, now add two more points C and D:
______C_____A_____P_______B______D______
The best position of point P is in the interval [A, B]
, so that the sum of the distances from the four points is the AB distance plus the CD distance.
Just sort the positions, then subtract the first coordinate from the last coordinate, which is the CD distance, and subtract the second coordinate from the penultimate, the second coordinate, which is the AB distance. And so on, until the middle stop.
The one-dimensional situation is analyzed, and the two-dimensional situation is the addition of two one-dimensional results.
Code
-
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Best_Meeting_Point { public static void main(String[] args) { Best_Meeting_Point out = new Best_Meeting_Point(); Solution s = out.new Solution(); System.out.println(s.minTotalDistance(new int[][] { {1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0} })); } public class Solution { public int minTotalDistance(int[][] grid) { // empty, null check List<Integer> ipos = new ArrayList<>(); List<Integer> jpos = new ArrayList<>(); for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { ipos.add(i); jpos.add(j); } } } int sum = 0; // ipos already sorted, since above it's iterating over grid via i index int iMid = ipos.get(ipos.size() / 2); for(Integer pos : ipos){ sum += Math.abs(pos - iMid); } Collections.sort(jpos); int jMid = jpos.size() / 2; for (int j = 0; j < jpos.size(); j++) { sum += Math.abs(jpos.get(jMid) - jpos.get(j)); } return sum; } } } ############ class Solution { public int minTotalDistance(int[][] grid) { int m = grid.length, n = grid[0].length; List<Integer> rows = new ArrayList<>(); List<Integer> cols = new ArrayList<>(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) { rows.add(i); cols.add(j); } } } Collections.sort(cols); int i = rows.get(rows.size() >> 1); int j = cols.get(cols.size() >> 1); return f(rows, i) + f(cols, j); } private int f(List<Integer> arr, int x) { int s = 0; for (int v : arr) { s += Math.abs(v - x); } return s; } }
-
// OJ: https://leetcode.com/problems/best-meeting-point/ // Time: O(MN^2) // Space: O(MN) class Solution { public: int minTotalDistance(vector<vector<int>>& A) { int M = A.size(), N = A[0].size(), ans = INT_MAX, dist[201][201] = {}, up[201][201] = {}, down[201][201] = {}, cnt[201] = {}; for (int i = 0; i < M; ++i) { int sum = 0, left = 0, right = 0; for (int j = 0; j < N; ++j) { if (A[i][j] == 0) continue; sum += j; right++; } for (int j = 0; j < N; ++j) { dist[i][j] = sum; if (A[i][j]) ++left, --right; sum += left - right; } cnt[i] = left; } int c = cnt[0]; for (int i = 1; i < M; ++i) { for (int j = 0; j < N; ++j) { int mn = INT_MAX; for (int k = 0; k < N; ++k) { mn = min(mn, dist[i - 1][k] + (abs(j - k) + 1) * c); } up[i][j] = up[i - 1][j] + mn; } c += cnt[i]; } c = cnt[M - 1]; for (int i = M - 2; i >= 0; --i) { for (int j = 0; j < N; ++j) { int mn = INT_MAX; for (int k = 0; k < N; ++k) { mn = min(mn, dist[i + 1][k] + (abs(j - k) + 1) * c); } down[i][j] = down[i + 1][j] + mn; } c += cnt[i]; } for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { ans = min(ans, dist[i][j] + up[i][j] + down[i][j]); } } return ans; } };
-
''' >>> sum(a for a in range(6)) 15 >>> sum([a for a in range(6)]) 15 ''' class Solution: def minTotalDistance(self, grid: List[List[int]]) -> int: def f(arr, x): return sum(abs(v - x) for v in arr) rows, cols = [], [] for i, row in enumerate(grid): for j, v in enumerate(row): if v: rows.append(i) cols.append(j) cols.sort() row_mid_val = rows[len(rows) >> 1] col_mid_val = cols[len(cols) >> 1] return f(rows, row_mid_val) + f(cols, col_mid_val) ############ class Solution(object): def minTotalDistance(self, grid): """ :type grid: List[List[int]] :rtype: int """ iList, jList, ppl = [], [], [] for i in range(0, len(grid)): for j in range(0, len(grid[0])): if grid[i][j] == 1: ppl.append((i, j)) iList.append(i) jList.append(j) jList.sort() m = (iList[len(iList) / 2], jList[len(jList) / 2]) return sum(map(lambda p: abs(p[1] - m[1]) + abs(p[0] - m[0]), ppl))
-
func minTotalDistance(grid [][]int) int { rows, cols := []int{}, []int{} for i, row := range grid { for j, v := range row { if v == 1 { rows = append(rows, i) cols = append(cols, j) } } } sort.Ints(cols) i := rows[len(rows)>>1] j := cols[len(cols)>>1] f := func(arr []int, x int) int { s := 0 for _, v := range arr { s += abs(v - x) } return s } return f(rows, i) + f(cols, j) } func abs(x int) int { if x < 0 { return -x } return x }