dfs超时，bp可以过

bp:f[a][b]=f[a][b]+f[i][j] 其中(a,b)是(i,j)所能在能量范围内到达的位置，记录该位置能到达几次，到了f[n][m]就是有多少条路径可以到终点。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 110;
typedef long long LL;
int n,m;
int g[N][N];
int mod  =10000;
int ans = 0;

int f[N][N];
//方法超时
void dfs(int x, int y)
{

    if(x==n && y==m)
    {
        ans+=1;
        return;
    }    
    
    //在能量范围内
    int e = g[x][y];
    //对于从x和y出发有多少种答案
    for(int dx=0;dx<= e;dx++)
    {
        for(int dy=(dx==0?1:0);dy<=e-dx;dy++)
        {
            int a = x+dx;
            int b = y+dy;
            if(a<x || a> x+e|| a>n || b < y || b>y+e || b>m)
                continue;
            dfs(a,b);
        }
    }
    ans = ans %mod;
}

void dp()
{
    memset(f,0,sizeof f);
    f[1][1] = 1;
    for(int i=1; i<=n;i++)
        for(int j = 1;j<=m;j++)
        {
            //在能量范围内
            int e = g[i][j];
            for(int dx=0;dx<= e;dx++)
            {
                for(int dy=(dx==0?1:0);dy<=e-dx;dy++)
                {
                    int a = i+dx;
                    int b = j+dy;
                    if(a<i || a> i+e|| a>n || b < j || b>j+e || b>m)
                        continue;
                    f[a][b] = (f[a][b]+f[i][j])%mod; 
                }
            }
        }
    ans = f[n][m];
}

int main()
{
    int T;
    
    scanf("%d",&T);
    while (T--)
    {
        memset(g,0,sizeof g);
        ans = 0;
        scanf("%d%d",&n,&m);
        
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                scanf("%d",&g[i][j]);
            }
        }
        //dfs(1,1);
        dp();
        cout << ans << endl;
    }
    
    return 0;
}