題目鏈接：https://leetcode.cn/problems/making-a-large-island/

題目描述：

給你一個(gè)大小為 n x n 二進(jìn)制矩陣 grid 。最多 只能將一格 0 變成 1 。

返回執(zhí)行此操作后，grid 中最大的島嶼面積是多少？

島嶼 由一組上、下、左、右四個(gè)方向相連的 1 形成。

示例 1:

輸入: grid = [[1, 0], [0, 1]]
輸出: 3
解釋: 將一格0變成1，最終連通兩個(gè)小島得到面積為 3 的島嶼。

示例 2:

輸入: grid = [[1, 1], [1, 0]]
輸出: 4
解釋: 將一格0變成1，島嶼的面積擴(kuò)大為 4。

示例 3:

輸入: grid = [[1, 1], [1, 1]]
輸出: 4
解釋: 沒有0可以讓我們變成1，面積依然為 4。

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] 為 0 或 1

解法：標(biāo)記+合并島嶼

首先我們先遍歷grid中的每一塊島嶼，分別利用深度優(yōu)先遍歷，分別向上下左右四個(gè)方向遍歷并標(biāo)記，計(jì)算出每塊島嶼的最大面積，并且給每一塊島嶼進(jìn)行編號(hào)，給相連的島嶼使用相同的標(biāo)號(hào)。

然后我們?cè)诒闅v每一個(gè)空島，使其填充為島嶼，，遍歷其上下左右四個(gè)坐標(biāo)，若坐標(biāo)為島嶼，則將先前標(biāo)記的標(biāo)號(hào)加入到set集合中，利用set不重復(fù)的特性，自動(dòng)去重，最后在里面標(biāo)號(hào)取出先前計(jì)算好的面積進(jìn)行相加，得到連接后的最大島嶼面積。

代碼：

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<Integer> 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<Integer> neighbors(int r, int c) {
        List<Integer> ans = new ArrayList();
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (0 <= nr && nr < N && 0 <= nc && nc < N)
                ans.add(nr * N + nc);
        }

        return ans;
    }
}