双端队列宽搜做法

重点：

对于每一个点，在没有障碍物的情况下，可以由上下或左右得到
但是，我们肯定优先选择上下得到，因为这样可以较多的在以后向左或向右走

因此：
1. 上下走的优先考虑，因为这样走不消耗体力，因此放在队头
2. 左右走的其次考虑，这样走消耗体力，放在队尾

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

const int N = 2005;
int n,m,r,c,x,y,cnt;
char g[N][N];
bool st[N][N];
int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};

struct Node{
    int a,b,rl,rr;
    //当前位置(a,b)，还能往左走rl步，往右走rr步
};

void bfs(){
    deque<Node> q;//双端队列
    q.push_back({r,c,x,y});//初始位置
    st[r][c] = 1;//标记可以走
    while(q.size()){
        auto t = q.front();q.pop_front();//取出队头元素
        int a = t.a,b = t.b,rl = t.rl,rr = t.rr;
        for(int i = 0;i < 4;i++){
            int nx = a + dx[i],ny = b + dy[i];
            //条件判断：

            //如果想向左或向右走，发现没有步数了，跳过
            if(dy[i] == -1 && dx[i] == 0 && (!rl)) continue;
            else if(dy[i] == 1 && dx[i] == 0 && (!rr)) continue;

            if(nx <= 0 || nx > n || ny <= 0 || ny > m) continue;//越界处理
            if(g[nx][ny] == '*') continue;//障碍物跳过
            if(st[nx][ny]) continue;//已标记跳过

            st[nx][ny] = 1;//标记

            //如果是往左或往右走，将步数-1，放到队尾
            //但是，如果是往上或往下走放在队头，因为消耗的体力少，能走的步数多，可以理解为最优解
            if(dy[i] == -1 && dx[i] == 0) q.push_back({nx,ny,rl - 1,rr});
            else if(dy[i] == 1 && dx[i] == 0) q.push_back({nx,ny,rl,rr - 1});
            else q.push_front({nx,ny,rl,rr});


        }
    }
}

int main(){
    //输入
    scanf("%d%d%d%d%d%d",&n,&m,&r,&c,&x,&y);
    for(int i = 1;i <= n;i++) cin >> g[i] + 1;

    //宽搜 处理 
    bfs();

    //统计
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            if(st[i][j]){
                cnt++;

    //输出      
    printf("%d",cnt);

    return 0;
}