Задача: 317. Shortest Distance from All Buildings
Сложность: hard

Дана сетка 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

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

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

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

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

😎 Решение:

class Solution {
    private function bfs(&$grid, $row, $col, $totalHouses) {
        $dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        $rows = count($grid);
        $cols = count($grid[0]);
        $distanceSum = 0;
        $housesReached = 0;
        $steps = 0;
        $q = [[$row, $col]];
        $vis = array_fill(0, $rows, array_fill(0, $cols, false));
        $vis[$row][$col] = true;

        while (!empty($q) && $housesReached != $totalHouses) {
            $size = count($q);
            while ($size-- > 0) {
                list($r, $c) = array_shift($q);
                if ($grid[$r][$c] == 1) {
                    $distanceSum += $steps;
                    $housesReached++;
                    continue;
                }
                foreach ($dirs as $dir) {
                    $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;
                        array_push($q, [$nr, $nc]);
                    }
                }
            }
            $steps++;
        }

        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 PHP_INT_MAX;
        }
        return $distanceSum;
    }

    public function shortestDistance($grid) {
        $minDistance = PHP_INT_MAX;
        $rows = count($grid);
        $cols = count($grid[0]);
        $totalHouses = 0;

        foreach ($grid as $row) {
            foreach ($row as $cell) {
                if ($cell == 1) {
                    $totalHouses++;
                }
            }
        }

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

        return $minDistance == PHP_INT_MAX ? -1 : $minDistance;
    }
}

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