# Leetcode 200. Number of islands

## DFS

透過標記已訪問過的島嶼為 "2" 來遍歷是否為同一個島嶼

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        islands = 0

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == "1":
                    stack = [row * cols + col]
                    grid[row][col] = "2"
                    islands += 1

                    while stack:
                        current = stack.pop()
                        x = current // cols
                        y = current % cols

                        # down
                        if x + 1 < rows:
                            if grid[x+1][y] == "1":
                                stack.append((x + 1) * cols + y)
                                grid[x+1][y] = "2"
                        # up
                        if x - 1 >= 0:
                            if grid[x-1][y] == "1":
                                stack.append((x - 1) * cols + y)
                                grid[x-1][y] = "2"
                        # left
                        if y - 1 >= 0:
                            if grid[x][y-1] == "1":
                                stack.append(x * cols + (y - 1))
                                grid[x][y-1] = "2"
                        # right
                        if y + 1 < cols:
                            if grid[x][y+1] == "1":
                                stack.append(x * cols + (y + 1))
                                grid[x][y+1] = "2"
        return islands

### DFS (Recursion)

走過的標記為 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

### 2024.04.19 每日一題
直接標記為0

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        dems = [[0,-1], [0,1], [-1, 0], [1, 0]]
        ans = 0

        def dfs(x,y):
            grid[y][x] = "0"
            for dx,dy in dems:
                dx += x
                dy += y
                if 0 <= dx < n and 0 <= dy < m and grid[dy][dx] == "1":
                    dfs(dx,dy)

        for node in range(m*n):
            x, y = node // m, node % m
            if grid[y][x] == "1":
                dfs(x,y)
                ans += 1
        
        return ans