这题是记忆化搜索：

#include
     
       #include
      
        #include
       
         using namespace std; int map[124][124]; int ans[124][124]; int N,M; int DFS( int x ,int y ) {
   int sum = 0; if( x == N && y == M ) return 1; if( ans[x][y]>=0 ) return ans[x][y]; for( int i=0; i<= map[x][y] ; i++ ) for( int j=0; j<= map[x][y]; j++ )       {
   if( (i+j)<=map[x][y] && ( i + x )<=N && ( j + y )<=M && ( i+j )!=0 )            {
                  sum+=DFS( i + x , j+y );                sum %= 10000;             }              }       ans[x][y] = sum; return  sum; } int main(  ) {
   int n; while( scanf( "%d",&n )==1 )    {
   while( n-- )        {
             scanf( "%d%d",&N, &M  );           memset( map , 0 , sizeof( map ) );           memset( ans , -1 , sizeof( ans ) ); for( int i=1; i<= N; i++ ) for( int j= 1; j<=M ; j++ )                scanf( "%d",&map[i][j] );           printf( "%d\n",DFS( 1 ,1) );           }     } return 0;    }