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[][][];
int visit[][][];
int ki,kj,kk,ei,ej,ek;
int n,m;
int to[][]={{,},{,-},{,},{-,}}; struct node
{
int i;
int j;
int k;
int time;
}; int go(int i,int j,int k)
{
if(j>=&&j<n&&k>=&&k<m&&data[i][j][k]!='#')
return ;
return ;
} void bfs()
{
node st,ed;
queue <node> q;
st.i=ki;
st.j=kj;
st.k=kk;
st.time=;
memset(visit,,sizeof(visit));
visit[ki][kj][kk]=;
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=;
if(st.i==)
t=;
if(data[t][st.j][st.k]!='O'&&data[t][st.j][st.k]!='#'&&visit[t][st.j][st.k]==)
{
//O的对面是O或#时不能走
st.i=t;
visit[t][st.j][st.k]=;
}
else continue;//看队列中的下一个
}
for(int i=;i<;i++)
{
ed.i=st.i;
ed.j=st.j+to[i][];
ed.k=st.k+to[i][];
if(go(ed.i,ed.j,ed.k)&&visit[ed.i][ed.j][ed.k]==)
{
visit[ed.i][ed.j][ed.k]=;
ed.time=st.time+;
q.push(ed);
}
}
}
cout<<"-1"<<endl;
return ;
} int main()
{
while(cin>>n>>m)
{
for(int i=;i<;i++)
{
for(int j=;j<n;j++)
{
scanf("%s",data[i][j]);//减少时间
for(int k=;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 ;
}

上一篇:[转]Linux中set,env和export这三个命令的区别


下一篇:Linux 休眠,挂起(待机),关机等几个命令的区别及如何实现;如何启用Ubuntu的休眠模式