827. Making A Large Island

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example 1:

Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.

Notes:

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

这道题在只有0和1的矩阵中用相连的1来表示小岛,现在说是有一个把0变为1的机会,这样原本不相邻的岛就有可能变的相邻了,从而组成一个更大的岛,让求出可能组成的最大的岛屿的面积,也就是相连的1的个数。在 LeetCode 中关于岛屿的题其实也做过许多,比如 Number of Distinct Islands IIMax Area of IslandNumber of Distinct IslandsNumber of Islands II,和 Number of Islands。其实大多题目的本质都是用 DFS 或者 BFS 去遍历所有相连的1,当然这道题也不例外。博主最开始的想法是首先用 DFS 来找出每个岛屿,然后把同一个岛屿的位置坐标都放到同一个 HashSet 中,这样就有了很多 HashSet,然后遍历所有的0的位置,对每个0位置,遍历其周围4个邻居,然后看邻居位置有没有属于岛屿的,有的话就把该岛屿的 HashSet 编号记录下来,遍历完4个邻居后,在把所有的相连的岛屿中的1个数加起来(因为 HashSet 可以直接求出集合中数字的总个数),每次更新结果 res 即可。这种方法是可以通过 OJ 的,速度还比下面展示的两种方法要快,就是代码比较长,没有下面方法的简洁,这里就不贴了。下面的这两种方法其实都是从每个0开始处理,先把0替换成1,然后再用 DFS 来找所有相连的1的个数,具体如何找就跟之前的岛屿的题目没啥区别了,这里就不细讲了,参见代码如下:
解法一:

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), res = 0;
        bool hasZero = false;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) continue;
                grid[i][j] = 1;
                vector<vector<bool>> visited(m, vector<bool>(n));
                res = max(res, helper(grid, i, j, visited));
                if (res == m * n) return res;
                grid[i][j] = 0;
                hasZero = true;
            }
        }
        return hasZero ? res : m * n;
    }
    int helper(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited) {
        int m = grid.size(), n = grid[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + helper(grid, i - 1, j , visited) + helper(grid, i + 1, j , visited) + helper(grid, i, j - 1, visited) + helper(grid, i, j + 1, visited);
    }
};

当然我们也可以用 BFS 来找所有相连的1的个数,整个的解题思路和上面的解法并没有什么不同,并不难理解,这可能就是论坛上会有人质疑这道题不应该标为 Hard 的原因,参见代码如下:
解法二:

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), res = 0;
        bool hasZero = false;
        vector<int> dirX{0, -1, 0, 1}, dirY{-1, 0, 1, 0};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) continue;
                vector<vector<bool>> visited(m, vector<bool>(n));
                queue<int> q{{i * n + j}};
                int sum = 0;
                while (!q.empty()) {
                    int t = q.front(); q.pop();
                    ++sum;
                    for (int k = 0; k < 4; ++k) {
                        int x = t / n + dirX[k], y = t % n + dirY[k];
                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0 || visited[x][y]) continue;
                        visited[x][y] = true;
                        q.push(x * n + y);
                    }
                }
                res = max(res, sum);
                if (res == m * n) return res;
                hasZero = true;
            }
        }
        return hasZero ? res : m * n;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/827

类似题目:

Number of Distinct Islands II

Max Area of Island

Number of Distinct Islands

Number of Islands II

Number of Islands

参考资料:

https://leetcode.com/problems/making-a-large-island/

https://leetcode.com/problems/making-a-large-island/discuss/313787/Two-java-solutions

https://leetcode.com/problems/making-a-large-island/discuss/127256/DFS-JAVA-AC-CONCISE-SOLUTION

https://leetcode.com/problems/making-a-large-island/discuss/127015/C%2B%2B-O(n*m)-15-ms-colorful-islands

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation