【leetcode】深さ優先検索

面接問題08.10.カラー塗り
面接問題16.19.水域の大きさ
130.囲まれた領域
1219.黄金鉱夫
79.単語検索
 
面接問題08.10.カラー塗り
関数を作成し、多くの画像編集ソフトでサポートされている「色塗り」機能を実現します.
塗りつぶす画像は2次元配列imageで表され、要素は初期色値です.初期座標点の横座標はsr縦座標はscである.塗りつぶしが必要な新しい色はnewColorです.
「周囲領域」とは、色が同じで、上、下、左、右の4つの方向に接続されている場合のいくつかの要素を指す.
新しい色で初期座標点の周囲を塗りつぶし、塗りつぶした画像を返してください.
例:入力:image=[[1,1,1],[1,1,0],[1,0,1]]sr=1,sc=1,newColor=2出力:[[2,2,2],[2,2,0],[2,0,1]]初期座標点は画像の真ん中に位置し,座標(sr,sc)=(1,1)である.初期座標点の周囲の領域で条件を満たすすべての画素点の色が2に変更されます.なお、右下のピクセルは、初期座標点の周囲領域に属していないため、2に変更されていません.
これは非常に単純な深さ優先探索問題であり,所与の点から,その点画素と上下左右4方向で同じ遍歴していない点(これもコード中ifの文の判定条件である)を遍歴し,これらの点の画素を新しい値に変えることを考えている.
dpはアクセス可能かどうかを示し,Trueはアクセス可能であることを示す.

    def floodFill(self, image, sr, sc, newColor):
        m,n = len(image),len(image[0])
        oldcolor = image[sr][sc]
        
        def dfs(i,j):
            if i < 0 or j < 0 or i >=m or j >=n:
                return
            if image[i][j] == oldcolor and dp[i][j]:
                dp[i][j] = False   #     ，   False
                image[i][j] = newColor
                dfs(i-1,j)  #up
                dfs(i+1,j)  #down
                dfs(i,j-1)  #left
                dfs(i,j+1)  #right
        
        dp = [[True for i in range(n)] for j in range(m)] #dp      ，True      
        dfs(sr,sc)
        return image

試験問題16.19.水域の大きさ
土地を表す整数行列landがあります.この行列の各点の値は、対応する場所の標高を表します.値が0の場合は水域を表します.垂直、水平または対角で接続された水域は池である.池の大きさはつながっている水域の個数を指す.マトリクス内のすべての池のサイズを計算する方法を記述し、戻り値を小さいものから大きいものにソートする必要があります.
例:入力:[[0,2,1,0],[0,1,0,1],[1,1,0,1],[0,1,0,1]]出力:[1,2,4]
本問題は前の問題と非常に類似しており,dpを用いて遍歴した点を記録する必要があるが,異なる点は主に,(1)画素充填は上下左右4方向に遍歴するだけで,本問題は斜め対角を考慮する必要がある.(2)画素充填は初期遍歴の位置を与えるが,本題では各点を遍歴する必要があり,まずその点が水域点であるか否かを判断し,その点を中心として1つの水域を遍歴し続け,最終的に水域数を記録する.

    def pondSizes(self, land):
        m,n = len(land),len(land[0])
        self.num = 0
        output = []
        dp = [[True for i in range(n)] for j in range(m)]
        def dfs(i,j):
            if i < 0 or j < 0 or i >=m or j >=n or dp[i][j] == False or land[i][j] != 0:
                return
            dp[i][j] = False
            self.num = self.num + 1
            dfs(i-1,j-1)  #up left
            dfs(i-1,j)  #up
            dfs(i-1,j+1)  #up right
            dfs(i+1,j-1)  #down left
            dfs(i+1,j)  #down
            dfs(i+1,j+1)  #down right
            dfs(i,j-1)  #left
            dfs(i,j+1)  #right
                  
        for i in range(m):
            for j in range(n):
                if dp[i][j] and land[i][j] == 0:
                    dfs(i,j)
                    output.append(self.num)
                    self.num = 0
        output.sort()
        return output

 130. 囲まれた領域
