Leetcode題解 Python：四月挑戰DAY17 Number of Islands

給一個二維串列，”1″代表是陸地，”0″則為水，周圍(超出範圍)都是水，每個不相連的陸地為一塊島，回傳該二維串列有幾塊島？

這題若用迴圈，要如何判定當前遇到的”1″是獨立的島嶼？是否曾經有找過？

使用 memo 去記錄已經搜尋過的”1″，並且遇到”1″的時候用遞迴函數再往四周找出所有鄰近的”1″

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
        landNums = 0
        memo = set()
        rows, cols = len(grid), len(grid[0])

        def search(y,x):
            if y == rows or y < 0 or x == cols or x < 0:
                return
            if (y,x) in memo: return
            else: memo.add((y,x))
            if grid[y][x] == "1":
                search(y-1,x)
                search(y+1,x)
                search(y,x-1)
                search(y,x+1)

        for y in range(rows):
            for x in range(cols):
                if (y,x) not in memo and grid[y][x] == "1":
                    search(y,x)   
                    landNums += 1
          
        return landNums

如果想省點空間，把傳入的二維串列當成 memo 使用也是一種選擇，還能稍微加速。