# Leetcode 200. Number of Islands

## 題解

### DFS

走過的標記為 2，對沒走過並且為 1 的島嶼進行 DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        directions = [
            [0,1],
            [0,-1],
            [1,0],
            [-1,0]
        ]

        m,n = len(grid),len(grid[0])
        output = 0

        def dfs(x,y):
            for direction in directions:
                new_x = x + direction[0]
                new_y = y + direction[1]
                if new_x < n and new_x >= 0 and new_y >= 0 and new_y < m and grid[new_y][new_x] == "1":
                    grid[new_y][new_x] = "2"
                    dfs(new_x,new_y)
        
        for y in range(m):
            for x in range(n):
                if grid[y][x] == "1":
                    output += 1
                    grid[y][x] = "2"
                    dfs(x,y)
                    
        return output