首页 > 代码库 > poj-2251

poj-2251

2024-07-03 02:04:47   223人阅读

题意：

首先会输入个 数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 }
View Code

 


联系
我们