『LeetCode』827 最大人工岛

题目

827. 最大人工岛

给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿由一组上、下、左、右四个方向相连的 1 形成。

示例 1:

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

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 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

题解

【最大人工岛】简单枚举

枚举

其实最简单最容易想到的办法就是遍历全图尝试将每一个 0 变为 1 后最大的岛屿是哪个。但显然遍历全图是 \(O(n^2)\), 每次查找最大的岛屿也是 \(O(n^2)\), 这个复杂度太过高了。

但更进一步想想，其实把某个位置的 0 变成 1 其实只会影响周围四个位置的岛屿，而其他位置的岛屿并不会变，所以我们可以预处理出所有岛屿的面积，然后就能在 \(O(1)\) 时间内判断将某个位置由 0 变 1 后岛屿的大小，从而将时间复杂度由 \(O(n^4)\) 降为 \(O(n^2 + n^2)\).

// Code language: C++
typedef vector<int> VI;
typedef vector<VI> VII;
int dir[4][2]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        VII mat(n, VI(m, 0));  // 岛屿编号
        VI cnt(n * m + 7);     // 记录岛屿面积
        int p = 1;             // 岛屿编号从 1 开始

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 0) continue;
                int sq = dfs(grid, mat, i, j, p);
                if (sq != 0) cnt[p++] = sq;
            }
        }
        int vis[4];
        int ans = cnt[1];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) continue;
                int sq = 1;
                memset(vis, 0, sizeof(vis));
                for (int k = 0, q = 0; k < 4; ++k) {
                    int x = i + dir[k][0], y = j + dir[k][1];
                    if (x < 0 || x == n || y < 0 || y == m) continue;
                    bool is_new = true;
                    for (int t = 0; t < q && is_new; ++t)
                        if (mat[x][y] == vis[t]) is_new = false;
                    if (!is_new) continue;
                    sq += cnt[mat[x][y]];
                    vis[q++] = mat[x][y];
                }
                ans = max(ans, sq);
            }
        }
        return ans;
    }

    int dfs(VII& grid, VII& mat, int i, int j, int p) {
        if (grid[i][j] == 0 || mat[i][j] != 0) return 0;
        int cnt = 1;
        mat[i][j] = p;
        for (int k = 0; k < 4; ++k) {
            int x = i + dir[k][0], y = j + dir[k][1];
            if (x < 0 || x == grid.size() || y < 0 || y == grid[0].size()) continue;
            cnt += dfs(grid, mat, x, y, p);
        }
        return cnt;
    }
};

时间复杂度: \(O(n^2)\)
空间复杂度: \(O(n^2)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』827 最大人工岛

题目

标签

题解

枚举