Задача: 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.

😎 Решение:

public class Solution {
    private static readonly int[] dr = { -1, 0, 1, 0 };
    private static readonly int[] dc = { 0, -1, 0, 1 };
    private int[][] grid;
    private int N;

    public int LargestIsland(int[][] grid) {
        this.grid = grid;
        N = grid.Length;

        int index = 2;
        int[] area = new int[N * N + 2];
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (grid[r][c] == 1) {
                    area[index] = Dfs(r, c, index++);
                }
            }
        }

        int ans = area.Max();
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (grid[r][c] == 0) {
                    HashSet<int> seen = new HashSet<int>();
                    foreach (var move in Neighbors(r, c)) {
                        if (grid[move.Item1][move.Item2] > 1) {
                            seen.Add(grid[move.Item1][move.Item2]);
                        }
                    }
                    int bns = 1;
                    foreach (int i in seen) bns += area[i];
                    ans = Math.Max(ans, bns);
                }
            }
        }
        return ans;
    }

    private int Dfs(int r, int c, int index) {
        int ans = 1;
        grid[r][c] = index;
        foreach (var move in Neighbors(r, c)) {
            if (grid[move.Item1][move.Item2] == 1) {
                grid[move.Item1][move.Item2] = index;
                ans += Dfs(move.Item1, move.Item2, index);
            }
        }
        return ans;
    }

    private IEnumerable<(int, int)> Neighbors(int r, int c) {
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
                yield return (nr, nc);
            }
        }
    }
}

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