200 Number of Islands
DFS
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid:
return 0
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
self.dfs(grid, i, j)
count += 1
return count
def dfs(self, grid, i, j):
if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '#'
self.dfs(grid, i+1, j)
self.dfs(grid, i-1, j)
self.dfs(grid, i, j+1)
self.dfs(grid, i, j-1)
463 Island Perimeter
遍历+判断
class Solution(object):
def islandPerimeter(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return 0
cnt = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
cnt += self.sum_adj(grid,i,j)
return cnt
def sum_adj(self, grid, i,j):
adjacent = (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1),
res = 0
for x, y in adjacent:
if x < 0 or y < 0 or x == len(grid) or y == len(grid[0]) or grid[x][y] == 0:
res += 1
return res
695. Max Area of Island
DFS
class Solution(object):
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return 0
ma = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
cnt = self.dfs(grid,i,j)
if cnt > ma:
ma = cnt
return ma
def dfs(self, grid, i,j):
if (i>=0 and j>=0 and i<len(grid) and j<len(grid[0]) and grid[i][j] == 1):
grid[i][j] = '#'
return 1+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 0