「青い橋の杯」深さ優先探索 - 大地の宮殿での宝探し

説明

ダンジョンには宝物庫があります。各マスには宝が1つずつ入っています。各宝物には値が付いています。ダンジョンの入り口は左上、出口は右下です。明は地下宮殿の入り口に連れて行かれ、王様から右か下にしか歩かないように言われます。あるマス目を通り抜けたとき、そのマス目にある宝物の価値が、明の手にある宝物の価値よりも高ければ、明はその宝物を拾うことができます。明が出口にたどり着いたとき、明の手の中にちょうどK個の宝物があれば、明に渡すことができます。与えられた状況でk個の宝物を手に入れるために、Mingはいくつの異なる行動をとることができるかを考えてください。

データ形式

空白で区切られた3つの整数の行を入力してください： n m k . 次にn行のデータがあり、それぞれm個の整数Ciでこのグリッド上の宝物の値を表します。

ちょうどk個の宝物を取るための行動コースの数を表す整数を出力してもらいます。この数は大きいかもしれないので、1000000007でモデル化した結果を出力してください。

例えば、入力する：
2 2 2
1 2
2 1
プログラムは出力すべきである：
2
再び、例えば、入力する：
2 3 2
1 2 3
2 1 5
プログラムは出力すべきである：
14

コードの実装：

#include <iostream>
#include<cstring>
using namespace std;
const int MAX=55;
const int K=15;
const int MOD=1000000007;
int n,m,k;
int map[MAX][MAX];
int dp[MAX][MAX][K][K];
/*dp[x][y][num][max]=nx,yの位置にいるとき、手に持っている宝物の総数を表す。
最も大きな値を持つものをmaxとし、この位置から終点までのフェッチ方法はn通りある*/ 
int dfs(int x,int y,int num,int maxValue)
{
 if(dp[x][y][num][maxValue+1]!=-1)
 return dp[x][y][num][maxValue+1];
 if(x==n && y==m){
 if(num==k || num==k-1&&map[x][y]>maxValue)
 return 1;
 return 0;
 }
 long long sum=0;
 if(x+1<=n){
 if(map[x][y]>maxValue)
 sum+=dfs(x+1,y,num+1,map[x][y]);
 sum+=dfs(x+1,y,num,maxValue);
 }
 if(y+1<=m){
 if(map[x][y]>maxValue)
 sum+=dfs(x,y+1,num+1,map[x][y]);
 sum+=dfs(x,y+1,num,maxValue);
 }
 return dp[x][y][num][maxValue+1]=sum%MOD;
}
int main() {
 cin>>n>>m>>k;
 for(int i=1;i<=n;i++)
 for(int j=1;j<=m;j++)
 cin>>map[i][j];
 memset(dp,-1,sizeof(dp));
 dfs(1,1,0,-1);
 cout<<dp[1][1][0][0]<<endl;
 return 0;
}