Pythonで解くコイン収集問題：左上から右下への往復移動で取得できる最大コイン数を求めるプログラム

問題の概要

0、1、-1 の3種類の値を含む2次元マトリックス（グリッド）を考えます。各値の意味は次のとおりです。

• 0：何もない空のセル
• 1：コインが置かれたセル
• -1：通過できない壁

左上のセルを出発点として、「右」または「下」方向への移動のみで右下のセルまで進み、そこから今度は「上」または「左」方向への移動のみで左上のセルへ戻ります。この往復移動で収集できるコインの最大数を求めるのが目的です。コインを取得したセルの値は 0 に変わり、同じコインを二度取得することはできません。また、右下のセルに到達できない場合は 0 を返します。

入力例と出力

たとえば、次のようなマトリックスが与えられたとします。

この場合、出力は 8 となります。

解法の考え方

一見すると「行き」と「帰り」の2回の移動を扱う必要がありそうですが、これを「左上から同時に出発する2人の移動」として捉えるとシンプルになります。両者とも「右」か「下」にしか進めないため、片方を行きの経路、もう片方を帰りの経路（逆順）とみなせるのです。

具体的には、以下の手順で解きます。

• n := マトリックスの行数、m := 列数とする
• 4つの引数 i, j, k, l を取る関数 util() を定義する。(i, j) と (k, l) はそれぞれ2人の現在位置を表す
• (i, j) がマトリックスの範囲外、または mat[i][j] が -1（壁）の場合は -inf を返す
• (k, l) が範囲外、または mat[k][l] が -1 の場合も -inf を返す
• i, j, k, l がすべて 0（＝両者がスタート地点にいる）の場合は mat[0][0] を返す
• best := -inf で初期化する
• [(-1, 0), (0, -1)] の各ペア (dx1, dy1) と (dx2, dy2) の組み合わせごとに、best := best と util(i + dy1, j + dx1, k + dy2, l + dx2) の最大値を更新する
• mat[i][j] ＋（i ≠ k のとき 1、それ以外は 0）× mat[k][l] ＋ best を返す。両者が同じセルにいる場合はコインを一度だけカウントする
• メイン処理では、max(0, util(n-1, m-1, n-1, m-1)) を返す

実装例（Python）

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

まとめ

このように、往復の経路探索を「2人が同時に左上から右下へ進む」という形に言い換えることで、再帰的に最適解を求められます。両者が同じセルに重なった場合はコインを一度だけ数える点がポイントです。なお、この実装は素朴な再帰のため入力サイズが大きくなると指数時間がかかるため、(i, j, k, l) をキーにメモ化（キャッシュ）を追加すれば O(n²m²) まで高速化できます。