题目描述

在二维地图上，0代表海洋，1 代表陆地，我们最多只能将一格 0 海洋变成 1 变成陆地。

进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）

样例

输入: [[1, 0], [0, 1]]
输出: 3
解释: 将一格 0 变成 1，最终连通两个小岛得到面积为 3 的岛屿。

输入: [[1, 1], [1, 0]]
输出: 4
解释: 将一格 0 变成 1，岛屿的面积扩大为 4。

输入: [[1, 1], [1, 1]]
输出: 4
解释: 没有 0 可以让我们变成 1，面积依然为 4。

注意

• 1 <= grid.length = grid[0].length <= 50
• 0 <= grid[i][j] <= 1

算法

(DFS/BFS) $O(nm)$

1. 首先通过 DFS / BFS 算法求出每个岛的大小，记录下每个坐标所属于的岛的编号。每个岛都记录 size。
2. 然后枚举每个 0 格子，将其改变为 1 后，寻找四周不同编号的岛的编号。将这些岛的 size 加起来，然后再加 1 就是合并之后大岛的 size。
3. 如果没有 0 格子，则直接返回 size 最大的岛即可（也就是 $ans = n * m$）。

时间复杂度

• DFS / BFS 的时间复杂度为 $O(nm)$。
• 枚举时，只需要常数时间复杂度更新答案，故总时间复杂度为 $O(nm)$。

C++ 代码

class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};

    void dfs(int x, int y, int n, int m, const vector<vector<int>> &grid,
             int &sz, int idx, vector<vector<int>> &vis) {

        vis[x][y] = idx;
        sz++;

        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 0 || tx >= n || ty < 0 || ty >= m ||
                grid[tx][ty] == 0 || vis[tx][ty] != -1)
                continue;

            dfs(tx, ty, n, m, grid, sz, idx, vis);
        }
    }

    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<int> sz(n * m, 0);
        vector<vector<int>> vis(n, vector<int>(m, -1));

        int idx = 0, ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == 1 && vis[i][j] == -1) {
                    dfs(i, j, n, m, grid, sz[idx], idx, vis);
                    ans = max(ans, sz[idx]);
                    idx++;
                }

        for (int x = 0; x < n; x++)
            for (int y = 0; y < m; y++)
                if (grid[x][y] == 0) {
                    unordered_set<int> islands;

                    for (int i = 0; i < 4; i++) {
                        int tx = x + dx[i], ty = y + dy[i];
                        if (tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] == 0)
                            continue;

                        islands.insert(vis[tx][ty]);
                    }

                    int tot = 1;
                    for (int idx : islands)
                        tot += sz[idx];

                    ans = max(ans, tot);
                }

        return ans;
    }
};