【LeetCode】695.岛屿的最大面积

1. 题目

2. 分析

简单的深搜，但是如何在深搜的时候记住最后获得的值呢？这是个问题。

3. 代码

class Solution:
    def __init__(self,):
        self.res = 0

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        res = 0
        vis = [[0] * n for i in range(m)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and vis[i][j] == 0: # 如果是1
                    vis[i][j] = 1
                    self.res = 1 # 重置为1。 计算当前这个区域有几个节点
                    self.dfs(grid,i,j,m,n,vis)
                    print(self.res)
                    res = max(res,self.res)
        print(vis)
        return res

    # 深搜的时候不停的更新最大值即可
    def dfs(self,grid,x,y,m,n,vis):
        # 向上
        if x-1 >=0 and vis[x-1][y] == 0 and grid[x-1][y] == 1:
            vis[x-1][y] = 1
            self.res += 1
            self.dfs(grid,x-1,y,m,n,vis)
        
        # 向下
        if x+1 <m and vis[x+1][y] == 0 and grid[x+1][y] == 1:
            vis[x+1][y] = 1
            self.res +=1 
            self.dfs(grid,x+1,y,m,n,vis)
        
        # 向左
        if y-1 >=0 and vis[x][y-1] == 0 and grid[x][y-1] == 1:
            vis[x][y-1] = 1
            self.res+=1
            self.dfs(grid,x,y-1,m,n,vis)
        
        # 向右
        if y+1 <n and vis[x][y+1] == 0 and grid[x][y+1] == 1:
            vis[x][y+1] = 1
            self.res += 1
            self.dfs(grid,x,y+1,m,n,vis)
        # return res
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