C++で解く「金鉱で採れる最大のゴールド量を求めるパス」問題

サイズ m × n の金鉱グリッドが与えられます。各マスにはそのマスに含まれるゴールドの量を表す整数が書かれており、0 は空のマスを意味します。以下の条件のもとで、収集できるゴールドの最大量を求めるのがこの問題の目的です。

問題の条件

• マスに到達するたびに、そこにあるすべてのゴールドを回収します。
• 現在位置からは、上下左右のいずれかに1歩移動できます。
• 同じマスは一度しか訪問できません。
• ゴールドが 0 のマスは絶対に訪れてはいけません。

たとえば、入力が [[0,6,0],[5,8,7],[0,9,0]] の場合、答えは 24 になります。これは「9 → 8 → 7」という経路をたどることで最大のゴールドを得られるためです。

アプローチ：DFS（深さ優先探索）による全経路の探索

この問題は、各マスを起点として DFS を実行し、取りうるすべての経路の中から最大値を求めることで解けます。具体的な手順は次のとおりです。

DFS 関数の設計

• dfs(grid, n, m, i, j) というメソッドを作成します。
• 座標 (i, j) がグリッド外に出た場合、または grid[i][j] が -1（訪問済み）や 0（空）の場合は 0 を返します。
• temp := grid[i][j] として現在の値を退避し、cost := grid[i][j] を初期化した上で、grid[i][j] = -1 として訪問済みマークを付けます。
• cost に、4方向（上・下・左・右）への再帰呼び出し結果の最大値を加算します。
• 処理が終わったら grid[i][j] = temp で元の値に戻し（バックトラック）、cost を返します。

メイン関数の流れ

• 行数 n、列数 m を取得し、答え ans = 0 で初期化します。
• すべてのマス (i, j) についてループし、値が 0 以外のマスから dfs を開始して、ans を最大値で更新していきます。
• 最後に ans を返します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int dfs(vector<vector<int>>& grid, int n, int m, int i, int j){
      if(i>=n || j>=m ||i<0||j<0 || grid[i][j]==-1 || grid[i][j] == 0)return 0;
      int temp =grid[i][j];
      int cost = grid[i][j];
      grid[i][j] = -1;
      cost+=max({dfs(grid,n,m,i+1,j),dfs(grid,n,m,i-1,j),dfs(grid,n,m,i,j+1),dfs(grid,n,m,i,j-1)});
      grid[i][j] = temp;
      return cost;
   }
   int getMaximumGold(vector<vector<int>>& grid) {
      int n = grid.size() ;
      int m = grid[0].size();
      int ans = 0;
      for(int i =0;i<n;i++){
         for(int j =0;j<m;j++){
            if(grid[i][j]){
               ans = max(ans,dfs(grid,n,m,i,j));
            }
         }
      }
      return ans;
   }
};
main(){
   vector<vector<int>> v = {{0,6,0},{5,8,7},{0,9,0}};
   Solution ob;
   cout << (ob.getMaximumGold(v));
}

入力例

[[0,6,0],[5,8,7],[0,9,0]]

出力例

24

計算量について

この手法では、各マスを起点に4方向への探索を繰り返すため、最悪計算量は O((m×n) × 4^(m×n)) となります。ただし、実際にはゴールドが 0 のマスや訪問済みマスを枝刈りすることで、多くの場合これより大幅に小さい探索範囲で済みます。バックトラックによってグリッドの状態を毎回復元している点が、この実装の重要なポイントです。