LG5003 跳舞的线 - 乱拐弯 线性DP

问题描述

LG5003

题解

设 \(mx[i][j][0/1]\)代表当前位置、朝向的最大拐弯数，最小同理。

来源为左边和上边。

坑点：起点可能为#。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

void fr(int &x){
    char ch=1;
    while(ch!='#'&&ch!='o') ch=getchar();
    if(ch=='#') x=1;
    else x=2;
}

int mx[1003][1003][2],mi[1003][1003][2];
int n,m;
int exist[1003][1003];

int main(){
    read(n);read(m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            fr(exist[i][j]);
        }
    }
    if(exist[1][1]==1){
        puts("-1");return 0;
    }
    memset(mx,0xcf,sizeof(mx));memset(mi,0x3f,sizeof(mi));
    mx[1][1][0]=mx[1][1][1]=mi[1][1][0]=mi[1][1][1]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(exist[i][j]==1) continue;
            mx[i][j][1]=max(mx[i][j][1],max(mx[i-1][j][1],mx[i][j-1][0]+1));
            mx[i][j][0]=max(mx[i][j][0],max(mx[i][j-1][0],mx[i-1][j][1]+1));
            mi[i][j][1]=min(mi[i][j][1],min(mi[i-1][j][1],mi[i][j-1][0]+1));
            mi[i][j][0]=min(mi[i][j][0],min(mi[i][j-1][0],mi[i-1][j][1]+1));
        }
    }
    if(mi[n][m][0]>=0x3f3f3f3f&&mi[n][m][1]>=0x3f3f3f3f) puts("-1");
    else printf("%d %d\n",max(mx[n-1][m][1],mx[n][m-1][0]),min(mi[n-1][m][1],mi[n][m-1][0]));
    return 0;
}