← Static tasks

296. Best Meeting Point

leetcode hard

#array#csharp#hard#leetcode#math#matrix#queue#search

Task

Дан бинарный сетка размером 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.

C# solution

matched/original
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;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinTotalDistance(int[][] grid) {
        int minDistance = int.MaxValue;
        for (int row = 0; row < grid.size(); row++) {
            for (int col = 0; col < grid[0].size(); col++) {
                int distance = Search(grid, row, col);
                minDistance = 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.size();
        int n = grid[0].size();
        bool[][] visited = new bool[m][];
        for (int i = 0; i < m; i++) {
            visited[i] = new bool[n];
        }
        int totalDistance = 0;
        while (q.size() > 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;
    }
}

Java solution

matched/original
public class Solution {
    public int minTotalDistance(int[][] grid) {
        int minDistance = Integer.MAX_VALUE;
        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<int[]> q = new LinkedList<>();
        q.add(new int[]{row, col, 0});
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int totalDistance = 0;

        while (!q.isEmpty()) {
            int[] point = q.poll();
            int r = point[0];
            int c = point[1];
            int d = point[2];

            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.add(new int[]{r + 1, c, d + 1});
            q.add(new int[]{r - 1, c, d + 1});
            q.add(new int[]{r, c + 1, d + 1});
            q.add(new int[]{r, c - 1, d + 1});
        }

        return totalDistance;
    }
}

JavaScript solution

matched/original
class Solution {
    minTotalDistance(grid) {
        let minDistance = Number.MAX_SAFE_INTEGER;
        for (let row = 0; row < grid.length; row++) {
            for (let col = 0; col < grid[0].length; col++) {
                const distance = this.search(grid, row, col);
                minDistance = Math.min(distance, minDistance);
            }
        }
        return minDistance;
    }

    search(grid, row, col) {
        const q = [[row, col, 0]];
        const m = grid.length;
        const n = grid[0].length;
        const visited = Array.from({ length: m }, () => Array(n).fill(false));
        let totalDistance = 0;

        while (q.length > 0) {
            const [r, c, d] = q.shift();

            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.push([r + 1, c, d + 1]);
            q.push([r - 1, c, d + 1]);
            q.push([r, c + 1, d + 1]);
            q.push([r, c - 1, d + 1]);
        }

        return totalDistance;
    }
}

Python solution

matched/original
class Solution:
    def minTotalDistance(self, grid: list[list[int]]) -> int:
        minDistance = float('inf')
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                distance = self.search(grid, row, col)
                minDistance = min(distance, minDistance)
        return minDistance

    def search(self, grid: list[list[int]], row: int, col: int) -> int:
        q = [(row, col, 0)]
        m = len(grid)
        n = len(grid[0])
        visited = [[False] * n for _ in range(m)]
        totalDistance = 0
        
        while q:
            r, c, d = q.pop(0)
            
            if r < 0 or c < 0 or r >= m or c >= n or visited[r][c]:
                continue
            
            if grid[r][c] == 1:
                totalDistance += d
            
            visited[r][c] = True
            
            q.append((r + 1, c, d + 1))
            q.append((r - 1, c, d + 1))
            q.append((r, c + 1, d + 1))
            q.append((r, c - 1, d + 1))
        
        return totalDistance

Go solution

matched/original
package main

import (
  "math"
)

func minTotalDistance(grid [][]int) int {
  minDistance := math.MaxInt32
  for row := 0; row < len(grid); row++ {
    for col := 0; col < len(grid[0]); col++ {
      distance := search(grid, row, col)
      if distance < minDistance {
        minDistance = distance
      }
    }
  }
  return minDistance
}

func search(grid [][]int, row int, col int) int {
  type Point struct {
    r, c, d int
  }
  q := []Point{{row, col, 0}}
  m := len(grid)
  n := len(grid[0])
  visited := make([][]bool, m)
  for i := range visited {
    visited[i] = make([]bool, n)
  }
  totalDistance := 0

  for len(q) > 0 {
    point := q[0]
    q = q[1:]
    r, c, d := point.r, point.c, point.d

    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 = append(q, Point{r + 1, c, d + 1})
    q = append(q, Point{r - 1, c, d + 1})
    q = append(q, Point{r, c + 1, d + 1})
    q = append(q, Point{r, c - 1, d + 1})
  }

  return totalDistance
}

Explanation

Algorithm

Определение координат домов:

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

Нахождение медианы:

Отсортируйте списки координат x и y.

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

Вычисление минимального общего расстояния:

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

Верните это значение как минимальное общее расстояние путешествия.

😎