Задача: 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](repeating: 0, count: N * N + 2)
        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
    }
}

Ставь 👍 и забирай 📚 Базу знаний