https://codeforces.com/problemset/problem/1063/B
题意：给定一个矩阵，你在一个给定坐标，规定向左右走的步数有限，计算你能走的最大步数。
分析：
假如只给了一个限制，也就是向左走的步数有限制，那么是不是bfs的时候向左走的代价赋值为1，向其他方向走的代价就是0.那么变成了01最短路，deque+bfs就可以。每次将代价为0的压入队头，代价为1的压入队尾，然后bfs更新点。
01最短路：https://www.geeksforgeeks.org/0-1-bfs-shortest-path-binary-graph/（其实用dijkstra理解就是优先把当前状态下代价最小的路先走通了，然后用来更新其他路。)
那么这题限制多了一个，向左和向右走的步数有限制，也就是说左和右代价为1.其他方向代价为0.然后deque去维护bfs。
建图把限制想成边权更容易理解。就转化成理解有i元钱，走一些路付一块钱，走一些路不用付钱，问总共能经过多少个节点。
01最短路可以deque+bfs做。
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=2e3+100; typedef long long LL; char ma[maxn][maxn]; bool vis[maxn][maxn]; LL sx,sy,n,m,l,r; LL ans=1; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; struct node{ LL x,y,lstep,rstep; }; void solve() { vis[sx][sy]=1; deque<node>q; q.push_back({sx,sy,l,r}); while(q.size()) { node u=q.front();q.pop_front(); for(LL i=0;i<4;i++) { LL vx=u.x+dx[i];LL vy=u.y+dy[i];LL vlstep=u.lstep;LL vrstep=u.rstep; if(ma[vx][vy]=='*'||vis[vx][vy]||vx<1||vx>n||vy<1||vy>m||(dy[i]==1&&vrstep<=0)||(dy[i]==-1&&vlstep<=0)) continue; if(dy[i]==1){ vis[vx][vy]=1;q.push_back({vx,vy,vlstep,vrstep-1});ans++; } else if(dy[i]==-1){ vis[vx][vy]=1;q.push_back({vx,vy,vlstep-1,vrstep});ans++; } else { vis[vx][vy]=1;q.push_front({vx,vy,vlstep,vrstep});ans++; } } } cout<<ans<<endl; } int main(void) { cin.tie(0);std::ios::sync_with_stdio(false); cin>>n>>m; cin>>sx>>sy; cin>>l>>r; for(LL i=1;i<=n;i++) for(LL j=1;j<=m;j++){ cin>>ma[i][j]; } solve(); return 0; }
