695. 岛屿的最大面积-深度优先遍历

695. 岛屿的最大面积-深度优先遍历

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[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：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

很普通的一个图的遍历的问题，解题代码如下：

int count;
void dfs(int** grid,int n,int m,int x,int y){
    count++;
   int  direction[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
    grid[x][y]=0;
    for(int i=0;i<4;i++){
        int x_new=x+direction[i][0],y_new=y+direction[i][1];
        if(x_new>=0&&x_new<n&&y_new>=0&&y_new<m){
            if(grid[x_new][y_new]==1){
                 dfs(grid,n,m,x_new,y_new);

            }
        }
    }


}


int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize){
    int n=gridSize,m=gridColSize[0];
    int max=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            
            if(grid[i][j]==1){
                count=0;
                dfs(grid,n,m,i,j);
                max=fmax(count,max);
            }
        }
    }
    return max;

}
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