← Static tasks

317. Shortest Distance from All Buildings

leetcode hard

#array#backtracking#csharp#graph#hard#leetcode#math#matrix#queue

Task

Дана сетка m x n, содержащая значения 0, 1 или 2, где:

каждое 0 обозначает пустую землю, по которой можно свободно проходить,

каждое 1 обозначает здание, через которое нельзя пройти,

каждое 2 обозначает препятствие, через которое нельзя пройти.

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

Верните минимальное суммарное расстояние для такого дома. Если построить такой дом невозможно согласно указанным правилам, верните -1.

Суммарное расстояние — это сумма расстояний между домами друзей и точкой встречи.

Пример

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

Output: 7

C# solution

matched/original
using System;
using System.Collections.Generic;
public class Solution {
    private int Bfs(int[][] grid, int row, int col, int totalHouses) {
        int[][] dirs = { new int[] { 1, 0 }, new int[] { -1, 0 }, new int[] { 0, 1 }, new int[] { 0, -1 } };
        int rows = grid.Length, cols = grid[0].Length, distanceSum = 0, housesReached = 0, steps = 0;
        Queue<int[]> q = new Queue<int[]>();
        q.Enqueue(new int[] { row, col });
        bool[,] vis = new bool[rows, cols];
        vis[row, col] = true;
        while (q.Count > 0 && housesReached != totalHouses) {
            int size = q.Count;
            while (size-- > 0) {
                int[] curr = q.Dequeue();
                int r = curr[0], c = curr[1];
                if (grid[r][c] == 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }
                foreach (var dir in dirs) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr, nc] && grid[nr][nc] != 2) {
                        vis[nr, nc] = true;
                        q.Enqueue(new int[] { nr, nc });
                    }
                }
            }
            steps++;
        }
        if (housesReached != totalHouses) {
            for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0 && vis[r, c]) grid[r][c] = 2;
            return int.MaxValue;
        }
        return distanceSum;
    }
    public int ShortestDistance(int[][] grid) {
        int minDistance = int.MaxValue, rows = grid.Length, cols = grid[0].Length, totalHouses = 0;
        foreach (var row in grid) foreach (var cell in row) if (cell == 1) totalHouses++;
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0) minDistance = Math.Min(minDistance, Bfs(grid, r, c, totalHouses));
        return minDistance == int.MaxValue ? -1 : minDistance;
    }
}

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:
    private int Bfs(int[][] grid, int row, int col, int totalHouses) {
        int[][] dirs = { new int[] { 1, 0 }, new int[] { -1, 0 }, new int[] { 0, 1 }, new int[] { 0, -1 } };
        int rows = grid.size(), cols = grid[0].size(), distanceSum = 0, housesReached = 0, steps = 0;
        queue<int[]> q = new queue<int[]>();
        q.Enqueue(new int[] { row, col });
        bool[,] vis = new bool[rows, cols];
        vis[row, col] = true;
        while (q.size() > 0 && housesReached != totalHouses) {
            int size = q.size();
            while (size-- > 0) {
                vector<int>& curr = q.Dequeue();
                int r = curr[0], c = curr[1];
                if (grid[r][c] == 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }
                foreach (var dir in dirs) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr, nc] && grid[nr][nc] != 2) {
                        vis[nr, nc] = true;
                        q.Enqueue(new int[] { nr, nc });
                    }
                }
            }
            steps++;
        }
        if (housesReached != totalHouses) {
            for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0 && vis[r, c]) grid[r][c] = 2;
            return int.MaxValue;
        }
        return distanceSum;
    }
    public int ShortestDistance(int[][] grid) {
        int minDistance = int.MaxValue, rows = grid.size(), cols = grid[0].size(), totalHouses = 0;
        foreach (var row in grid) foreach (var cell in row) if (cell == 1) totalHouses++;
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0) minDistance = min(minDistance, Bfs(grid, r, c, totalHouses));
        return minDistance == int.MaxValue ? -1 : minDistance;
    }
}

Java solution

matched/original
import java.util.*;

class Solution {
    private int bfs(int[][] grid, int row, int col, int totalHouses) {
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int rows = grid.length, cols = grid[0].length;
        int distanceSum = 0, housesReached = 0, steps = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{row, col});
        boolean[][] vis = new boolean[rows][cols];
        vis[row][col] = true;

