50分dp,请各位大佬修改

B3625 迷宫寻路

zgr20090920 @ 2023-10-20 19:15:29

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,dp[110][110];
char a[110][110];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=max(n,m);i++){
        if(a[1][i]!='#'){
            dp[1][i]=1;
        }
        else{
            dp[1][i]=0;
        }
        if(a[i][1]!='#'){
            dp[i][1]=1;
        }
    }
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            if(a[i][j]!='#'){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    }
    if(dp[n][m]>=1){
        printf("%s","Yes");
    }
    else{
        printf("%s","No");
    }
    return 0;
}

by Wardin @ 2024-01-07 13:58:09

不建议用动态规划,广搜是最优解。


|