当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,