首页 > 代码库 > HDU 3085 Nightmare Ⅱ (双向广搜)
HDU 3085 Nightmare Ⅱ (双向广搜)
题意:有M,G两人和鬼魂(Z)在n*m的方格内,M每秒走3步,G每秒走一步,鬼魂每秒走2步,问是否能
不遇到鬼魂下两人相遇,鬼魂可以穿墙(X),人不可以。初始鬼魂有2个。
#include<stdio.h> #include<string.h> #include<string> #include<queue> #include<map> #include<iostream> #include<algorithm> #define M 800 using namespace std; struct node { int x,y; node(){} node(int xx,int yy) { x=xx; y=yy; } }gg,mm,zz[2],f[2][M*M]; int step,front[2],rear[2]; char ma[M][M]; int n,m; int dir[4][2]={{-1,0},{0,1},{0,-1},{1,0}}; bool maphaten(int x,int y)//马哈顿距离判断鬼魂是否会与人相遇 { if(x>=0&&x<n&&y>=0&&y<m&&ma[x][y]!='X') { for(int i=0;i<2;i++) { if(abs(x-zz[i].x)+abs(y-zz[i].y)<=2*step) return false; } return true; } return false; } queue<node>q[3]; void clear()//记得清空队列 { for(int i=0;i<3;i++) while(!q[i].empty()) q[i].pop(); } bool bfs(int num,int move_step,char s,char e)//num:mm或是gg,move_step:每秒走的步数 { q[2]=q[num];//另外开个队列保存 for(int i=0;i<move_step;i++) { node u,v; while(!q[2].empty()) { u=q[2].front(); q[2].pop(); q[num].pop(); if(!maphaten(u.x,u.y)) continue; for(int k=0;k<4;k++) { v=u; v.x=u.x+dir[k][0]; v.y=u.y+dir[k][1]; if(!maphaten(v.x,v.y)||ma[v.x][v.y]==s) continue; if(ma[v.x][v.y]==e) return true;//s与e相遇 ma[v.x][v.y]=s; q[num].push(v); } } q[2]=q[num];//把走了第i步的状态保存到q[2],以免重复 } return false; } int BFS() { step=0; clear(); q[0].push(mm); q[1].push(gg); while(!q[0].empty()&&!q[1].empty()) { step++; if(bfs(0,3,'M','G')||bfs(1,1,'G','M')) return step; } return -1; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int k=0; for(int i=0;i<n;i++) { scanf("%s",ma[i]); for(int j=0;j<m;j++) { if(ma[i][j]=='M') mm=node(i,j); else if(ma[i][j]=='G') gg=node(i,j); else if(ma[i][j]=='Z') zz[k++]=node(i,j); } } printf("%d\n",BFS()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。