Number of Islands

https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1374/

这道题最容易理解的是DFS, 但是套用BFS的模板也可以做出来。

DFS Version

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i,j,grid):
            m = len(grid)
            n = len(grid[0])
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == "0":
                return
            grid[i][j] = "0"
            dfs(i-1,j,grid)
            dfs(i+1,j,grid)
            dfs(i,j-1,grid)
            dfs(i,j+1,grid)
        cnt = 0
        m = len(grid)
        if m == 0:
            return cnt
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    dfs(i,j,grid)
                    cnt+=1
        return cnt

BFS Version

from collections import deque
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        queue = deque()
        cnt = 0
        m = len(grid)
        dirs = [(0,1),(0,-1),(1,0),(-1,0)]
        if m == 0:
            return cnt
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    cnt+=1
                    queue.append((i,j))
                    grid[i][j] = "0"
                    while queue:
                        x,y = queue.popleft()
                        for d in dirs:
                            newX,newY = x+d[0],y+d[1]
                            if 0<=newX < m and 0<= newY <n and grid[newX][newY] =="1":
                                queue.append((newX,newY))
                                grid[newX][newY] = "0"
        return cnt