CF1063B?Labyrinth

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; }

?

轉載于:https://www.cnblogs.com/lxyyyy/p/11272565.html

總結

以上是生活随笔為你收集整理的【CF1063B】Labyrinth [最短路？ 01BFS]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。