0200. Number of Islands - chasel2361/leetcode GitHub Wiki

💡 Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1: Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Example 2: Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

---

這題要搜尋相連的島嶼有幾個，可以利用DFS(depth-first search)來解決，先宣告一個與grid同樣大小的list來儲存是否造訪過各個元素，接下來就利用DFS來逐一尋訪元素，只要可以執行一次DFS就代表有一個島嶼，利用累加就可以算出島嶼數量

Python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]: return 0
        
        m, n = len(grid), len(grid[0])
        visited = [[False for _ in range(n)] for _ in range(m)]
        res = 0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1' and not visited[i][j]:
                    res += 1
                    self.DFS(grid, visited, i, j)
        return res
    
    def DFS(self, grid, visited, i, j):
        if (0<=i<len(grid)) and (0<=j<len(grid[0])) and not visited[i][j] and grid[i][j] == '1':
            visited[i][j] = True
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                self.DFS(grid, visited, i+dr, j+dc)

這樣的時間複雜度是 O(N) (要把整個二維陣列走一遍)，空間複雜度是O(N) (要儲存整個二維陣列)