- Given a non-empty 2D array grid 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.
- Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
- Example 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]]
- Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
- Example 2:
- [[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
- class Solution(object):
- def maxAreaOfIsland(self, grid):
- h, w = len(grid), len(grid[0])
- def dfs(x, y):
- if 0 <= x < h and 0 <= y < w and grid[x][y]:
- grid[x][y] = 0
- return 1 + dfs(x-1, y) + dfs(x+1, y) + dfs(x, y-1) + dfs(x, y+1)
- return 0
- areas = [dfs(i, j) for i in range(h) for j in range(w) if gird[i][j]]
- return max(areas) if areas else 0
四方向 dfs 遍历, 注意每次进入递归函数且确定是 1 后要置 0, 这样对于每一个 island 来说, 第一次找到属于它的 1 时其它的全部都找到了, 把他们标记为 0 后避免了重复查找. 用 for(h,w) 在图中搜索尚未访问的 1 即可找到最大值.
来源: http://www.bubuko.com/infodetail-3122194.html