        while (!q.isEmpty() && housesReached != totalHouses) {
            int size = q.size();
            while (size-- > 0) {
                int[] curr = q.poll();
                int r = curr[0], c = curr[1];
                if (grid[r][c] == 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }
                for (int[] dir : dirs) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr][nc] && grid[nr][nc] != 2) {
                        vis[nr][nc] = true;
                        q.offer(new int[]{nr, nc});
                    }
                }
            }
            steps++;
        }

        if (housesReached != totalHouses) {
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == 0 && vis[r][c]) grid[r][c] = 2;
                }
            }
            return Integer.MAX_VALUE;
        }
        return distanceSum;
    }

    public int shortestDistance(int[][] grid) {
        int minDistance = Integer.MAX_VALUE, rows = grid.length, cols = grid[0].length, totalHouses = 0;
        for (int[] row : grid) for (int cell : row) if (cell == 1) totalHouses++;
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0) minDistance = Math.min(minDistance, bfs(grid, r, c, totalHouses));
        return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
    }
}

Python solution

matched/original
from collections import deque

class Solution:
    def bfs(self, grid, row, col, totalHouses):
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        rows, cols = len(grid), len(grid[0])
        distanceSum, housesReached = 0, 0
        q = deque([(row, col)])
        visited = [[False] * cols for _ in range(rows)]
        visited[row][col] = True
        steps = 0

        while q and housesReached != totalHouses:
            for _ in range(len(q)):
                r, c = q.popleft()
                if grid[r][c] == 1:
                    distanceSum += steps
                    housesReached += 1
                    continue

                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and grid[nr][nc] != 2:
                        visited[nr][nc] = True
                        q.append((nr, nc))
            steps += 1

        if housesReached != totalHouses:
            for r in range(rows):
                for c in range(cols):
                    if grid[r][c] == 0 and visited[r][c]:
                        grid[r][c] = 2
            return float('inf')

        return distanceSum

    def shortestDistance(self, grid):
        rows, cols = len(grid), len(grid[0])
        minDistance, totalHouses = float('inf'), 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    totalHouses += 1

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    minDistance = min(minDistance, self.bfs(grid, r, c, totalHouses))

        return -1 if minDistance == float('inf') else minDistance

Go solution

matched/original
import (
  "math"
)

func bfs(grid [][]int, row, col, totalHouses int) int {
  dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
  rows, cols := len(grid), len(grid[0])
  distanceSum, housesReached, steps := 0, 0, 0
  q := [][3]int{{row, col, 0}}
  vis := make([][]bool, rows)
  for i := range vis {
    vis[i] = make([]bool, cols)
  }
  vis[row][col] = true

  for len(q) > 0 && housesReached != totalHouses {
    r, c, steps := q[0][0], q[0][1], q[0][2]
    q = q[1:]

    if grid[r][c] == 1 {
      distanceSum += steps
      housesReached++
      continue
    }

    for _, dir := range dirs {
      nr, nc := r+dir[0], c+dir[1]
      if nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr][nc] && grid[nr][nc] != 2 {
        vis[nr][nc] = true
        q = append(q, [3]int{nr, nc, steps + 1})
      }
    }
  }

  if housesReached != totalHouses {
    for r := 0; r < rows; r++ {
      for c := 0; c < cols; c++ {
        if grid[r][c] == 0 && vis[r][c] {
          grid[r][c] = 2
        }
      }
    }
    return math.MaxInt32
  }
  return distanceSum
}

func shortestDistance(grid [][]int) int {
  minDistance := math.MaxInt32
  rows, cols := len(grid), len(grid[0])
  totalHouses := 0

  for _, row := range grid {
    for _, cell := range row {
      if cell == 1 {
        totalHouses++
      }
    }
  }

  for r := 0; r < rows; r++ {
    for c := 0; c < cols; c++ {
      if grid[r][c] == 0 {
        minDistance = min(minDistance, bfs(grid, r, c, totalHouses))
      }
    }
  }

  if minDistance == math.MaxInt32 {
    return -1
  }
  return minDistance
}

func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

Explanation

Algorithm

Инициализация и запуск BFS

Для каждой пустой ячейки (0) в сетке grid запустите BFS, обходя все соседние ячейки в 4 направлениях, которые не заблокированы и не посещены, отслеживая расстояние от начальной ячейки.

Обработка BFS и обновление расстояний

При достижении здания (1) увеличьте счетчик достигнутых домов housesReached и суммарное расстояние distanceSum на текущее расстояние. Если housesReached равно общему количеству зданий, верните суммарное расстояние. Если BFS не может достигнуть всех домов, установите значение каждой посещенной пустой ячейки в 2, чтобы не запускать новый BFS из этих ячеек, и верните INT_MAX.

Обновление и возврат минимального расстояния

Обновите минимальное расстояние (minDistance) после каждого вызова BFS. Если возможно достигнуть все дома из любой пустой ячейки, верните найденное минимальное расстояние. В противном случае, верните -1.

😎