B - Dungeon Master
POJ - 2251
深搜:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int map[31][31][31];
int sx,sy,sz,tx,ty,tz;
int dx[6]={1,-1,0,0,0,0};
int dy[6]={0,0,1,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
int n,m,k,ans=0x7f7f7f7f;
void dfs(int x,int y,int z,int tot){
if(tot>ans) return ;
if(x==tx&&y==ty&&z==tz){
ans=min(ans,tot);
return ;
}
for(int i=0;i<6;i++){
int cx=x+dx[i];
int cy=y+dy[i];
int cz=z+dz[i];
if(cx>=1&&cx<=n&&cy>=1&&cy<=m&&cz>=1&&cz<=k&&!map[cx][cy][cz]){
map[cx][cy][cz]=1;
dfs(cx,cy,cz,tot+1);
map[cx][cy][cz]=0;
}
}
}
int main(){
while(scanf("%d%d%d",&k,&n,&m)&&n!=0&&m!=0&&k!=0){
for(int c=1;c<=k;c++)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char x;cin>>x;
if(x=='#') map[i][j][c]=1;
else map[i][j][c]=0;
if(x=='S'){ sx=i;sy=j;sz=c; }
if(x=='E'){ tx=i;ty=j;tz=c; }
}
map[sx][sy][sz]=1;
dfs(sx,sy,sz,0);
if(ans!=0x7f7f7f7f) printf("Escaped in %d minute(s).\n",ans);
else printf("Trapped!\n");ans=0x7f7f7f7f;
}
}
/*
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct nond{
int x,y,z,tot;
};
queue<nond>que;
int map[31][31][31];
int sx,sy,sz,tx,ty,tz;
int dx[6]={1,-1,0,0,0,0};
int dy[6]={0,0,1,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
int n,m,k,ans=0x7f7f7f7f;
void bfs(int x,int y,int z){
nond tmp;tmp.x=x;tmp.y=y;tmp.z=z;tmp.tot=0;
que.push(tmp);
while(!que.empty()){
nond now=que.front();
que.pop();
for(int i=0;i<6;i++){
int cx=now.x+dx[i];
int cy=now.y+dy[i];
int cz=now.z+dz[i];
int ctot=now.tot+1;
if(cx==tx&&cy==ty&&cz==tz){ ans=min(ctot,ans); }
if(cx>=1&&cx<=n&&cy>=1&&cy<=m&&cz>=1&&cz<=k&&!map[cx][cy][cz]){
map[cx][cy][cz]=1;
nond c;c.x=cx;c.y=cy;c.z=cz;c.tot=ctot;
que.push(c);
}
}
}
}
int main(){
while(scanf("%d%d%d",&k,&n,&m)&&n!=0&&m!=0&&k!=0){
for(int c=1;c<=k;c++)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char x;cin>>x;
if(x=='#') map[i][j][c]=1;
else map[i][j][c]=0;
if(x=='S'){ sx=i;sy=j;sz=c; }
if(x=='E'){ tx=i;ty=j;tz=c; }
}
map[sx][sy][sz]=1;
bfs(sx,sy,sz);
if(ans!=0x7f7f7f7f) printf("Escaped in %d minute(s).\n",ans);
else printf("Trapped!\n");ans=0x7f7f7f7f;
}
}
/*
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0
*/
细雨斜风作晓寒。淡烟疏柳媚晴滩。入淮清洛渐漫漫。
雪沫乳花浮午盏,蓼茸蒿笋试春盘。人间有味是清欢。