LeetCode 200. Number of Islands

Study Plan - Graph Theory - Day 1 - Matrix Related Problems。

題目

輸入矩陣grid，其中’0’代表水域，’1’代表陸地，求有多少個島嶼。
一個或多個’1’水平或是垂直相鄰，算做同一個島嶼。且grid四周範圍外也算是水域。

解法

寫一個dfs(r,c)函數，若(r,c)為陸地則砍掉，然後向四周檢查，進而砍掉整個島。
維護一個變數cnt，對所有格子檢查是否為陸地，若是則cnt+1，然後用dfs把小島砍掉。

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

        def dfs(r, c):
            if not (0 <= r < M and 0 <= c < N) or grid[r][c] != '1':
                return
            grid[r][c] = '#'
            for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
                dfs(nr, nc)

        cnt = 0
        for i in range(M):
            for j in range(N):
                if grid[i][j] == '1':
                    cnt += 1
                    dfs(i, j)

        return cnt