岛屿数量

# 深度优先搜索
class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        grid = [[int(i) for i in sub] for sub in grid]
        if not grid:
            return 0

        def dfs(grid, i, j):
            if i < 0&nbs***bsp;j < 0&nbs***bsp;i >= len(grid)&nbs***bsp;j >= len(grid[0])&nbs***bsp;grid[i][j] == 0:
                return
            grid[i][j] = 0  # 将访问过的陆地标记为0，避免重复访问
            # 继续搜索相邻的陆地
            dfs(grid, i + 1, j)
            dfs(grid, i - 1, j)
            dfs(grid, i, j + 1)
            dfs(grid, i, j - 1)

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    count += 1  # 每找到一个新的岛屿，计数器加1
                    dfs(grid, i, j)
        return count

def find_block(grid, ind):
    i, j = ind
    grid[i][j] = 0
    if i - 1 >= 0:
        if grid[i - 1][j] == '1':
            grid[i - 1][j] = 0
            grid = find_block(grid, (i - 1, j))
    if i + 1 <= len(grid) - 1:
        if grid[i + 1][j] == '1':
            grid[i + 1][j] = 0
            grid = find_block(grid, (i + 1, j))
    if j - 1 >= 0:
        if grid[i][j - 1] == '1':
            grid[i][j - 1] = 0
            grid = find_block(grid, (i, j - 1))
    if j + 1 <= len(grid[0]) - 1:
        if grid[i][j + 1] == '1':
            grid[i][j + 1] = 0
            grid = find_block(grid, (i, j + 1))
    return grid


class Solution:
    def solve(self, grid) -> int:
        if len(grid) == 0:
            return 0
        num = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                ele = grid[i][j]
                if ele == '1':
                    grid = find_block(grid, (i, j))
                    num += 1
        return num

# 首先遍历每个点，如果当前点为1，则将岛屿数量加1，并以当前点为起点进行深度优先搜索，将所有与当前点联通的1标记为0，表示已经访问过。最后返回岛屿数量。
class Solution:
    def find(self,grid, r, c):
        # 当前的点标记为0
        grid[r][c] = 0
        row = len(grid)
        col = len(grid[0])
        # 遍历周围的点, 上下左右
        for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]: 
            # 如果不越界并且为1
            if 0<=x<row and 0<=y<col and grid[x][y] == '1':
                self.find(grid, x, y)

    def solve(self, grid: List[List[str]]) -> int:
        row = len(grid)
        col = len(grid[0])
        res = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1':
                    res += 1
                    self.find(grid, i, j)
        return res

#



# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组
# @return int整型
#
class Solution:
    def solve(self, grid: list[list[str]]) -> int:
        # write code here
        """
        从左到右依次遍历矩阵
        定义初始状态的矩阵岛屿数量为0
        """

        count = 0

        def bfs(i, j):
            res = []
            res.append([i, j])
            #定义方向,分别将横坐标和纵坐标与direction中的每个方向键相加进行判断该方向是陆地还是水
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            while res:
                element= res.pop(0)
                i, j=element[0], element[1]
                grid[i][j] = "0"
                for x in directions:
                    n = i + x[0]
                    m = j + x[1]
                    #筛选符合条件的1，加入到res中，等待下一步遍历该方向的四个方向，符合条件满足2点，第一点是横纵坐标得在0和 最大值之间包括0，不包括最大值
                    if 0 <= n < len(grid) and 0 <= m < len(grid[0]):
                        if grid[n][m] == "1":
                            res.append([n, m])
        #遍历整个grid，有1就从该入口进入，进行一轮的广度优先遍历，同时岛屿的数量加1
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    count += 1

                    # 搜索矩阵的四个方向进行广度优先搜索
                    bfs(i, j)
        return count

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组
# @return int整型
#
from typing import List
class Solution:
    def trackback(self,grid,i,j,visited):
        if i < 0 &nbs***bsp;i >= len(grid)&nbs***bsp;j < 0&nbs***bsp;j >= len(grid[0])&nbs***bsp;grid[i][j] != 1:
            return 
        elif grid[i][j] == 1 and visited[i][j] == False:
            visited[i][j] = True      #跳进这和函数满足值为1，将visited设置为True
            grid[i][j] = 0
            self.trackback(grid,i+1,j,visited)    #注意缩进，
            self.trackback(grid, i - 1, j, visited)
            self.trackback(grid, i , j - 1, visited)
            self.trackback(grid, i, j + 1, visited)
    def solve(self , grid: List[List[str]]) :
        count = 0
        global visited
        visited = []    #全局变量
        visited = [[False for i in range(len(grid))] for j in range(len(grid[0]))]  #不要写成乘法的浅拷贝
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1 and visited[i][j] == False:
                    self.trackback(grid,i,j,visited)
                    count += 1
        return count

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
class Solution:
    def visit(self, varr: List[List[int]], grid: List[List[str]], x: int, y: int) -> int:
        if varr[x][y] == 1&nbs***bsp;grid[x][y] == '0':
            return
        varr[x][y] = 1
        if y+1 < len(grid[0]):
            self.visit(varr, grid, x, y + 1)
        if x + 1 < len(grid):
            self.visit(varr, grid, x + 1, y)
        if y - 1 >= 0:
            self.visit(varr, grid, x, y - 1)
        if x - 1 >= 0:
            self.visit(varr, grid, x - 1, y)

    def solve(self, grid: List[List[str]]) -> int:
        varr = [[0] * len(grid[0]) for i in grid]
        ret = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1' and varr[i][j] == 0:
                    self.visit(varr, grid, i, j)
                    ret = ret +1
        return ret

    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=='1':
                    count+=1
                    self.dfs(grid,i,j)
        return count
    def dfs(self,grid,i,j):
        if i<0&nbs***bsp;i>=len(grid)&nbs***bsp;j<0&nbs***bsp;j>=len(grid[0])&nbs***bsp;int(grid[i][j]) == 0:
            return 
        grid[i][j] = '0';
        self.dfs(grid,i+1,j)
        self.dfs(grid,i-1,j)
        self.dfs(grid,i,j+1)
        self.dfs(grid,i,j-1)