题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1978
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100+5;
int G[maxn][maxn],R,C,p=10000;
int d[maxn][maxn];
bool inside(int x,int y){return x>=1&&x<=R&&y>=1&&y<=C;
}
int DP(int x,int y)
{int& ans=d[x][y];if(ans!=0) return ans;if(x==R&&y==C) return ans=1;int n=G[x][y];for(int dx=0;dx<=n;dx++){int ny=y+n-dx,i=x+dx;for(int j=y;j<=ny;j++){if(i==x&&j==y) continue;if(inside(i,j)) ans=(ans+DP(i,j))%p;}}return ans;
}
int main()
{int T; cin>>T;while(T--){cin>>R>>C;for(int i=1;i<=R;i++)for(int j=1;j<=C;j++)scanf("%d",&G[i][j]);memset(d,0,sizeof(d));cout<<DP(1,1)<<endl; } return 0;
}