岛屿数量

class Solution:
    def solve(self , grid ):
        def dfs(i, j, grid, lut):
            q = [(i,j)]
            while len(q) > 0:
                cur = q.pop() 
                lut.add(cur) 
                i, j = cur
                if i > 0 and grid[i-1][j] == '1' and (i-1,j) not in lut: 
                    q.append((i-1,j))
                if j > 0 and grid[i][j-1] == '1' and (i,j-1) not in lut: 
                    q.append((i,j-1))
                if i < len(grid) - 1 and grid[i+1][j] == '1' and (i+1,j) not in lut: 
                    q.append((i+1,j))
                if j < len(grid[0]) - 1 and grid[i][j+1] == '1' and (i,j+1) not in lut: 
                    q.append((i,j+1))
        if len(grid) == 0: return 0
        lut = set()
        ans = 0
        for i,row in enumerate(grid):
            for j,v in enumerate(row):
                if v == '1' and (i,j) not in lut:
                    ans += 1
                    dfs(i, j, grid, lut)
        
        return ans

#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
class Solution:
    def dfs(self, grid, i, j, height, width):
        grid[i][j] = 0
        if i > 0 and grid[i - 1][j]:
            grid[i - 1][j] = 0
            self.dfs(grid, i - 1, j, height, width)
        if j > 0 and grid[i][j - 1]:
            grid[i][j - 1] = 0
            self.dfs(grid, i, j - 1, height, width)
        if j + 1 < width and grid[i][j + 1]:
            grid[i][j + 1] = 0
            self.dfs(grid, i, j + 1, height, width)
        if i + 1 < height and grid[i + 1][j]:
            grid[i + 1][j] = 0
            self.dfs(grid, i + 1, j, height, width)

    def solve(self, grid):
        # write code here
        height = len(grid)
        width = len(grid[0])
        for i in range(height):
            for j in range(width):
                grid[i][j] = int(grid[i][j])
        total_num = 0
        for i in range(height):
            for j in range(width):
                if grid[i][j]:
                    total_num += 1
                    self.dfs(grid, i, j, height, width)
        return total_num

class Solution:
    def solve(self , grid ):
        # write code here
        if not grid:
            return 0
        
        def dfs(i, j):
            grid[i][j] = '0'
            for x, y in [(i-1,j), (i+1,j), (i, j-1), (i, j+1)]:
                if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                    dfs(x, y)
        
        m, n = len(grid), len(grid[0])
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    res += 1
                    dfs(i, j)
        return res

class Solution:
    def solve(self , grid ):
        # write code here
        if not grid:
            return 0
        cnt = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    cnt += 1
        return cnt
            

    def dfs(self, 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]!='1':
            return
        grid[i][j] = '2'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)