(Des)
有一个网格图,上面的格子分为空地和障碍,障碍是不可以走的.现在从给定的起点出发开始到处乱走,最多可以往左走(l)次,往右走(r)次.求可能到达的点数.
(Sol)
如果只限制了向左或向右走的次数就要简单一些,所以我们先思考这一种情形.
假设只限制了向左走不能超过(l)次.这样转化:对于每个点,它向左走花费的代价是(1),其他方向的代价是(0).求从给定起点出发,走到每一个点的最小花费.对于某一个点,如果这个花费是(leq l)的,那么这个位置就是可达的.这不就是(01)最短路嘛.
现在考虑第二个限制.其实可以发现从起点走到一个特定的点,若向左走的步数一定,那么向右走的步数也是一定的,而且向左走的步数越少,向右走的步数也越少.也就是说,在只考虑一个限制时跑的最短路在考虑两个限制时仍然是最短路.于是就直接按照上面讲的做就好了,统计答案的时候考虑两个限制.
其实,并不需要求出所有的最短路,只要满足限制的点向别的点转移就可以了.
(Code)
Code
```cpp
#include
#define il inline
#define Ri register int
#define go(i,a,b) for(Ri i=a;i<=b;++i)
#define yes(i,a,b) for(Ri i=a;i>=b;--i)
#define e(i,u) for(Ri i=b[u];i;i=a[i].nt)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define db double
#define inf 2147483647
using namespace std;
il int read()
{
Ri x=0,y=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*y;
}
const int N=2010;
int n,m,rx,ry,l,r,as,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
char s[N][N];bool vis[N][N];
struct nd{int x,y,l,r;};
dequeq;
int main()
{
n=read(),m=read();rx=read(),ry=read();l=read(),r=read();
go(i,1,n)scanf("%s",(s[i]+1));
q.push_back((nd){rx,ry,0,0});
while(q.size())
{
nd nw=q.front();Ri nx=nw.x,ny=nw.y,nl=nw.l,nr=nw.r;q.pop_front();
if(nl>l || nr>r || vis[nx][ny])continue;
vis[nx][ny]=1;++as;
go(i,0,3)
{
Ri tx=nx+dx[i],ty=ny+dy[i];
if(tx<1 || tx>n || ty<1 || ty>m || s[tx][ty]=='*')continue;
nd tw=(nd){tx,ty,nl+(i==1),nr+(i==0)};
if(i==1)q.push_back(tw);
else q.push_front(tw);
}
}
printf("%d
",as);
return 0;
}
<details>