C++でのチェリーピックアップ

N x Nグリッドが1つあるとすると、これはさくらんぼでいっぱいです。各セルには、次のように可能な整数の1つがあります-

• 0-セルが空であるため、通過できることを示します
• 1-セルにチェリーが含まれていることを示します。これを拾い上げて通過させることができます
• -1-セルに道を塞ぐとげが含まれていることを示します

これらのいくつかのルールを使用して、最大数のサクランボを収集する必要があります-

• 位置（0、0）から開始し、有効なパスセルを右または下に移動して（N-1、N-1）で終了します
• セル（N-1、N-1）に到達した後、有効なパスセルを左または上に移動して（0、0）に戻ります。
• チェリーを含むパスセルを通過するときに、それをピックアップすると、セルは空のセルになります（値は0になります）。
• （0、0）と（N-1、N-1）の間に有効なパスがない場合、チェリーを収集することはできません。

したがって、入力が-

出力は、位置（0、0）から開始し、下、下、右、右に進んで（2、2）に到達するため、5になります。ここでは、この1回の旅行で4つのサクランボが拾われ、マトリックスは次のようになります。

次に、左、上、上、左に移動して（0,0）に戻り、もう1つのチェリーを拾います。さくらんぼの総数は5個になります。

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

• サイズの配列ディレクトリを定義します：2 x 2：={{1、0}、{0、1}}
• INF：=10 ^ 9
• サイズが51x51x51の配列dpを定義します。
• 関数solve（）を定義します。これには、r1、c1、c2、1つの2D配列>＆グリッドが必要です。
• n：=グリッドのサイズ、r2：=r1 + c1-c2、ret：=0
• m：=（nがゼロ以外の場合、grid [0]のサイズ、それ以外の場合は0）
• r1<0またはc1<0またはr2<0またはc2<0またはr1>=nまたはr2>=nまたはc1>=mまたはc2>=mの場合、-
  • return -INF
• grid [r1、c1]が-1と同じか、grid [r2、c2]が-1と同じ場合、-
  • return -INF
• r1がr2と同じで、c1がc2と同じで、r1がn-1と同じで、c1がm-1と同じである場合、-
  • return grid [r1、c1]
• dp [r1、c1、c2]が-1に等しくない場合、-
  • return dp [r1、c1、c2]
• ret：=ret + grid [r1、c1]
• r1がr2と同じで、c1がc2と同じ場合、何もしません
• それ以外の場合
  • ret：=ret + grid [r2、c2]
• temp：=-INF
• kを初期化する場合：=0、k <2の場合、更新（kを1つ増やす）、実行-
  • temp：=tempの最大値とsolve（r1 + dir [k、0]、c1 + dir [k、1]、c2 + 1、grid）
  • temp：=tempの最大値とsolve（r1 + dir [k、0]、c1 + dir [k、1]、c2、grid）
• return dp [r1、c1、c2] =ret + temp
• メインの方法から、次の手順を実行します-
• dpに-1を入力
• ret：=resolve（0、0、0、grid）
• 最大0を返し、ret

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

例

#include <bits/stdc++.h>
using namespace std;
int dir[2][2] = {{1, 0}, {0, 1}};
const int INF = 1e9;
class Solution {
public:
   int dp[51][51][51];
   int solve(int r1, int c1, int c2, vector < vector <int> >& grid){
      int n = grid.size();
      int r2 = r1 + c1 - c2;
      int ret = 0;
      int m = n? grid[0].size() : 0;
      if(r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0 || r1 >= n || r2 >= n || c1 >= m || c2 >= m) return -INF;
      if(grid[r1][c1] == -1 || grid[r2][c2] == -1) return -INF;
      if(r1 == r2 && c1 == c2 && r1 == n - 1 && c1 == m - 1)return grid[r1][c1];
      if(dp[r1][c1][c2] != -1) return dp[r1][c1][c2];
      ret += grid[r1][c1];
      if(r1 == r2 && c1 == c2){
         }else ret += grid[r2][c2];
         int temp = -INF;
         for(int k = 0; k < 2; k++){
         temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2 + 1, grid));
         temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2, grid));
      }
      return dp[r1][c1][c2] = ret + temp;
   }
   int cherryPickup(vector<vector<int>>& grid) {
      memset(dp, -1, sizeof(dp));
      int ret = solve(0, 0, 0, grid);
      return max(0, ret);
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,-1},{1,0,-1},{1,1,1}};
   cout << (ob.cherryPickup(v));
}

入力

{{0,1,-1},{1,0,-1},{1,1,1}}

出力

5