Pythonの特定のマトリックスから収集できるコインの最大量を見つけるためのプログラム

行列[r、c]がそのセル内のコインの数を表す2D行列があるとします。どの位置からでも始められ、4つの方向（斜めではなく上、下、左、右）のいずれかを動かしてコインを集めたいと思います。セルに移動すると、コインが収集され、そのセルの値は0になります。0コインのセルにアクセスすることはできません。収集できるコインの最大数を見つける必要があります。

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

パス2−> 3 −> 6 −> 4 −> 3

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

• 行列が空の場合、

  • 0を返す

• n：=マトリックスの行数、m：=マットの列数

• x：=[-1、1、0、0]のようなリスト、y：=[0、0、-1、1]のようなリスト

• 関数util（）を定義します。これにはa、bが必要です

• ret：=0

• 0から3の範囲のkの場合、実行

  • （t1、t2）：=（x [k] + a、y [k] + b）

  • （t1、t2）が有効なセルの場合、

    • t：=mat [t1、t2]、mat [t1、t2]：=0

    • ret：=retの最大値と（util（t1、t2）+ t）

    • mat [t1、t2]：=t

• retを返す

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

• res：=0

• 0からn− 1の範囲のiの場合、実行

  • 0からm− 1の範囲のjの場合、実行

    • mat [i、j]がゼロ以外の場合、

      • t：=mat [i、j]、mat [i、j]：=0

      • res：=resの最大値と（util（i、j）+ temp）

• 解像度を返す

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

例

class Solution:
   def solve(self, mat):
      if not mat:
         return 0
      n, m = len(mat), len(mat[0])
      x, y = [−1, 1, 0, 0], [0, 0, −1, 1]
      def ok(a, b):
         return 0 <= a < n and 0 <= b < m and mat[a][b]
      def util(a, b):
         ret = 0
         for k in range(4):
            t1, t2 = x[k] + a, y[k] + b
            if ok(t1, t2):
               t, mat[t1][t2] = mat[t1][t2], 0
               ret = max(ret, util(t1, t2) + t)
               mat[t1][t2] = t
            return ret
         res = 0
         for i in range(n):
            for j in range(m):
               if mat[i][j]:
                  temp, mat[i][j] = mat[i][j], 0
                  res = max(res, util(i, j) + temp)
         return res
ob = Solution()
matrix = [
   [2, 4, 3],
   [3, 6, 0],
   [2, 0, 12]
]
print(ob.solve(matrix))

入力

[
[2, 4, 3],
[3, 6, 0],
[2, 0, 12] ]

出力

18