Задача: 1162. As Far from Land as Possible
Сложность: medium

Дана сетка размером n x n, содержащая только значения 0 и 1, где 0 представляет воду, а 1 представляет землю. Найдите ячейку с водой, такое что её расстояние до ближайшей ячейки с землёй максимально, и верните это расстояние. Если в сетке нет ни земли, ни воды, верните -1.

Расстояние, используемое в этой задаче, - это манхэттенское расстояние: расстояние между двумя ячейками (x0, y0) и (x1, y1) равно |x0 - x1| + |y0 - y1|.

Пример:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

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

1⃣Итерируйте по матрице и вставьте координаты ячеек с землёй в очередь. Инициализируйте переменную distance значением -1 для хранения текущего шага обхода в ширину (BFS). Также создайте копию матрицы visited для пометки ячеек с водой как посещённые, чтобы не вставлять их снова в очередь.

2⃣Выполните BFS: Обходите текущие элементы в очереди и для каждого элемента проверяйте координаты в четырёх направлениях, являются ли они ячейками с водой (0). Если да, вставьте их в очередь и измените их на ячейки с землёй (1) в матрице visited. После каждого пройденного уровня (внутренний цикл while завершён), увеличьте переменную distance.

3⃣Повторяйте, пока очередь не станет пустой. Верните значение distance. Если оно равно 0, это означает, что не было ячеек с водой и обход завершился после первого шага, поэтому верните -1. Если в матрице не было ячеек с землёй, цикл while вообще не начнётся, и переменная distance останется с начальным значением (-1).

😎 Решение:

class Solution {
    function maxDistance($grid) {
        $directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        $visited = $grid;
        $q = [];
        
        for ($i = 0; $i < count($grid); $i++) {
            for ($j = 0; $j < count($grid[0]); $j++) {
                if ($grid[$i][$j] == 1) {
                    $q[] = [$i, $j];
                }
            }
        }
        
        $distance = -1;
        while (count($q) > 0) {
            $qSize = count($q);
            while ($qSize-- > 0) {
                list($landX, $landY) = array_shift($q);
                foreach ($directions as $dir) {
                    $x = $landX + $dir[0];
                    $y = $landY + $dir[1];
                    if ($x >= 0 && $y >= 0 && $x < count($grid) && $y < count($grid[0]) && $visited[$x][$y] == 0) {
                        $visited[$x][$y] = 1;
                        $q[] = [$x, $y];
                    }
                }
            }
            $distance++;
        }
        
        return $distance == 0 ? -1 : $distance;
    }
}

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