マトリックス内のいくつかの要素をチェックするプログラムは、Pythonでサイクルを形成するかどうか

2次元行列があるとします。あるセルから開始して、同じ値の隣接するセル（上、下、左、右）を移動し、同じ開始点に戻ることができるかどうかを確認する必要があります。最後に訪れたセルを再訪することはできません。

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

2秒後にサイクルを形成できるため、出力はTrueになります。

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

• R：=行列の行数
• C：=行列の列数
• vis：=サイズR x Cの行列を作成し、Falseで埋めます
• 関数dfs（）を定義します。これが定着します
• stack：=2つの要素がrootとnullのスタック
• vis [root [0]、root [1]]：=True
• スタックが空でない間は、
  • [v、prev]：=スタックの最上位要素、およびスタックからポップ
  • vの各ネイバーwについて、実行します
    • wがprevと同じでない場合、
      • vis [w [0]、w [1]]がfalseの場合、
        • vis [w [0]、w [1]]：=True
        • [w、v]をスタックにプッシュします
    • それ以外の場合、
      • Trueを返す
• Falseを返す
• メインの方法から次の手順を実行します。
• 0からR-1の範囲のiの場合、do
  • 0からC-1の範囲のjの場合、do
    • vis [i、j]がfalseの場合、
      • dfs（（i、j））がtrueの場合、
        • Trueを返す
• Falseを返す

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

例

class Solution:
   def solve(self, matrix):
      R = len(matrix)
      C = len(matrix[0])

      def get_neighbors(i, j):
         val = matrix[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] == val:
               yield ii, jj

      vis = [[False] * C for _ in range(R)]

      def dfs(root):
         stack = [(root, None)]
         vis[root[0]][root[1]] = True
         while stack:
            v, prev = stack.pop()
            for w in get_neighbors(*v):
               if w != prev:
                  if not vis[w[0]][w[1]]:
                     vis[w[0]][w[1]] = True
                     stack.append((w, v))
                  else:
                     return True
         return False

      for i in range(R):
         for j in range(C):
            if not vis[i][j]:
               if dfs((i, j)):
                  return True
      return False
     
ob = Solution()
matrix = [
   [2, 2, 2, 1],
   [2, 1, 2, 1],
   [2, 2, 2, 1]
]
print(ob.solve(matrix))

入力

[  
[2, 2, 2, 1],  
[2, 1, 2, 1],  
[2, 2, 2, 1] ]

出力

True