【01BFS+思维】Codeforces Round #516 D. Labyrinth

【01BFS+思维】Codeforces Round #516 D. Labyrinth

题意：
给出一个迷宫，限定能往左走和往右走的次数分为为l,r，上下走不限，迷宫中能走的范围最大时多少格子？

思路：
采用双端队列，BFS的时候优先上下走放在双端队列首部，左右走放在队列尾部，这样可以保证走的方法最优。

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int MAXN=2000+10;

//01BFS
//左右走的放在队列首部，上下走的放在队列尾部
char s[MAXN][MAXN];
int n,m;
struct Node
{
    int X,Y,l,r;
    Node(){}
    Node(int _X,int _Y,int _l,int _r):X(_X),Y(_Y),l(_l),r(_r){}
};
deque<Node>que;
bool vis[MAXN][MAXN];
int dirx[4]={1,-1,0,0};
int diry[4]={0,0,-1,1};



int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int r,c;
    int x,y;
    cin>>r>>c;
    cin>>x>>y;
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>s[i][j];
    Node now=Node(r,c,x,y);
    que.push_back(now);
    while(!que.empty())
    {
        now=que.front();que.pop_front();
        if(vis[now.X][now.Y]||now.l<0||now.r<0)continue;
        vis[now.X][now.Y]=1;ans++;
        for(int i=0;i<4;i++)
        {
            int nextx=now.X+dirx[i],nexty=now.Y+diry[i];
            if(nextx<1||nextx>n||nexty<1||nexty>m||s[nextx][nexty]=='*')continue;
            if(i==0||i==1)//up down
            {
                que.push_front(Node(nextx,nexty,now.l,now.r));
            }
            else if(i==2)//left
            {
                que.push_back(Node(nextx,nexty,now.l-1,now.r));
            }
            else if(i==3)
            {
                que.push_back(Node(nextx,nexty,now.l,now.r-1));
            }
        }
    }
    cout<<ans<<endl;



    return 0;
}