水题一枚，可惜，因为忘记判断是否越界WA了好几次。
思路：DP的高效在于，可以利用前面的结果，或者说其实有点递推的意思，如斐波那契数列 f[4]=f[3]+f[2]，f[3]和f[2]都是以前算出来过的，所以只进行一次计算就算出了f[4]，而不是从头算f[3]=f[1]+f[2];f[4]=f[3]+f[2];,从头算计算次数远高于直接递推，所以DP题往往是考虑第i步是怎么来的，找出状态转移方程（其实就是递推式），本题思路反过来，对每一个格子，考虑它对其他格子结果的影响。
如果到达map[i][j]有dp[i][j]种方法，map[i][j=a，那么可以从map[i][j]到达map[i][j]的“方圆a格”，所以以map[i][j]为中心方圆a格的格子 到达的方法都需要加上dp[i][j];
需要注意的是map[i][j]的方圆a格可能在n*m范围之外，所以小心判断

#include 
  
   
#include 
   
     #include 
    
      using namespace std; #define SIZE 102 #define MOD 10000 //bool vis[SIZE][SIZE]; int mat[SIZE][SIZE]; int dp[SIZE][SIZE]; int n,m; void init() { memset(dp,0,sizeof(dp)); memset(mat,0,sizeof(mat)); } int main() { int ncase,i,j,tt,ii,jj,mm; scanf(%d,&ncase); while(ncase--) { init(); scanf(%d%d,&n,&m); dp[1][1]=1; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf(%d,&mat[i][j]); tt=mm=mat[i][j]; if(tt) { for(ii=i;ii<=i+tt&&ii<=n;ii++) { for(jj=0;jj<=mm&&jj+j<=m;jj++) { if(ii==i&&j+jj==j)continue; dp[ii][j+jj]=((dp[ii][j+jj]+dp[i][j]))%MOD; } mm--; } } } printf(%d ,dp[n][m]); } return 0; }