LeetCode解題の心得-島の数(python)

タイトル
「1」(陸地)と「0」(水)からなる2次元メッシュを与え,島の数を計算した.1つの島は水に囲まれ、水平方向または垂直方向に隣接する陸地で接続されている.グリッドの4つのエッジが水で囲まれていると仮定できます.
例1:
入力:11110 11010 11000 00000
出力:1
例2:
入力:11000 11000 0010000011
出力:3
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/number-of-islands著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
構想
幅優先探索思想を用いて,1つのルートノード(値1をとる)が隣接する(ここでは水平または垂直方向に隣接する1を指す)ノードをすべてキューに入れ,キュー内のすべてのノードを遍歴して同様の操作を行い,キューから取り出したノードごとにその値を0にしてアクセスしたことを示す.外層スリーブの2つのループは、2次元配列を巡回するために使用され、ルートノードが発見されるたびに幅優先検索が開始され、numsに1を加え、numsが島の数であることを返します.
1.幅優先探索(BFS)
時間複雑度O(n*m),空間複雑度O(min(n,m)),94%を破った

class Solution:
    def __init__(self):
        self.queue = []
        self.visited = []
        self.nums = 0
        
    def numIslands(self,  grid: List[List[str]]) -> int:
        if grid == []:
            return 0
        x_len = len(grid)
        y_len = len(grid[0])
        for i in range(x_len):
            for j in range(y_len):
                if grid[i][j] == '1':
                    self.queue.append((i,j))
                    grid[i][j] = '0'
                    self.nums += 1
                    while self.queue:
                        x,y = self.queue.pop(0)
                        if (x-1>=0) and (grid[x-1][y] == '1'):
                            self.queue.append((x-1,y))
                            grid[x-1][y] = '0'
                        if (x+1<x_len) and (grid[x+1][y] == '1'):
                            self.queue.append((x+1,y))
                            grid[x+1][y] = '0'
                        if (y-1>=0) and (grid[x][y-1] == '1'):
                            self.queue.append((x,y-1))
                            grid[x][y-1] = '0'
                        if (y+1<y_len) and (grid[x][y+1] == '1'):
                            self.queue.append((x,y+1))
                            grid[x][y+1] = '0'
        return self.nums

2.深さ優先探索(DFS)
「ウイルス」を伝播するためのcov関数を定義し、これもcovと呼ばれる理由であり、恐れている.jpg 1は健常者、0は感染者が最初からgridを遍歴し、元素=1のとき、ここの座標をcovに伝達し、ウイルスはDFSを通じて伝播し、その近くが「0」になるまで伝播を停止する.統計はcovを何回か呼び出して、いくつかの島(いくつかの健康な人の集団)を代表します
時間複雑度O(n*m),空間複雑度O(n*m)が94%を破った

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
    
        def cov(node:list):
            i, j = node
            if i-1 >= 0 and grid[i-1][j] == '1': 
                grid[i-1][j] = '0'
                cov([i-1,j])
            if i+1 < len(grid) and grid[i+1][j] == '1':
                grid[i+1][j] = '0'
                cov([i+1,j])
            if j-1 >= 0 and grid[i][j-1] == '1':
                grid[i][j-1] = '0'
                cov([i,j-1])
            if j+1 < len(grid[0]) and grid[i][j+1] == '1':
                grid[i][j+1] = '0'
                cov([i,j+1])
            
        nums = 0
        if grid == []:
            return 0
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if grid[x][y] == '1':
                    nums += 1
                    cov([x, y])
        
        return nums