Pythonで最大長のスネークシーケンスを見つける

数字のグリッドがあるとします。ヘビのシーケンスを見つけて返す必要があります。複数のスネークシーケンスがある場合は、1つだけを返します。スネークシーケンスはグリッド内の隣接する数字を使用して作成されることがわかっているため、各数字について、右側の数字またはその下の数字は+1または-1の値になります。したがって、現在の値がグリッドセル（a、b）にある場合、その数値が±1の場合は右（a、b + 1）に移動でき、その数値が±1の場合は下（a + 1、b）に移動できます。

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

その場合、出力は6、シーケンス-10（0、0）から9（1、0）から8（1、1）から7（1、2）から6（1、3）から7（2、3）になります。 〜8（3、3）

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

• 関数get_path（）を定義します。これには、グリッド、マット、i、jが必要です

• パス：=新しいリスト

• pt：=ポイント[i、j]

• パスの最後にptを挿入します

• grid [i、j]が0でない場合は、実行してください

  • i> 0で、grid [i、j]-1がgrid[i-1、j]と同じである場合、

    • pt：=[i-1、j]

    • パスの最後にptを挿入します

    • i：=i-1

  • それ以外の場合、j> 0でgrid[i、j]-1がgrid[i、j-1]と同じである場合、

    • pt：=[i、j-1]

    • パスの最後にptを挿入します

    • j：=j-1

• リターンパス

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

• lookup：=サイズM x Nのグリッドを作成し、0で塗りつぶします

• length_max：=0、max_row：=0、max_col：=0

• 0からMの範囲のiの場合、実行

  • 0からNの範囲のjについては、次のようにします

    • iまたはjがゼロ以外の場合、

      • （i>0anおよび|grid[i-1、j] --grid [i、j] |が1の場合、

        • lookup [i、j] =lookup [i、j]、lookup [i-1、j] + 1）の最大値

        • length_max

          • length_max：=lookup [i、j]

          • max_row：=i

          • max_col：=j

      • （j>0かつ|grid [i、j-1] --grid [i、j] |が1の場合、

        • length_max

        • lookup [i、j] =lookup [i、j]、lookup [i、j-1] + 1）の最大値

          • length_max：=lookup [i、j]

          • max_row：=i

          • max_col：=j

• length_maxを表示

• パス：=get_path（lookup、grid、max_row、max_col）

• パス内のすべての要素を逆の順序で印刷します

例

＆mius;

M = 4
N = 4
def get_path(grid, mat, i, j):
   path = list()
   pt = [i, j]
   path.append(pt)
   while (grid[i][j] != 0):
      if (i > 0 and grid[i][j]-1 == grid[i-1][j]):
         pt = [i-1, j]
         path.append(pt)
         i -= 1
      elif (j > 0 and grid[i][j]-1 == grid[i][j-1]):
         pt = [i, j-1]
         path.append(pt)
         j -= 1
   return path
def get_sequence(grid):
   lookup = [[0 for i in range(N)] for j in range(M)]
   length_max = 0
   max_row = 0
   max_col = 0
   for i in range(M):
      for j in range(N):
         if (i or j):
            if (i > 0 and
               abs(grid[i-1][j] - grid[i][j]) == 1):
                  lookup[i][j] = max(lookup[i][j],lookup[i-1][j] + 1)
                  if (length_max < lookup[i][j]):
                     length_max = lookup[i][j]
                     max_row = i
                     max_col = j
                  if (j > 0 and
                     abs(grid[i][j-1] - grid[i][j]) == 1):
                     lookup[i][j] = max(lookup[i][j],lookup[i][j-1] + 1)
                     if (length_max < lookup[i][j]):
                        length_max = lookup[i][j]
                        max_row = i
                        max_col = j
   print("Maximum length:", length_max)
   path = get_path(lookup, grid, max_row, max_col)
   print("Sequence is:")
   for ele in reversed(path):
   print(grid[ele[0]][ele[1]], " [", ele[0], ", ", ele[1], "]", sep = "")
grid = [
   [10, 7, 6, 3],
   [9, 8, 7, 6],
   [8, 4, 2, 7],
   [2, 2, 2, 8]]
get_sequence(grid)

入力

[[10, 7, 6, 3],
[9, 8, 7, 6],
[8, 4, 2, 7],
[2, 2, 2, 8]]

出力

Maximum length: 6
Sequence is:
10 [0, 0]
9 [1, 0]
8 [1, 1]
7 [1, 2]
6 [1, 3]
7 [2, 3]
8 [3, 3]