这道DP有点精妙~,大概最优子结构的转移函数写法长这样:
$$f_{max,i,j,0}=max(f_{max,i,j-1,0},f_{max,i,j-1,1}+1)$$
$$f_{max,i,j,1}=max(f_{max,i-1,j,0}+1,f_{max,i-1,j,1})$$
$$f_{min,i,j,0}=max(f_{min,i,j-1,0},f_{min,i,j-1,1}+1)$$
$$f_{min,i,j,1}=max(f_{min,i-1,j,0}+1,f_{min,i-1,j,1})$$
为了防止在起始点拐弯,最好的办法是-1越界。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register int
#define LL long long
using namespace std;
int n,m;
int f[1010][1010][2],g[1010][1010][2];
char a[1010][1010];
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];
memset(f,63,sizeof(f));
if(a[1][1]=='#'){cout<<-1;return 0;}
g[1][1][0]=g[1][1][1]=0;
f[1][1][0]=f[1][1][1]=0;//0 left 1 down
for(int i=1;i<=m;i++)g[0][i][1]=g[0][i][0]=-2147483647;
for(int i=1;i<=n;i++)g[i][0][1]=g[i][0][0]=-2147483647;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]=='o')
{
if(i==1&&j==1)continue;
g[i][j][1]=max(g[i-1][j][1],g[i][j-1][0]+1);
f[i][j][1]=min(f[i-1][j][1],f[i][j-1][0]+1);
g[i][j][0]=max(g[i-1][j][1]+1,g[i][j-1][0]);
f[i][j][0]=min(f[i-1][j][1]+1,f[i][j-1][0]);
}
int Ansa=max(g[n][m][1],g[n][m][0]);
int Ansb=min(f[n][m][1],f[n][m][0]);
if(Ansb>n+m-2)cout<<-1<<endl;
else cout<<Ansa-1<<" "<<Ansb<<endl;
return 0;
}