###### tags: `Week_2`, `Graph/BFS/DFS`

# Graph/BFS/DFS

## 733. [Flood Fill](https://leetcode.com/problems/flood-fill/)

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        
        target_color = image[sr][sc]
        def dfs(i, j):
            # print(i, j)
            if image[i][j] != target_color:                
                return
            elif image[i][j] == target_color:
                image[i][j] = color
                
            if i - 1 >= 0:
                dfs(i-1, j)
            if i + 1 < len(image):
                dfs(i+1, j)
            if j - 1 >= 0:
                dfs(i, j-1)
            if j + 1 < len(image[i]):
                dfs(i, j+1)
        
        if image[sr][sc] == color:
            return image
        else:
            dfs(sr, sc)
            return image

## 200. [Number of Islands](https://leetcode.com/problems/number-of-islands/)

import queue
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        num_queue = queue.Queue()
        num_islands = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == '1':
                    num_islands+=1
                    grid[i][j] = '0'
                    num_queue.put((i, j))
                    while not num_queue.empty():
                        row, col = num_queue.get()
                        if row - 1 >= 0 and grid[row - 1][col] == '1':
                            num_queue.put((row-1, col))
                            grid[row-1][col] = '0'
                        if col - 1 >= 0 and grid[row][col - 1] == '1':
                            num_queue.put((row, col - 1))
                            grid[row][col - 1] = '0'
                        if row + 1 < len(grid) and grid[row + 1][col] == '1':
                            num_queue.put((row+1, col))
                            grid[row+1][col] = '0'
                        if col + 1 < len(grid[row]) and grid[row][col + 1] == '1':
                            num_queue.put((row, col + 1))
                            grid[row][col + 1] = '0'
        return num_islands