題目鏈接：點擊查看

題目大意：給出一個迷宮，一個男孩和一個女孩還有兩只鬼，男孩每秒鐘走3格，女孩每秒鐘走1格，鬼每秒鐘向四周分裂2格，問男孩和女孩能否在鬼占領(lǐng)迷宮之前匯合，能的話輸出匯合時間，否則輸出-1

題目分析：雙向bfs模板題，不過在我看來雙向bfs和單向bfs沒什么區(qū)別，就是格式上有點不一樣，對于這個題目每次男孩bfs一次，然后女孩bfs一次，注意實時判斷當(dāng)前格子是否已經(jīng)被鬼占領(lǐng)，每次向外擴(kuò)展的時候也不需要用vis數(shù)組標(biāo)記重復(fù)了，只需要在原迷宮的基礎(chǔ)上打上自己的特殊符號即可，只要另一方遍歷到該符號即代表兩人相遇，就可以及時返回了

這個題目有一個需要注意的地方，一開始沒仔細(xì)看題目，想當(dāng)然的以為M代表的是女生，G代表的是男生，結(jié)果正好相反了，當(dāng)時調(diào)了有點時間，回去仔細(xì)讀了一遍題才發(fā)現(xiàn)的。。

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=810;const int b[4][2]={0,1,0,-1,1,0,-1,0};int n,m,k,step,ans;char maze[N][N];struct Node {int x,y;Node(int X,int Y){x=X;y=Y;}Node(){} }ghost[2];queue<Node>gg,mm;bool check(int x,int y) {if(x<0||y<0||x>=n||y>=m)return false;if(maze[x][y]=='X')return false;for(int i=0;i<2;i++)if(step*2>=abs(x-ghost[i].x)+abs(y-ghost[i].y))return false;return true; }bool bfsgg() {for(int tt=1;tt<=3;tt++){queue<Node>q(gg);while(!q.empty()){Node cur=q.front();q.pop();gg.pop();if(!check(cur.x,cur.y))continue;for(int i=0;i<4;i++){int xx=cur.x+b[i][0];int yy=cur.y+b[i][1];if(!check(xx,yy))continue;if(maze[xx][yy]=='M')continue;if(maze[xx][yy]=='G')return true;maze[xx][yy]='M';gg.push(Node(xx,yy));}}}return false; }bool bfsmm() {queue<Node>q(mm);while(!q.empty()){Node cur=q.front();q.pop();mm.pop();if(!check(cur.x,cur.y))continue;for(int i=0;i<4;i++){int xx=cur.x+b[i][0];int yy=cur.y+b[i][1];if(!check(xx,yy))continue;if(maze[xx][yy]=='G')continue;if(maze[xx][yy]=='M')return true;maze[xx][yy]='G';mm.push(Node(xx,yy));}}return false; }bool solve() {while(!gg.empty())gg.pop();while(!mm.empty())mm.pop();step=k=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(maze[i][j]=='G')mm.push(Node(i,j));else if(maze[i][j]=='M')gg.push(Node(i,j));else if(maze[i][j]=='Z'){ghost[k].x=i;ghost[k].y=j;k++;}while(!mm.empty()&&!gg.empty()){step++;if(bfsgg()||bfsmm()){ans=step;return true;}}return false; }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%s",maze[i]);if(solve())printf("%d\n",ans);elseprintf("-1\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 3085 Nightmare Ⅱ(双向bfs)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。