01BFS 和普通的01BFS不一样的是这题可以重复走
从(sx,sy)到(x,y)假设向左走了l步向右走了r步 则有sx+r-l=x 即l-r=sx-x为定值 所以向左走越多步则向右也走越多
我们可以只看向右走 然后以向右就可以表达出向左走 跑一遍01BFS 最后统计答案
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; const int N=2000+5,M=1000+5,inf=0x3f3f3f3f,P=9999973; int n,m,r,c,L,R,ans=0; char mp[N][N]; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } //右 左 下 上 int dx[5]={0,0,1,-1}; int dy[5]={1,-1,0,0}; deque<pii>q; int dis[N][N]; void bfs(pii s){ memset(dis,inf,sizeof(dis)); while(!q.empty()) q.pop_front(); q.push_back(s),dis[s.first][s.second]=0; while(!q.empty()){ pii tmp=q.front(); q.pop_front(); int x=tmp.first,y=tmp.second; for(int i=0;i<4;++i){ int nx=x+dx[i],ny=y+dy[i]; if(nx&&nx<=n&&ny&&ny<=m&&mp[nx][ny]=='.'){ if(dis[nx][ny]>dis[x][y]+(!i)){ dis[nx][ny]=dis[x][y]+(!i); if(!i) q.push_back(make_pair(nx,ny)); else q.push_front(make_pair(nx,ny)); } } } } } int main(){ freopen("in.txt","r",stdin); rd(n),rd(m),rd(r),rd(c),rd(L),rd(R); for(int i=1;i<=n;++i) scanf("%s",mp[i]+1); bfs(make_pair(r,c)); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(dis[i][j]<=R&&dis[i][j]+c-j<=L) ++ans; printf("%d",ans); return 0; }