Labyrinth

题意是说，有一个迷宫，限制了左移和右移的次数，但上移和下移的次数不做限制，问从某一点出发，最多能访问多少个点。

bfs搜一遍，每个节点记录当前剩余的左移和右移次数。需要注意的是，这题应该使用优先队列，每次走的时候优先走那些剩余左右移动次数多的点，这样才能尽可能地访问更多的点。这应该也算是一种贪心策略。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int lmx,rmx;
struct node{
    int x,y;
    int lef,rig;
    bool operator<(const node& na) const{
        if(lef==na.lef)    return rig<na.rig;        //优先走那些左右次数大的点,否则会导致有些点无法到达 
        return lef<na.lef;
    }
};
char mp[2005][2005];
bool vis[2005][2005];
int n,m;
int dir[4][2]=<!--swig0-->;        //上,下,左,右 
bool check(int cx,int cy)            //行,列 
{
    if(cx<0||cx>=n||cy<0||cy>=m||mp[cx][cy]=='*'||vis[cx][cy])    return 0;
    return 1;
}
int bfs(int sx,int sy)
{
    int ans=0;
    mst(vis,0);
    priority_queue<node> que;
    que.push(node{sx,sy,lmx,rmx});
    vis[sx][sy]=1;ans++;
    while(!que.empty()){
        node cur=que.top();
        que.pop();
        int xx=cur.x;int yy=cur.y;
        int L=cur.lef;
        int R=cur.rig;
        for(int i=0;i<4;i++){
            int tx=xx+dir[i][0];
            int ty=yy+dir[i][1];
            if(i==2){
                if(L<=0)    continue;
                if(check(tx,ty)){
                    vis[tx][ty]=1;
                    que.push(node{tx,ty,L-1,R});
                    ans++;
                }
            }else if(i==3){
                if(R<=0)    continue;
                if(check(tx,ty)){
                    vis[tx][ty]=1;
                    que.push(node{tx,ty,L,R-1});
                    ans++;
                }
            }else{
                if(check(tx,ty)){
                    vis[tx][ty]=1;
                    que.push(node{tx,ty,L,R});
                    ans++;
                }
            }
        }
    }
    return ans;
}
int main()
{
    scanf("%d %d",&n,&m);
    int r,c;scanf("%d %d",&r,&c);
    scanf("%d %d",&lmx,&rmx);
    for(int i=0;i<n;i++){
        scanf("%s",mp[i]);
    }
    int ans=bfs(r-1,c-1);
    printf("%d\n",ans);
    return 0;
}