首页 > 代码库 > nefu 1191 平行宇宙 （bfs）
nefu 1191 平行宇宙 （bfs）
Description
小k是时空贸易者，他经常在两个平行宇宙之间往来经商，现在他要从S点到达E点，问最少需要多长时间。（已知小k在同一个宇宙中只能向上下左右四个方向移动，每次移动需要1个单位时间，且不能在危险小行星带‘#‘中移动，遇到黑洞‘O‘时，他会被瞬间吸入另一个宇宙的对应的同一位置，比如从一个宇宙的黑洞处(2,2)必须且只能移动到另一个宇宙的(2,2)位置）
Input
多组输入数据，每组数据第一行包含两个整数n,m（2<=n,m<=1000），表示两个宇宙的大小。接下来n行表示第一个宇宙，再接下来n行表示第二个宇宙。
Output
每组数据输出一个整数，表示最短时间，如果不能到达目的地，输出-1
Sample Input
4 6#S##E##.##..#.O.#.#####.#######.#####..O####...O
Sample Output
11
// 其实这题不难，但是要注意细节问题
#include <iostream>#include <cstring>#include <cstdio>#include <queue>using namespace std;char data[2][1005][1005];int visit[2][1005][1005];int ki,kj,kk,ei,ej,ek;int n,m;int to[4][2]={{0,1},{0,-1},{1,0},{-1,0}};struct node{ int i; int j; int k; int time;};int go(int i,int j,int k){ if(j>=0&&j<n&&k>=0&&k<m&&data[i][j][k]!=‘#‘) return 1; return 0;}void bfs(){ node st,ed; queue <node> q; st.i=ki; st.j=kj; st.k=kk; st.time=0; memset(visit,0,sizeof(visit)); visit[ki][kj][kk]=1; q.push(st); while(!q.empty()) { st=q.front(); q.pop(); if(st.i==ei&&st.j==ej&&st.k==ek) { cout<<st.time<<endl; return ; } if(data[st.i][st.j][st.k]==‘O‘) { int t=1; if(st.i==1) t=0; if(data[t][st.j][st.k]!=‘O‘&&data[t][st.j][st.k]!=‘#‘&&visit[t][st.j][st.k]==0) { //O的对面是O或#时不能走 st.i=t; visit[t][st.j][st.k]=1; } else continue;//看队列中的下一个 } for(int i=0;i<4;i++) { ed.i=st.i; ed.j=st.j+to[i][0]; ed.k=st.k+to[i][1]; if(go(ed.i,ed.j,ed.k)&&visit[ed.i][ed.j][ed.k]==0) { visit[ed.i][ed.j][ed.k]=1; ed.time=st.time+1; q.push(ed); } } } cout<<"-1"<<endl; return ;}int main(){ while(cin>>n>>m) { for(int i=0;i<2;i++) { for(int j=0;j<n;j++) { scanf("%s",data[i][j]);//减少时间 for(int k=0;k<m;k++) { if(data[i][j][k]==‘S‘) { ki=i;kj=j;kk=k; } if(data[i][j][k]==‘E‘) { ei=i;ej=j;ek=k; } } } } bfs(); } return 0;}
nefu 1191 平行宇宙 （bfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。