dp[][]从这个点为起点的路径数量
终点的自己到自己算一种
使用递推f()=所有出去之和
#include <bits/stdc++.h>
using namespace std;
int n,m;
int g[105][105];int visited[105][105];
int dp[105][105];//从这个点出发的方案数
int dfs(int x,int y,int w)
{if(dp[x][y]!=-1) return dp[x][y];if(x==n&&y==m) return 1;//一种 int cc=0;for(int ii=0;ii<=w;ii++){for(int jj=0;jj<=w-ii;jj++){if(jj==0&&ii==0) continue;int nx=x+ii;int ny=y+jj;int nw=g[nx][ny];if(nx<=0||nx>n||ny<=0||ny>m) continue;cc+=dfs(nx,ny,nw);cc=cc%10000;}}return dp[x][y]=cc;
}
int main()
{int t;cin>>t;while(t--){cin>>n>>m;memset(dp,-1,sizeof(dp));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>g[i][j];}}int ans=dfs(1,1,g[1][1]);cout<<ans<<endl;}
}
dfs的
#include <bits/stdc++.h>
using namespace std;
int n,m;
int g[105][105];int visited[105][105];
int ans=0;
void dfs(int x,int y,int w)
{if(x==n&&y==m) {ans=(ans+1)%10000;return;}for(int ii=0;ii<=w;ii++){for(int jj=0;jj<=w-ii;jj++){if(jj==0&&ii==0) continue;int nx=x+ii;int ny=y+jj;int nw=g[nx][ny];if(nx<=0||nx>n||ny<=0||ny>m) continue;if(visited[nx][ny]==1) continue;visited[nx][ny]=1;dfs(nx,ny,nw);visited[nx][ny]=0;}}
}
int main()
{int t;cin>>t;while(t--){ans=0;cin>>n>>m;memset(visited,0,sizeof(visited));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>g[i][j];}}visited[1][1]=1;dfs(1,1,g[1][1]);cout<<ans<<endl;}
}