[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