Задача: 296. Best Meeting Point
Сложность: hard

Дан бинарный сетка размером m x n, где каждая 1 обозначает дом одного друга. Верните минимальное общее расстояние путешествия.

Общее расстояние путешествия — это сумма расстояний между домами друзей и точкой встречи.

Расстояние рассчитывается по Манхэттенскому расстоянию, где distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Пример:

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.

👨‍💻 Алгоритм:

1⃣Определение координат домов:
Пройдите по сетке и соберите координаты всех домов (ячейки с значением 1) в два списка: один для координат x и один для координат y.

2⃣Нахождение медианы:
Отсортируйте списки координат x и y.
Найдите медианы в обоих списках. Медианы координат x и y укажут оптимальную точку встречи.

3⃣Вычисление минимального общего расстояния:
Вычислите сумму Манхэттенских расстояний от каждого дома до точки встречи, используя найденные медианы в качестве координат точки встречи.
Верните это значение как минимальное общее расстояние путешествия.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int MinTotalDistance(int[][] grid) {
        int minDistance = int.MaxValue;
        for (int row = 0; row < grid.Length; row++) {
            for (int col = 0; col < grid[0].Length; col++) {
                int distance = Search(grid, row, col);
                minDistance = Math.Min(distance, minDistance);
            }
        }
        return minDistance;
    }

    private int Search(int[][] grid, int row, int col) {
        Queue<Tuple<int, int, int>> q = new Queue<Tuple<int, int, int>>();
        q.Enqueue(Tuple.Create(row, col, 0));
        int m = grid.Length;
        int n = grid[0].Length;
        bool[][] visited = new bool[m][];
        for (int i = 0; i < m; i++) {
            visited[i] = new bool[n];
        }
        int totalDistance = 0;

        while (q.Count > 0) {
            var point = q.Dequeue();
            int r = point.Item1;
            int c = point.Item2;
            int d = point.Item3;

            if (r < 0 || c < 0 || r >= m || c >= n || visited[r][c]) {
                continue;
            }

            if (grid[r][c] == 1) {
                totalDistance += d;
            }

            visited[r][c] = true;

            q.Enqueue(Tuple.Create(r + 1, c, d + 1));
            q.Enqueue(Tuple.Create(r - 1, c, d + 1));
            q.Enqueue(Tuple.Create(r, c + 1, d + 1));
            q.Enqueue(Tuple.Create(r, c - 1, d + 1));
        }

        return totalDistance;
    }
}

Ставь 👍 и забирай 📚 Базу знаний