欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 825 Walking on the Safe Side

程序员文章站 2022-04-02 19:01:09
...

题意:
从左上角到右下角共有几条路,只能向下和向右走。

思路:
dp[i][j]=dp[i-1][j]+dp[i][j-1]
某点的路线数等于左边和上边之和
初始化: dp[0][1]=1或dp[1][0]=1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;
int dp[1005][1005],g[1005][1005];

int main()
{
    ios::sync_with_stdio(false);
    int T,n,m;
    scanf("%d",&T);
    for(int k=1;k<=T;k++)
    {
        memset(dp,0,sizeof(dp));
        memset(g,0,sizeof(g));
        scanf("%d%d",&n,&m);
        int x;
        char c;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            int s=0;
            while((c=getchar())!='\n')
            {
                if(c>='0'&&c<='9')
                {
                    s=s*10+c-'0';
                }
                else
                {
                    g[x][s]=1;
                    s=0;
                }
            }
            if(s)
            {
                g[x][s]=1;
                s=0;
            }
        }
        dp[0][1]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(g[i][j]==0)
                {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        printf("%d\n",dp[n][m]);
        if(k!=T)
            printf("\n");
    }
    return 0;
}
相关标签: 动态规划