「X」と「O」(アルファベットO)を含む2次元マトリクスが与えられる.「X」に囲まれたすべての領域を見つけ、これらの領域のすべての「O」を「X」で埋めます.
例:
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
X X X X X X X X X X X X X O X X
説明:
囲まれた区間は境界上に存在しない.言い換えれば、どの境界上の「O」も「X」として充填されない.境界上にない、または境界上の「O」に接続されていない「O」は、最終的に「X」として充填されます.2つの要素が水平方向または垂直方向に隣接している場合は、それらを「接続」と呼びます.
本題は前の2題とよく似ている.初めて問題を見ると、前の方法で各点を巡り、Oかどうかを判断し、その後、その点を中心に拡散する可能性があります.しかし、実際には、Oが境界にある限り、このOと水平に垂直な他のOは充填されなくてもよいというより簡単な方法があります.つまり、境界上のすべてのOとそれに接続されたO点を見つけるだけで、これらの点を残すことができます.

class Solution:
    def solve(self, board):
        if not board:
            return
        m,n = len(board),len(board[0])
        dp = [[True for i in range(n)] for j in range(m)]  #True      
        def dfs(i,j):
            if i < 0 or j < 0 or i >=m or j >=n or dp[i][j] == False or board[i][j] != 'o':
                return
            dp[i][j] = False
            dfs(i-1,j)  #up
            dfs(i+1,j)  #down
            dfs(i,j-1)  #left
            dfs(i,j+1)  #right
                 
        for i in range(m):
            if 0 < i 

 1219. 黄金鉱夫
