Number of Islands
LeetCode 200
class Solution:
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
"""
DFS解題有個很重要的地方為 BASE CASE: 終止條件
"""
if not grid:
return 0
else:
count = 0
row = len(grid)
col = len(grid[0])
for i in range(row):
for j in range(col):
if grid[i][j] == '1':
self.dfs(grid, i, j)
#self.bfs(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) # down
self.dfs(grid,i,j+1) # right
self.dfs(grid,i-1,j) # up
self.dfs(grid,i,j-1) # left
def bfs(self, grid, i, j):
queue = collections.deque()
queue.append((i,j))
while queue:
i, j = queue.popleft()
if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j] =='1':
grid[i][j] = '#'
queue.extend([(i-1,j),(i+1,j),(i,j-1),(i,j+1)])
Last updated