見注釋

"""
# 參考題解排在第四的解法。
# see: https://leetcode-cn.com/problems/number-of-islands/solution/shen-du-you-xian-sou-suo-xi-wang-da-jia-xi-huan-by/
# 然后自己再來嘗試一下。
"""
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        """
        通過這道題，我學(xué)到了: 二維數(shù)組盡量不要使用 pop(0)，而要盡量使用　pop(),本題我就卡在第20行。
        （也想借鑒評(píng)論區(qū)　使用　visited = set(), 但是最終結(jié)果不正確。)
        因?yàn)槟隳玫袅说谝粋€(gè)元素，那么后面所有的元素索引都要修改。那樣的話，效率非常低下。

        這個(gè)flood 函數(shù)，目就算把一塊陸地四周與之相連的部分都變成不相干的部分。作為后面排除來用。
        """
        # 評(píng)論區(qū)深度優(yōu)先大多使用的都是遞歸，我還是覺得遍歷比較容易理解一些。
        def flood(i, j):
            # 這里有人用 collections.deque(), queue.Queue()
            stack = [(i, j)]
            # stack = deque([i, j]) # 解包的時(shí)候報(bào)錯(cuò)。
            # 如果當(dāng)前這個(gè)格子是 "1",那就把它變成"2",
            # 然后檢查它的上下左右，如果它的上下左右等于"1",那就加入到隊(duì)列當(dāng)中。
            while stack:
                i, j = stack.pop()
                if grid[i][j] == "1":
                    grid[i][j] = "2"
                # 需要添加邊界。
                # 上方
                if i > 0 and grid[i-1][j] == "1":
                    stack.append([i-1, j])
                # 下方　
                if i+1 < len(grid) and grid[i + 1][j] == "1":
                    stack.append([i + 1, j])
                # 左側(cè)
                if j > 0 and grid[i][j-1] == "1":
                    stack.append([i, j-1])
                # 右側(cè)
                if j+1 < len(grid[i]) and grid[i][j + 1] == "1":
                    stack.append([i, j + 1])
                # print(grid)

        ret = 0
        for m in range(len(grid)):
            for n in range(len(grid[m])):
                if grid[m][n] == "1":
                    ret += 1
                    flood(m, n)
        return ret