CF1063B Labyrinth ~ Codeforces
数据范围较小，考虑使用搜索。
由于向左向右的步数限制过大，我们只能用\(x,y\)进行记忆化，否则空间和时间都过不去。
既然状态只有\(x,y\)，我们就要让最优情况最先被遍历到，所以考虑BFS。
我们考虑，对于\((x,y)\)状态来说，什么样的情况是最优的？
显然，对于上图所示情况，中间的路径是最优的。
不难发现，从起点\((r,c)\)到终点\((x,y)\)，“向右的步数\(-\)向左的步数”是固定值，也就是说，向右走得越多，向左也要走得越多，反之亦然。并不存在“通过多付出向右走的代价以减少向左走的代价”。所以我们可以认为，向左右走的总次数越少，该情况越不劣。
又因为每次操作花费只有\(0,1\)两种，所以任何时刻，队列中的操作总花费最多是\(2\)个相邻的整数。进而，我们可以采用0-1 BFS来求解，开一个双端队列，如果此次操作花费为\(1\)则放在队尾，否则放在队头，就可以保证每次从队头取出的都是最优的情况。
点击查看代码
#include<bits/stdc++.h>
#define N 2002
using namespace std;
struct Status{int x,y,l,r;};
int n,m,x,y,l,r,ans,dx[4]{-1,0,1,0},dy[4]{0,1,0,-1};
string s[N];
deque<Status> q;
bitset<N> vis[N];
signed main(){
cin>>n>>m>>x>>y>>l>>r;
for(int i=1;i<=n;i++) cin>>s[i],s[i]=' '+s[i];
q.push_back({x,y,l,r});
ans=vis[x][y]=1;
while(!q.empty()){
Status sta=q.front();
q.pop_front();
for(int i=0;i<4;i++){
int xx=sta.x+dx[i],yy=sta.y+dy[i],tl=sta.l,tr=sta.r;
if(dy[i]==1) tr--; else if(dy[i]==-1) tl--;
if(xx<1||yy<1||xx>n||yy>m||s[xx][yy]=='*'||vis[xx][yy]||tl<0||tr<0) continue;
vis[xx][yy]=1,ans++;
if(i==1) q.push_back({xx,yy,sta.l,sta.r-1});
else if(i==3) q.push_back({xx,yy,sta.l-1,sta.r});
else q.push_front({xx,yy,sta.l,sta.r});
}
}
cout<<ans<<"\n";
return 0;
}