金鉱を開発するには、地質調査学者がこの金鉱の資源分布を明らかにし、m*nの大きさのグリッドgridで表記します.各セルの整数は、このセルの金の数を表します.セルが空の場合は0です.
収益を最大化するために、鉱夫は以下のルールに従って金を採掘する必要があります.
鉱夫がユニットに入るたびに、そのセルのすべての金が収集されます.鉱夫は毎回現在の位置から上下左右の4つの方向に歩くことができる.各セルは1回のみ採掘(入る)ことができます.金の数が0のセルは採掘できません.鉱夫はグリッドのいずれかの金のあるセルから出発したり、停止したりすることができます. 
例1:入力:grid=[[0,6,0],[5,8,7],[0,9,0]]出力:24解釈:[[0,6,0],[5,8,7],[0,9,0]]最も黄金を集めるルートは、9->8->7である.
例2:入力:grid=[[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]出力:28解釈:[[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]最も多くの黄金を集めるルートは、1->2->3->4->5->6->7である.
アルゴリズムの主な流れは次のとおりです.

        
       if       0，      
       else                    （   dfs  ）
                   
     

注意点:

は、各初期遍歴点にあり、改点採掘から遍歴が許可された点を記録するためにdpを申請する.

dfs関数では、ある点を巡回すると、まずこの点のdp値をFalseに設定し、すでに巡回した後、上下左右の巡回を開始する.しかし最後に必ずdp値をTrueに戻すのは遡及のためである.この例grids=[[1,0,7,0,0,0],[2,0,6,0,1,0],[3,5,6,7,4,2],[4,3,1,0,2],[3,0,5,0,20,0]]で、感じてみてください.

class Solution:
    def getMaximumGold(self, grid):
        m,n = len(grid), len(grid[0])  # 、 
        def dfs(a,b):
            if a < 0 or b < 0 or a>= m or b >= n:
                return 0
            if dp[a][b] == False or grid[a][b] == 0:
                return 0 
            dp[a][b] = False   #        
            up = dfs(a-1,b)
            down = dfs(a+1,b)
            left = dfs(a,b-1)
            right = dfs(a,b+1)
            dp[a][b] = True   #!!!!!!!    
            return grid[a][b] + max(up,down,left,right)

        maxvalue = 0         
        for i in range(m):
            for j in range(n):
                # [i,j]          
                if grid[i][j] == 0: #     0，       
                    continue
                print(grid[i][j])
                dp = [[True for k in range(n)] for g in range(m)]  #   [i,j]            
                maxvalue = max(maxvalue, dfs(i,j)) #         
        return maxvalue

79.単語検索
2 Dメッシュと単語を指定して、その単語がメッシュに存在するかどうかを見つけます.
単語はアルファベット順で、隣接するセル内のアルファベットで構成され、「隣接」セルは水平または垂直に隣接するセルである必要があります.同じセル内のアルファベットは繰り返し使用できません.
例:board=['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]
与えられたword="ABCCED"、true与えられたword="SEE"を返し、true与えられたword="ABCB"を返し、falseを返す
前の問題は各点から採掘して得た最大黄金量を計算する必要があり、本題は前の問題に類比することもできる.すなわち、各点から始まり、長さが与えられたwordのすべての単語を列挙し、与えられた単語が私たちが見つけた単語のシーケンスにあるかどうかを判断する.ただし、この問題の特殊性のため、2つの制約を設定できます.

が遍歴したi番目のアルファベットは、与えられたwordのi番目のアルファベットに等しくなければ、直接スキップすることができる.

各アルファベットがwordのアルファベットに等しい場合、すべての再帰を直接飛び出してTrueに戻ることができます.ここではselfを使います.Flagは単語が見つかったかどうかを記録します.例えば、所与のboard=

['A','B','C','E'],['S','F','C','S'],['A','D','E','E']],私たちが探している単語はASAで、board[0][0]:Aから遍歴し、2番目のアルファベットはboard[1][0]:Sまで遍歴し、2番目のアルファベットはboard[2][0]:Aまで遍歴し、このとき直接return Trueができます.つまり、Sの右位置board[1][1]:Fを遍歴する必要はありません.

class Solution:
    def exist1(self, board, word):
        #dp + Flag
        #228 ms	15.2 MB
        m,n = len(board),len(board[0])
        length = len(word)
        self.Flag = False
        dp = [[True for k in range(n)] for g in range(m)]
        
        def digui(s,index,a,b):  
            if a < 0 or b < 0 or a>= m or b >= n or dp[a][b] == False or self.Flag:
                return
            if board[a][b] != word[index]:  #index  word  index   
                return
            s = s + board[a][b] 
            if index == length-1:
                self.Flag = True
                return self.Flag
            index = index + 1
            dp[a][b] = False
            digui(s, index,a-1,b)   # 
            digui(s, index,a+1,b)    # 
            digui(s, index,a,b-1)   # 
            digui(s, index,a,b+1)    # 
            dp[a][b] = True   #!!!!    
        
        for i in range(m):
            for j in range(n):  
                digui('',0,i,j)
                if self.Flag:
                    return self.Flag
        return False

dpの場合はvisitedで代用できます.

    def exist2(self, board, word):
        #visited + Flag
        #280 ms	15 MB
        m,n = len(board),len(board[0])
        length = len(word)
        visited = set()
        self.Flag = False
        
        def digui(s,index,a,b):  
            if a < 0 or b < 0 or a>= m or b >= n or (a,b) in visited or self.Flag:
                return
            if board[a][b] != word[index]:  #index  word  index   
                return
            s = s + board[a][b] 
            if index == length-1:
                self.Flag = True
                return self.Flag
            index = index + 1
            visited.add((a,b))
            digui(s, index,a-1,b)   # 
            digui(s, index,a+1,b)    # 
            digui(s, index,a,b-1)   # 
            digui(s, index,a,b+1)    # 
            visited.remove((a,b))   #!!!!    
        
        for i in range(m):
            for j in range(n):
                digui('',0,i,j)
                if self.Flag:
                    return self.Flag
        return False