A49456.一个简单的迷宫 题解

题目明确写了只能向下和右方走，明显的 DP。设 $dp_{i,j}$ 表示走到 $(i,j)$ 的最大价值。若为障碍，设置为 $-\infin$，否则得到 $dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})+a_{i,j}$ 直接转移即可。

建议降橙，它不配黄题。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,x,y;
ll a[1005][1005],dp[1005][1005];
bool vis[1005][1005];
int main(){
    cin>>n>>k;
    for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) cin>>a[i][j];
    for(ll i=1;i<=k;i++){
        cin>>x>>y;
        vis[x][y]=true;
    }
    memset(dp,0xcf,sizeof(dp));
    dp[0][1]=dp[1][0]=0;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            if(vis[i][j]) continue;
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
        }
    }
    if(dp[n][n]<0) dp[n][n]=-1;
    cout<<dp[n][n];
    return 0;
}