Codeforces 1063B Labyrinth

题目链接https://codeforces.com/contest/1063/problem/B

题意:一个迷宫有些格子是障碍不能通过,现在限制向左走和向右走的步数,问从给定起点出发能到达哪些非障碍点。

思路BFS,由于左右有限制,所以我们肯定是上下先能走就走,然后用优先队列优先弹出当前左右步数之和最多的状态去走即可,后来看题解发现这个可以用双端队列去掉优先队列的一个log

#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2000+10;
struct P{
    int x,y,L,R;
    bool operator<(const P&rhs)const{
        return L+R<=rhs.L+rhs.R;
    }
};
int n,m,i,j,r,c,x,y,ans;
bool vis[N][N];
char s[N][N];
priority_queue<P>Q;
bool check(int x,int y){
    return x>=1 && x<=n && y>=1 && y<=m; 
}
int main(){
    read(n),read(m);
    read(r),read(c),read(x),read(y);
    for (i=1;i<=n;++i) scanf("%s",s[i]+1);
    vis[r][c]=1;
    Q.push((P){r,c,x,y});
    while (!Q.empty()){
        auto cur=Q.top();Q.pop();

        int tx=cur.x+1,ty=cur.y;
        if (check(tx,ty) && s[tx][ty]!='*' && !vis[tx][ty]){
            vis[tx][ty]=1;
            Q.push((P){tx,ty,cur.L,cur.R});
        }

        tx=cur.x-1,ty=cur.y;
        if (check(tx,ty) && s[tx][ty]!='*' && !vis[tx][ty]){
            vis[tx][ty]=1;
            Q.push((P){tx,ty,cur.L,cur.R});
        }

        if (cur.R){
            tx=cur.x,ty=cur.y+1;
            if (check(tx,ty) && s[tx][ty]!='*' && !vis[tx][ty]){
                vis[tx][ty]=1;
                Q.push((P){tx,ty,cur.L,cur.R-1});
            }
        }

        if (cur.L){
            tx=cur.x,ty=cur.y-1;
            if (check(tx,ty) && s[tx][ty]!='*' && !vis[tx][ty]){
                vis[tx][ty]=1;
                Q.push((P){tx,ty,cur.L-1,cur.R});
            }
        }
    }
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)ans+=vis[i][j];
    printf("%d\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注