题意:n x m 的矩阵,元素代表机器人到达这个点时能量变成的值,机器人起始时在(1, 1),它要去(n, m),只能走右或者走下,每走一步消耗 1 点能量,问到达(n, m)的方法有多少种,结果对 10000 取模。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1978
——>>状态:dp[i][j] 表示到达 (i, j) 的路径数。
状态转移方程:dp[newx][newy] = (dp[newx][newy] + dp[i][j]) % MOD;((newx, newy)是可以到达的点)
觉得有点很重要:对于能量 e,用两层 for 枚举能走到的所有点。。
#include <cstdio> #include <cstring> const int MAXN = 100 + 10; const int MOD = 10000; int n, m; int G[MAXN][MAXN]; int dp[MAXN][MAXN]; void Read() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &G[i][j]); } } } void Dp() { memset(dp, 0, sizeof(dp)); dp[1][1] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (dp[i][j]) { int e = G[i][j]; for (int x = 0; x <= e; ++x) { for (int y = 0; y <= e; ++y) { if (x + y == 0) continue; if (x + y > e) break; int newx = i + x; int newy = j + y; if (newx <= n && newy <= m) { dp[newx][newy] = (dp[newx][newy] + dp[i][j]) % MOD; } } } } } } printf("%d\n", dp[n][m]); } int main() { int T; scanf("%d", &T); while (T--) { Read(); Dp(); } return 0; }