動機

以為是要數幾座島，結果是要數島的面積

Problem

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:

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

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]Output: 0

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is either 0 or 1.

Sol

def dfs(g,i,j):
    if 0 > i or 0 > j or i >= len(g) or j >= len(g[0]) or g[i][j][1] or g[i][j][0] == 0:
        return 0
    else:
        ret = 1
        g[i][j][1] = True
        for (x,y) in [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]:
            ret += dfs(g,x,y)
        return ret
        
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ret = 0
        g = [[[x,False] for x in gg] for gg in grid]
        for i in range(len(g)):
            for j in range(len(g[0])):
                ret = max(ret, dfs(g,i,j))
        return ret