题目是中文,就不啰嗦了。。。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; int dp[110][110],mp[110][110]; int n,m; int dfs(int x,int y) { int k=mp[x][y]; int i,j; if(x==m && y==n) return 1; if(dp[x][y]) return dp[x][y]; for(i=0;i<=min(k,m-x);i++) //一定要从0开始 { for(j=0;j<=min(k-i,n-y);j++) { if(i==0 && j==0) continue; dp[x][y]+=dfs(x+i,y+j); dp[x][y]=dp[x][y]%10000; } } return dp[x][y]; } int main() { int T; scanf("%d",&T); while(T--) { memset(dp,0,sizeof(dp)); memset(mp,0,sizeof(mp)); scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); } dfs(1,1); printf("%d\n",dp[1][1]); } return 0; }