dp[0/1][i][j][0/1]表示到达(i,j)格子之后,离开该格子的方向为右/下(第二个0/1)最大/小(第一个0/1)拐弯次数
但是样例都没过。。。求助QAQ
#include<cstdio>
const int M=1005,INF=2e9;
int n,m,dp[2][M][M][2];
inline int max(const int a,const int b){
return a>b?a:b;
}
inline int min(const int a,const int b){
return a>b?b:a;
}
signed main(){
int i,j,w1,w2,w3,w4,ans1,ans2;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)dp[0][i][0][0]=dp[0][i][0][1]=INF;
for(i=1;i<=m;++i)dp[0][0][i][0]=dp[0][0][i][1]=INF;
for(i=1;i<=n;++i){
getchar();
for(j=1;j<=m;++j){
if(getchar()=='#')continue;
w1=min(dp[0][i-1][j][0]+1,dp[0][i-1][j][1]);
w2=min(dp[0][i][j-1][0],dp[0][i][j-1][1]+1);
dp[0][i][j][0]=min(w1+1,w2);
dp[0][i][j][1]=min(w2+1,w1);
w1=max(dp[1][i-1][j][0]+1,dp[1][i-1][j][1]);
w2=max(dp[1][i][j-1][0],dp[1][i][j-1][1]+1);
dp[1][i][j][0]=max(w1+1,w2);
dp[1][i][j][1]=max(w2+1,w1);
// printf("%d %d ",dp[0][i][j][1],dp[0][i][j][0]);
// printf("%d %d\t",dp[1][i][j][1],dp[1][i][j][0]);
}
// printf("\n");
}
ans1=max(dp[1][n][m][1],dp[1][n][m][0]);
ans2=min(dp[0][n][m][1],dp[0][n][m][0]);
if(!ans1||!ans2)printf("-1");
else printf("%d %d",ans1,ans2);
}