题目:
给定一个包含了一些 0 和 1的非空二维数组 grid
, 一个 岛屿 是由四个方向 (水平或垂直) 的 1
(代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为0。)
示例 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]]
对于上面这个给定矩阵应返回 6
。注意答案不应该是11,因为岛屿只能包含水平或垂直的四个方向的‘1’。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0
。
注意: 给定的矩阵grid
的长度和宽度都不超过 50。
解题思路:
深度优先搜索。以grid为1的坐标为中心,分别向上下左右四个方向进行搜索,这里注意边界条件:四个方向的坐标应该在grid矩阵内。
代码:
class Solution {
public:
int cnt;
int c,k;
int maxArea = ;
int maxAreaOfIsland(vector<vector<int>>& grid) {
vector<vector<bool>> visited; c = grid.size();
k = grid[].size();
visited.resize(c);
for(int i=; i<c; i++) //visited数组初始化,对于本题可以直接用grid作为访问标记。
visited[i].resize(k);
for(int i=; i<c; ++i)
for(int j=; j<k; ++j){
visited[i][j] = false;
} for(int i=; i<c; ++i)
for(int j=; j<k; ++j) {
if(!visited[i][j] && grid[i][j]) {
cnt = ;
DFS(grid,i,j,visited);
maxArea = max(maxArea, cnt);
}
}
return maxArea;
} void DFS(vector<vector<int>> &grid, int i,int j, vector<vector<bool>> &visited) {
visited[i][j] = true;
//以下进行上下左右搜索
if(i+ < c && !visited[i+][j] && grid[i+][j] ) {
cnt++;
DFS(grid,i+,j,visited); }
if(i->= && !visited[i-][j] && grid[i-][j]) {
cnt++;
DFS(grid, i-, j, visited); }
if(j+<k && !visited[i][j+] && grid[i][j+]) {
cnt++;
DFS(grid,i,j+,visited); }
if(j->= && !visited[i][j-] && grid[i][j-]) {
cnt++;
DFS(grid,i,j-,visited); }
}
};