Сложность: medium
Вам дано целое число n. У вас есть бинарная сетка размером n x n, в которой все значения изначально равны 1, за исключением некоторых индексов, указанных в массиве mines. Элемент массива mines с индексом i определяется как mines[i] = [xi, yi], где grid[xi][yi] == 0.
Верните порядок самого большого крестообразного знака из 1, выровненного по осям, который содержится в сетке. Если такого знака нет, верните 0.
Крестообразный знак из 1 порядка k имеет некоторый центр grid[r][c] == 1, а также четыре луча длиной k - 1, идущих вверх, вниз, влево и вправо, состоящие из 1. Обратите внимание, что за пределами лучей креста могут быть 0 или 1, проверяется только соответствующая область крестообразного знака на наличие 1.
Пример:
Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.
👨💻 Алгоритм:
1⃣Создайте сетку размером n x n, заполненную единицами. Затем используйте массив mines, чтобы установить значения нулей в соответствующих ячейках сетки.
2⃣Для каждой ячейки в сетке создайте четыре дополнительных сетки: left, right, up и down, которые будут хранить длину непрерывных единиц, простирающихся в соответствующем направлении от каждой ячейки.
3⃣Пройдите по всей сетке и для каждой ячейки определите минимальную длину луча среди четырех направлений. Эта минимальная длина будет определять порядок крестообразного знака с центром в данной ячейке. Обновите максимальный порядок крестообразного знака и верните его после завершения обхода всей сетки. Если такого знака нет, верните 0.
😎 Решение:
class Solution {
function orderOfLargestPlusSign($N, $mines) {
$banned = [];
foreach ($mines as $mine) {
$banned[$mine[0] * $N + $mine[1]] = true;
}
$ans = 0;
for ($r = 0; $r < $N; ++$r) {
for ($c = 0; $c < $N; ++$c) {
$k = 0;
while ($k <= $r && $r < $N - $k && $k <= $c && $c < $N - $k &&
!isset($banned[($r - $k) * $N + $c]) &&
!isset($banned[($r + $k) * $N + $c]) &&
!isset($banned[$r * $N + $c - $k]) &&
!isset($banned[$r * $N + $c + $k])) {
$k++;
}
$ans = max($ans, $k);
}
}
return $ans;
}
}Ставь 👍 и забирай 📚 Базу знаний