#深度优先搜索题目

class Solution:  
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        row=len(grid)
        col=len(grid[0])
        count=0
        def dfs(i,j):
            grid[i][j]=0 变为0
            for x,y in [[-1,0],[1,0],[0,-1],[0,1]]:#列表里列表，循环里面的x，y值
                tmp_i=i+x
                tmp_j=j+y
                if 0<=tmp_i<row and 0<=tmp_j<col and grid[tmp_i][tmp_j]=="1": #确立相关条件，确保未出界，而且旁边的值也为1
                    dfs(tmp_i,tmp_j) #旁边的值深入
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":#确立某一个值为1
                    dfs(i,j)#进入函数
                    count+=1#区域块加一
        return count

#广度优先搜索
他跟深度的区别在于，深度是一层层找，第二层找到后有可能第一层还有未发现的值。而它先找到最近的相关的部分值
因此需要引入队列，但是没有深度好

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        from collections import deque
        if not grid: return 0
        row = len(grid)
        col = len(grid[0])
        cnt = 0

        def bfs(i, j):
            queue = deque()#引入队列
            queue.appendleft((i, j))#左边加入队列
            grid[i][j] = "0"
            while queue:
                i, j = queue.pop()#输出最后一个i，j
                for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                    tmp_i = i + x
                    tmp_j = j + y
                    if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":#满足相关条件
                        grid[tmp_i][tmp_j] = "0"
                        queue.appendleft((tmp_i, tmp_j))#添加值但首先循环不断向左边添加，直到（i,j）完成之后，进行相关的下一个

        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    bfs(i, j)
                    cnt += 1
        return cnt