题意:
首先会输入个 数l,r,c 接下来会如数l个r*c的矩阵,其实点为S,结束点为E,每个点都可以向六个方向走,东,南,西,北,上,下,求从起始点到结束点的最短路径。
Sample Input
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0
解题思路:
其实看到最短路径就该想到用BFS求解,但是在POJ分类上是分为DFS的,但是DFS不知道该怎么求解。若用BFS其实就跟二维的BFS是一样的,就是三维的多了两个方向,并且在判断的时候
也需要加一些条件。并且开数组的时候要尽量开的大一些,开小了会RE。
具体代码:
1 #include<iostream> 2 #include<queue> 3 #include<cstring> 4 #include<stdio.h> 5 using namespace std; 6 char map[40][40][40]; 7 bool visit[40][40][40]; 8 int xx[]={1,-1,0,0,0,0}; 9 int yy[]={0,0,0,0,-1,1}; 10 int zz[]={0,0,-1,1,0,0}; 11 12 int beginx,beginy,beginz; 13 struct Node 14 { 15 int l,r,c; 16 int step; 17 Node (int l1,int r1,int c1,int step1):l(l1),r(r1),c(c1),step(step1){}; 18 }; 19 int h,g,f; 20 int length[30000]; 21 int bfs() 22 { 23 queue<Node> q; 24 Node node(beginx,beginy,beginz,0); 25 memset(visit,false,sizeof(visit)); 26 memset(length,0,sizeof(length)); 27 while(!q.empty()) q.pop(); 28 q.push(node); 29 while(!q.empty()) 30 { 31 node=q.front(); 32 q.pop(); 33 if(map[node.l][node.r][node.c]==‘E‘) 34 return node.step; 35 for(int i=0;i<6;i++) 36 { 37 int x=node.l+xx[i]; 38 int y=node.r+yy[i]; 39 int z=node.c+zz[i]; 40 if(x>=0&&x<=h&&y>=0&&y<=g&&z>=0&&z<=f&&!visit[x][y][z]&&(map[x][y][z]==‘.‘||map[x][y][z]==‘E‘)) 41 { 42 visit[x][y][z]=true; 43 Node temp(x,y,z,node.step+1); 44 q.push(temp); 45 46 } 47 } 48 } 49 return 0; 50 } 51 int main() 52 { 53 while(1) 54 { 55 cin>>h>>g>>f; 56 if(h==0&&g==0&&f==0) 57 break; 58 for(int i=0;i<h;i++) 59 for(int j=0;j<g;j++) 60 for(int k=0;k<f;k++) 61 { 62 cin>>map[i][j][k]; 63 if(map[i][j][k]==‘S‘) 64 { 65 beginx=i; 66 beginy=j; 67 beginz=k; 68 } 69 70 } 71 int tempd=bfs(); 72 if(tempd) printf("Escaped in %d minute(s).\n",tempd); 73 else printf("Trapped!\n"); 74 } 75 //system("pause"); 76 return 0; 77 }
原文:http://www.cnblogs.com/baoluqi/p/3710311.html