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;
}