uva 825 - Walking on the Safe Side(dp)
题目大意:给出n,m,现在给出n行数据, 每行有k(k为不定值)个数字, 第一个数字代表行数, 后面k - 1个数代表当前行的这个位置不可走, 问有多少路径可以从(1,1)到(n,m),只能向下或向右。解题思路:dp[i][j] = dip[i - 1][j] + dp[i][j - 1], 很简单的dp问题。
#include <stdio.h> #include <string.h> const int N = 1005; int n, m, dp[N][N], g[N][N]; void handle(int k, char str[]) { int len = strlen(str), num = 0; for (int i = 0; i <= len; i++) { if (str[i] >= '0' && str[i] <= '9') num = num * 10 + str[i] - '0'; else { g[k][num] = 1; num = 0; } } } void read() { int r; char str[N]; memset(dp, 0, sizeof(dp)); memset(g, 0, sizeof(g)); scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", &r); gets(str); handle(r, str); } } int solve () { dp[0][1] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (g[i][j]) continue; dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[n][m]; } int main() { int cas; scanf("%d", &cas); while (cas--) { read(); printf("%d\n", solve()); if (cas) printf("\n"); } return 0; }
补充:软件开发 , C++ ,