题解 P5003 【跳舞的线 - 乱拐弯】
3493441984zz
2019-02-06 09:40:12
# 这题很简单的，但是有坑点！！
坑了我一天，搞得我直接放弃，第二天才弄对。。
------------
# 设计状态：
我们设：
$f[i][j][0]$表示到了第$(i,j)$这个格子后，方向向右的最少拐弯数
$f[i][j][1]$表示到了第$(i,j)$这个格子后，方向向下的最少拐弯数
$g[i][j][0]$表示到了第$(i,j)$这个格子后，方向向右的最多拐弯数
$g[i][j][1]$表示到了第$(i,j)$这个格子后，方向向下的最多拐弯数
------------
# 状态转移：
我们开始设计转移方程：
### 对于$f[i][j][0]$:
$1$、它可能是由它左边这个格子向右直走一格来的，这样的话本来方向向右，现在还是向右，所以不拐弯，所以第一个状态转移方程：$$f[i][j][0]=f[i][j-1][0]$$
$2$、它还可能由它上面那个格子向下走一格，再拐一次弯向着右边转移来的，那么这个时候多拐了一次弯，所以第二个状态转移方程：$$f[i][j][0]=f[i-1][j][1]+1$$
**所以对于$f[i][j][0]$的状态转移总方程为:$$f[i][j][0]=min(f[i][j][0],min(f[i][j-1][0],f[i-1][j][1]+1))$$**
那么对于其他的状态转移方程也是这个思路，下面是状态转移代码：
~~~cpp
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(!map[i][j])
{
f[i][j][0]=min(f[i][j][0],min(f[i][j-1][0],f[i-1][j][1]+1));
f[i][j][1]=min(f[i][j][1],min(f[i-1][j][1],f[i][j-1][0]+1));
g[i][j][0]=max(g[i][j][0],max(g[i][j-1][0],g[i-1][j][1]+1));
g[i][j][1]=max(g[i][j][1],max(g[i-1][j][1],g[i][j-1][0]+1));
}
~~~
------------
# 坑点：
要特判起点为#的情况$QAQ$，我为这个调了一天$qwQ$
------------
### 最后是美滋滋的代码时间~~~
~~~cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1007
using namespace std;
int n,m;
int f[N][N][2],g[N][N][2],map[N][N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
char in;
scanf(" %c",&in);
if(in=='#')
map[i][j]=1;
}
if(map[1][1])
{
printf("-1");
return 0;
}
memset(f,0x3f,sizeof(f));
int inf=f[0][0][0];
memset(g,0xcf,sizeof(g));
f[1][1][0]=f[1][1][1]=0;
g[1][1][0]=g[1][1][1]=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(!map[i][j])
{
f[i][j][0]=min(f[i][j][0],min(f[i][j-1][0],f[i-1][j][1]+1));
f[i][j][1]=min(f[i][j][1],min(f[i-1][j][1],f[i][j-1][0]+1));
g[i][j][0]=max(g[i][j][0],max(g[i][j-1][0],g[i-1][j][1]+1));
g[i][j][1]=max(g[i][j][1],max(g[i-1][j][1],g[i][j-1][0]+1));
}
if(f[n][m][0]>=inf&&f[n][m][1]>=inf)
{
printf("-1");
return 0;
}
printf("%d %d",max(g[n-1][m][1],g[n][m-1][0]),min(f[n-1][m][1],f[n][m-1][0]));
return 0;
}
~~~