岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出：1
示例 2：

输入：grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出：3

---

深度优先遍历

遍历网格中的每个元素，如果为”1”，则答案ans计数加1，
同时启动深度优先遍历，将上下左右四个方向的连接元素全部标记为非”1”
遍历下一个元素

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(grid, row, column):
            # 标记着色
            grid[row][column] = ans
            # 上
            if row>0 and grid[row-1][column] == "1":
                dfs(grid, row-1, column)
            # 下
            if row < rows-1 and grid[row+1][column] == "1":
                dfs(grid, row+1, column)
            # 左
            if column>0 and grid[row][column-1] == "1":
                dfs(grid, row, column-1)
            # 右
            if column<columns-1 and grid[row][column+1] == "1":
                dfs(grid, row, column+1)

        rows = len(grid)
        columns = len(grid[0])
        ans = 0
        for i in range(rows):
            for j in range(columns):
                if grid[i][j] == "1":
                    ans += 1
                    dfs(grid, i, j)
        # print(grid)
        return ans

广度优先搜索

这个就是最直观的思路，
用一个队列存储已访问的节点，然后出队列的时候，将其上下左右方向”连通”(即值为1)的元素放入队列

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

        queue = collections.deque()
        for i in range(rows):
            for j in range(columns):
                if grid[i][j] == "1":
                    ans += 1
                    queue.append((i, j))
                    grid[i][j] = ans
                    queue.append((i, j))
                    while queue:
                        row, column = queue.popleft()
                        if row>0 and grid[row-1][column] == "1":
                            queue.append((row-1, column))
                            grid[row-1][column] = ans
                        if row < rows-1 and grid[row+1][column] == "1":
                            queue.append((row+1, column))
                            grid[row+1][column] = ans
                        if column>0 and grid[row][column-1] == "1":
                            queue.append((row, column-1))
                            grid[row][column-1] = ans
                        if column<columns-1 and grid[row][column+1] == "1":
                            queue.append((row, column+1))
                            grid[row][column+1] = ans
        # print(grid)
        return ans

        

并查集

TODO