POJ 2251 Dungeon Master (BFS最短路)

三维空间里BFS最短路

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
using namespace std;
char mapp[][][];
bool vis[][][];
struct Node {
int f,r,c,step;
} s,e;
int l,r,c;
int dir[][]= {{,,},{,,-},{,,},{,-,},{,,},{-,,}}; bool ok(int x,int y,int z) {
if(x< || y< || z< || x>=l || y>=r || z>=c)
return ;
else if(mapp[x][y][z] == '#')
return ;
else if(vis[x][y][z])
return ;
return ;
}
int dfs() {
Node q,t;
queue<Node>Q;
q.f=s.f,q.r=s.r,q.c=s.c;
q.step=;
vis[s.f][s.r][s.c]=;
Q.push(q);
while(!Q.empty()) {
t=Q.front();
Q.pop();
Node a;
if(t.f==e.f&&t.r==e.r&&t.c==e.c) {
return t.step;
}
for(int i=; i<; i++) {
a.f=t.f+dir[i][];
a.r=t.r+dir[i][];
a.c=t.c+dir[i][];
if(!ok(a.f,a.r,a.c))
continue;
vis[a.f][a.r][a.c]=;
a.step=t.step+;
Q.push(a);
}
}
return ;
}
int main() {
while(scanf("%d%d%d",&l,&r,&c),l||r||c) {
memset(vis,,sizeof(vis));
for(int k=; k<l; k++) {
for(int i=; i<r; i++) {
scanf("%s",mapp[k][i]);//遇到空格自动结束
for(int j=; j<c; j++) {
//scanf("%c",mapp[k][i][j]);
if(mapp[k][i][j]=='S') {
s.f=k;
s.r=i;
s.c=j;
}
if(mapp[k][i][j]=='E') {
e.f=k;
e.r=i;
e.c=j;
}
}
}
}
int ans;
ans=dfs();
if(ans)
printf("Escaped in %d minute(s).\n",ans);
else
printf("Trapped!\n");
}
return ;
}
上一篇:用C# sqlserver实现增删改查


下一篇:Android高手进阶教程(十七)之---Android中Intent传递对象的两种方法(Serializable,Parcelable)!