Codeforces Round #516 (Div. 2）D. Labyrinth

D. Labyrinth

题目链接：https://codeforces.com/contest/1064/problem/D

题意：

给出一个n*m的矩阵以及人物的起点，并且给出x，y，分别代表这个人向左最多走x步，向右最多走y步。

矩阵中存在障碍，问这个人最多能到达多少数量的格子。

题解：

就是一个bfs...只是要稍微剪枝一下，如果发现当前这个点所到达的格子已经被之前的一个点到达过，当且仅当当前点的x或y至少一个比之前到达的点大时，就将这个点入队。

只有这样才能保证解最优。

代码如下:

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

const int N =  ;

int n,m,R,C;

int mp[N][N],vis[N][N][],l[N][N],r[N][N],check[N][N];

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

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

int ans = ;

char s[N];

bool ok(int x,int y){

    if(x>= && x<=n && y>= && y<=m && mp[x][y]!=) return true;

    return false ;

}

struct node{

    int x,y,lx,ly;

}cur;

queue <node> q;

void bfs(){

    while(!q.empty()){

        node now = q.front();q.pop();

        int x = now.x,y = now.y,l,r;

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

            cur.x=x+dx[i];cur.y=y+dy[i];

            l = now.lx;r = now.ly;

            if(i==) r--;

            if(i==) l--;

            if(ok(cur.x,cur.y)&&r>=&&l>=){

                if(l>vis[cur.x][cur.y][]||r>vis[cur.x][cur.y][]){

                    if(vis[cur.x][cur.y][]==-) ans++;

                    q.push(node{cur.x,cur.y,l,r});

                    vis[cur.x][cur.y][]=l;

                    vis[cur.x][cur.y][]=r;

                }

            }

        }

    }

}

int main(){

    int x,y;

    cin>>n>>m>>R>>C>>x>>y;

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

        scanf("%s",s);

        for(int j=;j<m;j++){

            if(s[j]=='.') mp[i][j+]=;

            else mp[i][j+]=;

        }

    }

    q.push(node{R,C,x,y});

    memset(vis,-,sizeof(vis));

    vis[R][C][]=x;vis[R][C][]=y;

    check[R][C]=;

    bfs();

    cout<<ans;

    return ;

}