Сложность: 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 {
public int orderOfLargestPlusSign(int N, int[][] mines) {
Set<Integer> banned = new HashSet<>();
for (int[] mine : mines)
banned.add(mine[0] * N + mine[1]);
int ans = 0;
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
int k = 0;
while (k <= r && r < N - k && k <= c && c < N - k &&
!banned.contains((r - k) * N + c) &&
!banned.contains((r + k) * N + c) &&
!banned.contains(r * N + c - k) &&
!banned.contains(r * N + c + k)) {
k++;
}
ans = Math.max(ans, k);
}
}
return ans;
}
}Ставь 👍 и забирай 📚 Базу знаний