LeetCode 695. Max Area of Island
文章目录
Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 1:
[[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]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
大致题意
找到最大的岛屿大小(示例中为1的部分)
题解
题目类型: DFS
题目给的地图就是最好的状态图,0不用开始深搜,1就可以搜索,搜索过后的标注为0
每到一个岛屿就开始深搜表示查找相应大小,和之前的最大大小进行比对,找到最大值
代码如下
class Solution {
public:
int search(int row, int column, vector<vector<int>>& grid) {
if (row >= 0 && column >= 0 && row < grid.size() && column < grid[row].size() && grid[row][column] > 0) {
grid[row][column] = 0;
return 1 + search(row + 1, column, grid) + search(row - 1, column, grid) + search(row, column + 1, grid) + search(row, column - 1, grid);
}
return 0;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int maxArea = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
maxArea = max(search(i, j, grid), maxArea);
}
}
return maxArea;
}
};
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论