CF D. Labyrinth 01BFS

由于上下走不限制，所以按照贪心，我们应该尽可能走上下方向.
我们可以开一个双端队列，并认为每次提取队首的时候得到的是到达该点的最优策略.(这个一定是唯一的，因为不可能向右走几格，然后再退回去. )
那么如果向上下走是不损失的，所以将上下的格子推进队首，优先扩展，然后将左右推进队尾，最后扩展.
这个贪心是正确的，可以保证每一个格子被扩展时都是最优策略.

#include<bits/stdc++.h>

#define maxn 2003

using namespace std;

void setIO(string s) {

    string in=s+".in";

    freopen(in.c_str(),"r",stdin);

}

int dx[]={0,1,0,-1};

int dy[]={1,0,-1,0};

struct Node {

    int x,y;

    Node(int y=0,int x=0):x(x),y(y){}

};

deque<Node>Q;

int n,m,r,c,X,Y;

int G[maxn][maxn],vis[maxn][maxn],L[maxn][maxn],R[maxn][maxn];

char str[maxn];

int main() {

    int cc=1;

    // setIO("input");

    scanf("%d%d%d%d%d%d",&n,&m,&r,&c,&X,&Y);

    for(int i=1;i<=n;++i) {

        scanf("%s",str+1);

        for(int j=1;j<=m;++j) G[i][j]=!(str[j]=='.');

    }

    vis[r][c]=1;

    Q.push_back(Node(r, c));

    while(!Q.empty()) {

        Node u=Q.front(); Q.pop_front();

        for(int i=0;i<4;++i) {

            int x=u.x+dx[i],y=u.y+dy[i];

            if(x<1||x>m||y<1||y>n||vis[y][x]||G[y][x]) continue;

            vis[y][x]=1;

            L[y][x]=L[u.y][u.x];

            R[y][x]=R[u.y][u.x];

            if(x<u.x) {

                if(L[u.y][u.x] + 1 > X) continue;

                else {

                    L[y][x]=L[u.y][u.x]+1;

                    Q.push_back(Node(y, x));

                    ++cc;

                    continue;

                }

            }

            if(x>u.x) {

                if(R[u.y][u.x] + 1 > Y) continue;

                else {

                    R[y][x]=R[u.y][u.x]+1;

                    Q.push_back(Node(y,x));

                    ++cc;

                    continue;

                }

            }

            Q.push_front(Node(y,x));

            ++cc;

        }

    }

    printf("%d\n",cc);

    return 0;

}

巴特西

CF D. Labyrinth 01BFS

最新文章

热门文章