子寒的博客
0%

leetcode695 Max Area of Island 解题报告

发表于 分类于

英文原题

You are given an m x n binary matrix grid. 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.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

example

1
2
3
Input: 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]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

分析

    很经典的深度搜索题目，我的思路是遍历所有的点，发现有1以后去求这个岛屿的面积，用dfs，上下左右四个方向寻找，这里为了避免重复寻找，每找到一个1就把它变成0，看代码应该更直观。     第二次做这个题目了，上次做example还没有配图，这次居然有图了。

python 代码

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
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        maxArea = 0
        tmpArea = [0]
        
        def getArea(x, y):
            if x >= 0 and y >= 0 and x < len(grid) and y < len(grid[0]) and grid[x][y] == 1:
                tmpArea[0] += 1
                grid[x][y] = 0
                getArea(x-1, y)
                getArea(x+1, y)
                getArea(x, y-1)
                getArea(x, y+1)
            else:
                return
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    getArea(i, j)
                    maxArea = max(tmpArea[0], maxArea)
                    tmpArea[0] = 0
        
        return maxArea