题目概述

给出一张地图，有障碍和空地。问从 $(s,t)$ 出发最多往左走 $max_L$ 步，往右走 $max_R$ 步能到达多少点。

解题报告

翰爷秒了Orz。看似有两个限制，实际上把式子写一下发现只有一个限制。

对于一个点 $(x,y)$ ，往左走和往右走的步数之差是个定值，所以往左走的次数 $L$ 和往右走的次数 $R$ 满足：$L\le max_L,R\le max_R,R-L=y-t$ 。也就是 $L\le max_L,L\le max_R+t-y$ ，刷最短路就好了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=2000,maxm=2000,maxt=maxn*maxm,df[4][2]={{0,-1},{-1,0},{0,1},{1,0}};

int n,m,s,t,L,R,dis[maxn+5][maxm+5],ans;char pic[maxn+5][maxm+5];
struct data{
    int x,y,s;data(int X,int Y,int S) {x=X;y=Y;s=S;}
    inline bool operator < (const data &a) const {return s>a.s;}
};
priority_queue<data> que;

#define check(x,y) (1<=(x)&&(x)<=n&&1<=(y)&&(y)<=m)
int main(){
    freopen("D.in","r",stdin);freopen("D.out","w",stdout);
    scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&L,&R);
    for (int i=1;i<=n;i++) scanf("%s",pic[i]+1);
    memset(dis,63,sizeof(dis));dis[s][t]=0;que.push(data(s,t,0));
    while (!que.empty()){
        data now=que.top();int x=now.x,y=now.y,s=now.s;que.pop();
        for (int f=0,xx,yy;f<4;f++){
            xx=x+df[f][0];yy=y+df[f][1];
            if (check(xx,yy)&&pic[xx][yy]!='*'&&s+!f<dis[xx][yy])
                dis[xx][yy]=s+!f,que.push(data(xx,yy,s+!f));
        }
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            ans+=dis[i][j]<=min(L,R-(j-t));printf("%d\n",ans);return 0;
}