来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/max-area-of-island
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一、题目描述
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为0。)
示例 1:
1 2 3 4 5 6 7 8 |
[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]] |
对于上面这个给定矩阵应返回 6。注意答案不应该是11,因为岛屿只能包含水平或垂直的四个方向的‘1’。
示例 2:
1 |
[[0,0,0,0,0,0,0,0]] |
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
二、题解
和地图相关的题目求最值,第一个想到的都应该是深度优先搜索,例如求两点间的最短路径、迷宫找最短出口等,都可以用深搜来解决问题。当然,出了深搜以外,还可以通过回溯来解决。深搜实际上是递归,而回溯则是迭代。
使用深搜的思路:遍历每个地图点,如果是陆地,就往四个方向上继续蔓延,一旦遍历到非陆地或者超出地图范围了就返回。
要注意的问题是,当一个点蔓延到另外一个点后,另外一个点也可能会蔓延回来。例如A是B的左节点,B作为陆地蔓延到A后又会作为A的右节点蔓延回来。这种情况下就导致重复计算,所以为了避免重复处理,需要特殊处理这个问题。可以采取的办法是每访问到一个节点,就把它变成海洋。
输入数据需要考虑的特殊场景:空地图,地图只有一列或一行。
三、代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
class Solution { /* * @grid 地图 * @i/j 需要计算的地图坐标 * @row/col 地图的行数和列数 * @return 返回相连的面积 */ int dfs(vector<vector<int>> &grid, int i, int j, const int row, const int col) { int top, bottom, left, right; // dfs退出条件,到达了边界,或者当前值为0 if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0) return 0; // 已经访问过的节点置为0,避免重复计算 grid[i][j] = 0; // 分别计算上下左右四个方向上的面积 top = dfs(grid, i + 1, j, row, col); bottom = dfs(grid, i - 1, j, row, col); right = dfs(grid, i, j + 1, row, col); left = dfs(grid, i, j - 1, row, col); // 返回总面积 return top + bottom + left + right + 1; } public: int maxAreaOfIsland(vector<vector<int>> &grid) { int i, j, row, col, res; if (grid.empty()) return 0; row = grid.size(); col = grid[0].size(); res = 0; for (i = 0; i < row; i++) { for (j = 0; j < col; j++) { // 提前剪枝 if (grid[i][j] == 0) continue; // 遍历每一个节点 res = max(res, dfs(grid, i, j, row, col)); } } return res; } }; |
测试案例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
TEST(leetcode, demo) { Solution s; vector<vector<int>> input1{ {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0}, {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0} }, input2{{1}}, input3{{0,0,0,0,0,0}}, input4; EXPECT_EQ(s.maxAreaOfIsland(input1), 6); EXPECT_EQ(s.maxAreaOfIsland(input2), 1); EXPECT_EQ(s.maxAreaOfIsland(input3), 0); EXPECT_EQ(s.maxAreaOfIsland(input4), 0); } |
评论