学步园

记忆化搜索

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define mod 10000
int const MAX = 110;
int map[MAX][MAX],vis[MAX][MAX];
int T,n,m;
int dfs(int x,int y){
    int num,temp;
    num = 0;
    if(x == n && y == m) return 1;
    if(vis[x][y] != -1) return vis[x][y];
    temp = map[x][y];
    for(int i = 0;i <= temp;i++){
       for(int j = 0;j <= temp;j++){
          if(x + i <= n && y + j <= m && i + j != 0 && i + j <= temp){
            num += dfs(x + i,y + j);
            num %= mod;
          }
       }
    }
    vis[x][y] = num;
    return num;
}
int main(){
   while(~scanf("%d",&T)){
      while(T--){
          scanf("%d%d",&n,&m);
          for(int i = 1;i <= n;i++){
             for(int j = 1;j <= m;j++){
                scanf("%d",&map[i][j]);
             }
          }
          memset(vis,-1,sizeof(vis));
          printf("%d\n",dfs(1,1));
      }
   }
   return 0;
}