题解 CF1063B 【Labyrinth】
ouuan
2018-10-14 22:00:16
这题有向左最大步数和向右最大步数两个约束，所以很烦。能不能只有一个约束呢？这个时候往往要观察几个约束条件之间的关系。
**1.向左走的步数-向右走的步数=起点横坐标-终点横坐标**
有了这个式子，就可以用向左走的步数同时表示向右走的步数。
**2.向左走的步数越多，向右走的步数越多**
这个条件是可以由上面那个式子推来的，它的作用是保证了向左走的步数最少时一定是全局最优解。
所以整个问题被转化成了只用管向左步数的01最短路，用SPFA即可解决，计算答案时满足**向左步数<=向左最大步数&&向左步数+横坐标之差<=最大向右步数**就计入答案。
参考代码：
```
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
const int N=2010;
const int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
int n,m,r,c,x,y,dis[N][N],ans;
bool g[N][N],inq[N][N];
char s[N];
queue<pii> q;
int main()
{
int i,j,tx,ty;
pii t;
memset(dis,0x3f,sizeof(dis));
scanf("%d%d%d%d%d%d",&n,&m,&r,&c,&x,&y);
for (i=1;i<=n;++i)
{
scanf("%s",s);
for (j=1;j<=m;++j)
{
if (s[j-1]=='.')
{
g[i][j]=true;
}
}
}
dis[r][c]=0;
q.push(pii(r,c));
while (!q.empty())
{
t=q.front();
q.pop();
inq[t.first][t.second]=false;
for (i=0;i<4;++i)
{
tx=t.first+dir[i][0];
ty=t.second+dir[i][1];
if (g[tx][ty]&&dis[tx][ty]>dis[t.first][t.second]+(i==0))
{
dis[tx][ty]=dis[t.first][t.second]+(i==0);
if (!inq[tx][ty])
{
inq[tx][ty]=true;
q.push(pii(tx,ty));
}
}
}
}
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
if (g[i][j]&&dis[i][j]<=x&&dis[i][j]+j-c<=y)
{
++ans;
}
}
}
printf("%d",ans);
return 0;
}
```