How many ways(メモリ検索)

How many ways
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4275    Accepted Submission(s): 2499
Problem Description
これは簡単な生存ゲームで、ロボットを1つの碁盤の始点(1,1)から碁盤の終点(n,m)まで制御します.ゲームのルールは以下の通りです.1.ロボットが最初に碁盤の始点にエネルギーを表示し、始点にエネルギーを表示します.2.ロボットは右または下にしか歩けず、一歩ずつエネルギーを消費します.3.ロボットはその場に留まることができません.4.ロボットが実行可能な経路を選択した後、彼がこの経路の終点に着いたとき、彼は終点にマークされたエネルギーしかありません.  上記の図のように、ロボットは最初は(1,1)点で、4単位のエネルギーを持っていて、青いブロックは彼が着くことができる点を示しています.もし彼が今回の経路選択で選択した終点は(2,4)です.
ポイント(2,4)ポイントに到達すると1単位のエネルギーを持ち、(6,6)ポイントに到達するまで次のパス選択を開始します.私たちの問題はロボットが起点から終点までどのように歩くかです.これは大きな数かもしれませんが、出力の結果は10000に対して型を取ります.
 
Input
1行目は、データのグループ数を表す整数Tを入力する.各データのセットの最初の行には、2つの整数n,m(1<=n,m<=100)が入力される.碁盤の大きさを表す.次にn行を入力し、各行m個の整数e(0<=e<20)を入力する.
 
Output
データ出力方式のセット毎に合計10,000を型抜きした結果である.
 
Sample Input
1 6 6 4 5 6 6 4 3 2 2 3 1 7 2 1 1 4 6 2 7 5 8 4 3 9 5 7 6 6 2 1 5 3 1 1 3 7 2
 
Sample Output
3948
标题解:記憶化検索、開始から終点までの方法は1で、前に戻ります;dp[x][y]は、x,yから終点に到達する方法の数を表す.以前検索して直接戻りました.
コード:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int INF=0x3f3f3f3f;
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x)
#define PI(x) printf("%d",x)
#define SD(x,y) scanf("%lf%lf",&x,&y)
#define P_ printf(" ")
const int MOD=10000;
const int MAXN=110;
int dp[MAXN][MAXN],mp[MAXN][MAXN];
typedef long long LL;
int N,M;
int dfs(int x,int y){
	if(dp[x][y]>=0)return dp[x][y];//         ； 
	dp[x][y]=0;
	for(int i=0;i<=mp[x][y];i++)
	for(int j=0;j<=mp[x][y]-i;j++){//    mp[x][y] 
		if(x+i>N||y+j>M)continue;
		 dp[x][y]=(dp[x][y]+dfs(x+i,y+j))%MOD;
	}
	return dp[x][y];
}
int main(){
	int T;
	SI(T);
	while(T--){
		SI(N);SI(M);
		mem(dp,-1);
		for(int i=1;i<=N;i++){
			for(int j=1;j<=M;j++){
				SI(mp[i][j]);
			}
		}
		dp[N][M]=1;
		printf("%d
",dfs(1,1));
	}
	return 0;
}