[Leetcode] - 200
dfs
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(i, j):
if i < 0 or i >= szx:
return
if j < 0 or j >= szy:
return
if grid[i][j] == '#' or grid[i][j] == '0':
return
grid[i][j] = '#'
dfs(i+1, j)
dfs(i-1, j)
dfs(i, j+1)
dfs(i, j-1)
cnt = 0
szx = len(grid)
szy = len(grid[0])
for i in range(szx):
for j in range(szy):
if grid[i][j] == '1':
dfs(i,j)
cnt += 1
return cnt
bfs
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def bfs(vx, vy, grid, szx, szy):
mv = [[1,0], [-1,0], [0,1], [0,-1]]
que = deque([[vx, vy]])
while que:
vx, vy = que.popleft()
for dx, dy in mv:
nx = vx + dx
ny = vy + dy
if nx < 0 or nx >= szx:
continue
if ny < 0 or ny >= szy:
continue
if grid[nx][ny] != '1':
continue
grid[nx][ny] = 'm'
que.append([nx, ny])
return
szx = len(grid)
szy = len(grid[0])
cnt = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
grid[i][j] = 'm'
bfs(i, j, grid, szx, szy)
cnt += 1
return cnt
Reference
この問題について([Leetcode] - 200), 我々は、より多くの情報をここで見つけました https://velog.io/@jisngprk/Leetcode-200テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol