Задача: 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 {
int[] dr = new int[]{-1, 0, 1, 0};
int[] dc = new int[]{0, -1, 0, 1};
int[][] grid;
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 = 0;
for (int x: area) ans = Math.max(ans, x);
for (int r = 0; r < N; ++r)
for (int c = 0; c < N; ++c)
if (grid[r][c] == 0) {
Set seen = new HashSet();
for (Integer move: neighbors(r, c))
if (grid[move / N][move % N] > 1)
seen.add(grid[move / N][move % N]);

int bns = 1;
for (int i: seen) bns += area[i];
ans = Math.max(ans, bns);
}

return ans;
}

public int dfs(int r, int c, int index) {
int ans = 1;
grid[r][c] = index;
for (Integer move: 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;
}

public List neighbors(int r, int c) {
List ans = new ArrayList();
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
if (0