Задача: 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 { var dr = [-1, 0, 1, 0] var dc = [0, -1, 0, 1] var grid = [[Int]]() var N = 0 func largestIsland(_ grid: [[Int]]) -> Int { self.grid = grid N = grid.count var index = 2 var area = Int for r in 0..<N { for c in 0..<N { if grid[r][c] == 1 { area[index] = dfs(r, c, index) index += 1 } } } var ans = 0 for x in area { ans = max(ans, x) } for r in 0..<N { for c in 0..<N { if grid[r][c] == 0 { var seen = Set<Int>() for move in neighbors(r, c) { if grid[move / N][move % N] > 1 { seen.insert(grid[move / N][move % N]) } } var bns = 1 for i in seen { bns += area[i] } ans = max(ans, bns) } } } return ans } func dfs(_ r: Int, _ c: Int, _ index: Int) -> Int { var ans = 1 grid[r][c] = index for move in neighbors(r, c) { if grid[move / N][move % N] == 1 { grid[move / N][move % N] = index ans += dfs(move / N, move % N, index) } } return ans } func neighbors(_ r: Int, _ c: Int) -> [Int] { var ans = Int for k in 0..<4 { let nr = r + dr[k] let nc = c + dc[k] if nr >= 0 && nr < N && nc >= 0 && nc < N { ans.append(nr * N + nc) } } return ans } } Ставь 👍 и забирай 📚 Базу знаний