Сложность: hard
Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.
Верните размер самого большого острова в grid после выполнения этой операции.
Остров — это группа 1, соединенных в 4 направлениях.
Пример:
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
👨💻 Алгоритм:
1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер.
2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1.
3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.
😎 Решение:
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
def dfs(r, c, index):
ans = 1
grid[r][c] = index
for nr, nc in neighbors(r, c):
if grid[nr][nc] == 1:
grid[nr][nc] = index
ans += dfs(nr, nc, index)
return ans
def neighbors(r, c):
for dr, dc in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N:
yield nr, nc
N = len(grid)
index = 2
area = [0] * (N * N + 2)
for r in range(N):
for c in range(N):
if grid[r][c] == 1:
area[index] = dfs(r, c, index)
index += 1
ans = max(area)
for r in range(N):
for c in range(N):
if grid[r][c] == 0:
seen = {grid[nr][nc] for nr, nc in neighbors(r, c) if grid[nr][nc] > 1}
ans = max(a
Ставь 👍 и забирай 📚 Базу знаний