hdu 1987 How many ways (两种解法 1.搜索 2.dp)

How many waysTime Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2112 Accepted Submission(s): 1274

Problem Description
如上图，机器人一开始在(1,1)点，并拥有4单位能量，蓝色方块表示他所能到达的点，如果他在这次路径选择中选择的终点是(2,4)

点，当他到达(2,4)点时将拥有1单位的能量，并开始下一次路径选择，直到到达(6,6)点。
我们的问题是机器人有多少种方式从起点走到终点。这可能是一个很大的数，输出的结果对10000取模。InputOutputSample InputSample Output#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#define maxn 105#define mod 10000#define INF 0x3f3f3f3fusing namespace std;int n,m,ans;int mp[maxn][maxn];int dp[maxn][maxn];void solve(){ int i,j,p,q,r,d; memset(dp,0,sizeof(dp)); dp[1][1]=1; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { r=min(i+mp[i][j],n); for(p=i;p<=r;p++) { d=min(j+mp[i][j]-(p-i),m); for(q=j;q<=d;q++) { if(p==i&&q==j) continue ; dp[p][q]+=dp[i][j]; if(dp[p][q]>=mod) dp[p][q]%=mod; } } } }}int main(){ int i,j,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%d",&mp[i][j]); } } solve(); printf("%d\n",dp[n][m]); } return 0;}