Pythonの2Dグリッドでサイクルを検出するプログラム

サイズmxnのグリッドと呼ばれる文字の2D配列が1つあるとします。内部のサイクルを検出できるかどうかを確認する必要があります。ここで、サイクルとは、同じ位置で開始および終了するグリッド内の長さ4以上のパスです。現在のセルの値が同じである場合、4つの方向（上、下、左、または右）に移動でき、一部のセルに再度アクセスすることはできません。

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

緑のセルがサイクルを形成しているため、出力はTrueになります。

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

• 白：=0、灰色：=1、黒：=2

• R：=グリッドの行数

• C：=グリッドの列数

• color：=空のマップ。デフォルト値は0です

• 関数dfs（）を定義します。これには、r、c、pr：=-1、pc：=-1

  が必要です。

• color [r、c]：=GRAY

• diの各ペア（x、y）について、実行します

  • （nr、nc）：=（r + x、c + y）

  • 0 <=nr>

    • color [nr、nc]がWHITEと同じ場合、

      • dfs（nr、nc、r、c）がtrueの場合、

        • Trueを返す

      • それ以外の場合、color [nr、nc]がGRAYと同じである場合、

        • Trueを返す

    • color [r、c]：=BLACK

    • Falseを返す

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

    • 0からR-1の範囲のrの場合、実行

      • 0からC-1の範囲のcの場合、実行

        • color [r、c]がWHITEと同じ場合、

          • dfs（r、c）が真の場合、

            • Trueを返す

• Falseを返す

例

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

from collections import defaultdict
di = [(0,1),(1,0),(0,-1),(-1,0)]
def solve(grid):
   WHITE,GRAY,BLACK = 0 ,1 ,2
   R,C = len(grid),len(grid[0])

   color = defaultdict(int)

   def dfs(r,c,pr=-1,pc=-1):
      color[r,c] = GRAY
      for x,y in di:
         nr,nc = r+x,c+y
         if (0<=nr<R and 0<=nc<C and grid[r][c] == grid[nr][nc] and (nr,nc)!=(pr,pc)):
            if color[nr,nc]==WHITE:
               if dfs(nr,nc,r,c):
                  return True
            elif color[nr,nc] == GRAY:
               return True

      color[r,c] = BLACK
      return False

   for r in range(R):
      for c in range(C):
         if color[r,c] == WHITE:
            if dfs(r,c):
               return True
   return False
matrix = [["m","m","m","p"],["m","k","m","m"],["m","m","s","m"],["f","m","m","m"]]
print(solve(matrix))

入力

7, [5,1,4,3]

出力

True