Pythonで左上と右下のセルを分割するために必要な壁の数を数えるプログラム

0が空のセルを表し、1が壁を表す2次元バイナリ行列があるとします。左上のセルと右下のセルの間にパスがないように、壁になる必要のあるセルの最小数を見つける必要があります。左上のセルと右下のセルに壁を配置することはできません。斜めにではなく、左右、上下にしか動かせません。

したがって、入力が次のような場合

その場合、出力は2になります

これを解決するには、次の手順に従います-

• R：=行列の行数、C：=行列の列数

• 訪問した：=新しいセット

• tin：=新しいマップ、low：=新しいマップ

• タイマー：=0

• bridge_pts：=新しいセット

• par：=新しいマップ

• src：=ペア（0、0）

• tgt：=ペア（R − 1、C − 1）

• 関数dfs（）を定義します。これにはv、親が必要です

• vを訪問済みとしてマーク

• par [v]：=親、tin [v]：=タイマー、low [v]：=タイマー

• タイマー：=タイマー+ 1

• 子供：=0

• vの隣人ごとに、実行します

  • toが親と同じ場合、

    • 次のイテレーションに行く

  • 訪問した場合は

    • low [v]：=low[v]とtin[to]の最小値

  • それ以外の場合

    • dfs（to、v）

    • low [v]：=low[v]とlow[to]の最小値

    • low [to]> =tin [v]で、親がnullでない場合、

      • vをbridge_ptsに追加

    • 子供：=子供+1

• 親がnullで、子が1より大きい場合、

  • vをbridge_ptsに追加

• 関数bfs（）を定義します。これが定着します

• Q：=単一要素のルートを持つリストを持つ両端キュー

• 訪問：=新しいセットと最初にルートを挿入

• Qが空でない間、実行します

  • v：=Qの最後の要素、次にQから最後の要素を削除

  • vがtgtと同じ場合、

    • Trueを返す

  • vの隣のwごとに、実行します

    • wにアクセスしない場合は、

      • wを訪問済みとしてマーク

      • Qの左側にwを挿入します

• Falseを返す

• メインの方法から、次のようにします-

• dfs（src、null）

• tgtが標準に達していない場合は、

  • 0を返す

• bridge_ptsの各ペア（i、j）について、実行します

  • matrix [i、j]：=1

• bfs（src）がtrueの場合、

  • 2を返す

• 1を返す

理解を深めるために、次の実装を見てみましょう-

例

from collections import deque
class Solution:
   def solve(self, matrix):
      R = len(matrix)
      C = len(matrix[0])
      def get_neighbors(i, j):
         for ii, jj in ((i + 1, j), (i− 1, j), (i, j + 1), (i, j − 1)):
            if 0 <= ii < R and 0 <= jj < C and matrix[ii][jj] == 0:
               yield ii, jj
      visited = set()
      tin = {}
      low = {}
      timer = 0
      bridge_pts = set()
      par = {}
      src = (0, 0)
      tgt = (R− 1, C− 1)
      def dfs(v, parent):
         nonlocal timer
         visited.add(v)
         par[v] = parent
         tin[v] = timer
         low[v] = timer
         timer += 1
         children = 0
         for to in get_neighbors(*v):
            if to == parent:
               continue
            if to in visited:
               low[v] = min(low[v], tin[to])
            else:
               dfs(to, v)
               low[v] = min(low[v], low[to])
               if low[to] >= tin[v] and parent is not None:
                  bridge_pts.add(v)
               children += 1
               if parent is None and children > 1:
                  bridge_pts.add(v)
               def bfs(root):
                  Q = deque([root])
                  visited = set([root])
                  while Q:
                     v = Q.pop()
                     if v == tgt:
                        return True
                     for w in get_neighbors(*v):
                        if w not in visited:
                           visited.add(w)
                           Q.appendleft(w)
                  return False
               dfs(src, None)
               if tgt not in par:
                  return 0
               for i, j in bridge_pts:
                  matrix[i][j] = 1
               if bfs(src):
                  return 2
               return 1
ob = Solution()
matrix = [
   [0, 0, 0, 0],
   [0, 1, 0, 0],
   [0, 1, 1, 0],
   [0, 0, 0, 0],
]
print(ob.solve(matrix))

入力

[
   [0, 0, 0, 0],
   [0, 1, 0, 0],
   [0, 1, 1, 0],
   [0, 0, 0, 0],
]

出力

2