How many ways

這是一個簡單的生存遊戲，你控制一個機器人從一個棋盤的起始點(1,1)走到棋盤的終點(n,m)。遊戲的規則描述如下：

1.機器人一開始在棋盤的起始點并有起始點所标有的能量。

2.機器人隻能向右或者向下走，并且每走一步消耗一機關能量。

3.機器人不能在原地停留。

4.當機器人選擇了一條可行路徑後，當他走到這條路徑的終點時，他将隻有終點所标記的能量。

如上圖，機器人一開始在(1,1)點，并擁有4機關能量，藍色方塊表示他所能到達的點，如果他在這次路徑選擇中選擇的終點是(2,4) 點，當他到達(2,4)點時将擁有1機關的能量，并開始下一次路徑選擇，直到到達(6,6)點。

我們的問題是機器人有多少種方式從起點走到終點。這可能是一個很大的數，輸出的結果對10000取模。

Input

第一行輸入一個整數T,表示資料的組數。

對于每一組資料第一行輸入兩個整數n,m(1 <= n,m <= 100)。表示棋盤的大小。接下來輸入n行,每行m個整數e(0 <= e < 20)。

Output

對于每一組資料輸出方式總數對10000取模的結果.

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. 狀态表示：

   f[x][y] //表示以(x,y)為起點，走到終點(n,m)有多少種走法

2. 狀态計算：我們可以用dfs來周遊所有路徑，同時用上記憶化搜尋來避免重複計算。

ac代碼：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <iomanip>
#define LL long long
using namespace std;
const int N=105,mod=10000;
int n,m;
int a[N][N],f[N][N];
int dfs(int x,int y)
{
	if(f[x][y]!=-1) return f[x][y]; //記憶化,如果f[x][y]已經被計算過了
	f[x][y]=0;                      //那麼跳過計算
	for(int i=0;i<=a[x][y];i++)     //周遊目前點(x,y)的能量所能到達的
	for(int j=0;j<=a[x][y]-i;j++)   //所有點
	{
		if(x+i>=1&&x+i<=n&&y+j>=1&&y+j<=m) //保證(x+i,y+j)沒有越界
		f[x][y]=(f[x][y]+dfs(x+i,y+j))%mod;//遞歸求解
	}
	return f[x][y];
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		cin>>a[i][j];
		memset(f,-1,sizeof f);  //初始化
	    f[n][m]=1;
	    dfs(1,1);
	    cout<<f[1][1]<<endl;    //f[1][1]即為正确答案
	}
	return 0;
}