左上から右下のセルから選択してPythonで返すことができるコインの数を見つけるプログラム

3つの可能な値を持つ2D行列があるとします-

• 空のセルの場合は0。

• コインの場合は1。

• 壁の場合は-1。

左上のセルから始めて、右または下の方向にのみ移動して右下のセルに到達することにより、取得できるコインの最大数を見つける必要があります。次に、上方向または左方向に移動するだけで、左上のセルに戻ります。コインを受け取ると、セルの値は0になります。右下のセルに到達できない場合は、0を返します。

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

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

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

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

• 関数util（）を定義します。これにはi、j、k、lが必要です

• iとjがmatの範囲内にない場合、またはmat [i、j]が-1と同じ場合、

  • -inf

    を返します

• kとlがmatの範囲内にない場合、またはmat [k、l]が-1と同じ場合、

  • -inf

    を返します

• i、j、k、lがすべて0の場合、

  • リターンマット[0,0]

• 最高：=−inf

• [（-1、0）、（0、-1）]の各ペア（dx1、dy1）に対して、実行

  • [（-1、0）、（0、-1）]の各ペア（dx2、dy2）について、実行

    • best：=bestとutil（i + dy1、j + dx1、k + dy2、l + dx2）の最大値

• return mat [i、j] +（iがkと同じでない場合は1、それ以外の場合は0）* mat [k、l] + best

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

• 最大値0とutil（n − 1、m − 1、n − 1、m − 1）を返します

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

例

class Solution:
   def solve(self, mat):
      n, m = len(mat), len(mat[0])
      def util(i, j, k, l):
         if not (0 <= i < n and 0 <= j < m) or mat[i][j] == −1:
            return −1e9
         if not (0 <= k < n and 0 <= l < m) or mat[k][l] == −1:
            return −1e9
         if i == 0 and j == 0 and k == 0 and l == 0:
            return mat[0][0]
         best = −1e9
         for dx1, dy1 in [(−1, 0), (0, −1)]:
            for dx2, dy2 in [(−1, 0), (0, −1)]:
               best = max(best, util(i + dy1, j + dx1, k + dy2, l + dx2))
         return mat[i][j] + (i != k) * mat[k][l] + best
      return max(0, util(n − 1, m − 1, n − 1, m − 1))
ob = Solution()
matrix = [
   [0, 1, 1],
   [1, 1, 1],
   [1, −1, 1],
   [0, 1, 1]
]
print(ob.solve(matrix))

入力

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

出力

8