695. Max Area of Island@python
2021-06-16 22:05
标签：color array 空间复杂度 代码 because amp lis 复杂度 object Given a non-empty 2D array Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.) Example 1: Given the above grid, return 题意:在一个二维数组中,找出能够连接在一起的数字1的最大长度 思路:DFS 代码: 时间复杂度: O(mn) 空间复杂度:O(1) 695. Max Area of Island@python 标签：color array 空间复杂度 代码 because amp lis 复杂度 object 原文地址：https://www.cnblogs.com/chimpan/p/9723220.htmlgrid 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.[[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. Note the answer is not 11, because the island must be connected 4-directionally.class Solution(object):
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
res = 0
m = len(grid)
n = len(grid[0])
for i in range(m): # 遍历数组
for j in range(n):
if grid[i][j] == 1:
res = max(res, self.dfs(grid, i, j))
return res
def dfs(self, grid, i, j):
m = len(grid)
n = len(grid[0])
if i or i > m-1 or j or j > n-1 or grid[i][j] == 0:
return 0
count = 1
grid[i][j] = 0 # 将值变为0,防止重复计数或者递归栈溢出
count += self.dfs(grid, i+1, j) + self.dfs(grid, i-1, j) + self.dfs(grid, i, j-1) + self.dfs(grid, i, j+1)
return count
下一篇：Java程序语言的后门-反射机制
文章标题：695. Max Area of Island@python
文章链接：http://soscw.com/essay/94758.html