🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 827. Making A Large Island
Сложность: 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
