题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1978
思路:从右到左、从下到上递推。
设dp[i][j]为dp[i0][j0]可达的点,则dp[i0][j0] += dp[i][j];
PS:每个点可达的区域都是一个三角形,如图:
1 #include <cstdio>
2 #include <cstring>
3 #define N 105
4
5 int a[N][N], dp[N][N];
6
7 int main()
8 {
9 int n, m, t;
10 scanf("%d",&t);
11 while(t--)
12 {
13 scanf("%d%d",&n,&m);
14 for(int i=1; i<=n; i++)
15 for(int j=1; j<=m; j++)
16 scanf("%d",&a[i][j]);
17 memset(dp, 0, sizeof(dp));
18 dp[n][m] = 1;
19 for(int i=n; i>=1; i--)
20 {
21 for(int j=m; j>=1; j--)
22 {
23 for(int ii=i; ii<=i+a[i][j] && ii<=n; ii++)
24 {
25 for(int jj=j; jj-j+ii-i<=a[i][j] && jj<=m; jj++)
26 {
27 if(ii==i && jj==j) continue;
28 dp[i][j] = (dp[i][j] + dp[ii][jj])%10000;
29 }
30 }
31 }
32 }
33 printf("%d\n",dp[1][1]);
34 }
35 return 0;
36 }
2 #include <cstring>
3 #define N 105
4
5 int a[N][N], dp[N][N];
6
7 int main()
8 {
9 int n, m, t;
10 scanf("%d",&t);
11 while(t--)
12 {
13 scanf("%d%d",&n,&m);
14 for(int i=1; i<=n; i++)
15 for(int j=1; j<=m; j++)
16 scanf("%d",&a[i][j]);
17 memset(dp, 0, sizeof(dp));
18 dp[n][m] = 1;
19 for(int i=n; i>=1; i--)
20 {
21 for(int j=m; j>=1; j--)
22 {
23 for(int ii=i; ii<=i+a[i][j] && ii<=n; ii++)
24 {
25 for(int jj=j; jj-j+ii-i<=a[i][j] && jj<=m; jj++)
26 {
27 if(ii==i && jj==j) continue;
28 dp[i][j] = (dp[i][j] + dp[ii][jj])%10000;
29 }
30 }
31 }
32 }
33 printf("%d\n",dp[1][1]);
34 }
35 return 0;
36 }