In a 2D grid of 0
s and 1
s, we change at most one 0
to a 1
.html
After, what is the size of the largest island? (An island is a 4-directionally connected group of 1
s).java
Example 1:git
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:github
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:code
Input: [[1, 1], [1, 1]] Output: 4 Explanation: Can't change any 0 to 1, only one island with area = 4.
Notes:htm
1 <= grid.length = grid[0].length <= 50
.0 <= grid[i][j] <= 1
.
这道题在只有0和1的矩阵中用相连的1来表示小岛,如今说是有一个把0变为1的机会,这样本来不相邻的岛就有可能变的相邻了,从而组成一个更大的岛,让求出可能组成的最大的岛屿的面积,也就是相连的1的个数。在 LeetCode 中关于岛屿的题其实也作过许多,好比 Number of Distinct Islands II,Max Area of Island,Number of Distinct Islands,Number 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的个数,具体如何找就跟以前的岛屿的题目没啥区别了,这里就不细讲了,参见代码以下:blog
解法一:leetcode
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 的缘由,参见代码以下:get
解法二:同步
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
相似题目:
参考资料:
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