http://poj.org/problem?id=2251一道三维的迷宫题，要求求出最短路径。
广度优先搜索的框架是很清晰的，就是在code的时候一些细节注意不到，就只好调啊，调啊，就这样两个小时就过去了%>_<%
说一下代码思路吧：
1.读入数据
2.预处理迷宫，主要是给迷宫周围加一道墙，便于统一处理
3.找到起点'S'，和终点'E'的坐标分别记录在p0、p1中
4.从起点开始进行广搜，直到队列q空(qf == fr)或到达目的地时结束
5.输出结果
注意：
1.广搜的时候要注意改变走过节点的状态，避免二次走过同一个点。
2.对于每一个节点，候选的子节点有6个，分别是上下左右前后，可由二维数组d[][]记录各个增量，拓展节点时只要将当前节点与对应的增量相加既是下个节点的坐标。这样做的目的是便于统一处理，用一个for循环就可以把6个方向都遍历一遍。
3.每个可达节点到起点'S'的距离记录在st[][]中，子节点比其父节点的距离大1。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LENMP 33
#define LENQ 30000
typedef struct
{
int l;
int r;
int c;
}Point;
int main()
{
int i, j, k;
Point p0, p1;
Point q[LENQ];
int qf, qr;
char mp[LENMP][LENMP][LENMP];
int st[LENMP][LENMP][LENMP];
int L, R, C;
int find;
int d[6][3] = {0, 0, 1, 0, 0, -1, 0, 1, 0, 0, -1, 0, 1, 0, 0, -1, 0, 0};
scanf("%d%d%d", &L, &R, &C);
while(L + R + C != 0)
{
for(i = 1; i <= L; i++)//read mp
{
for(j = 1; j <= R; j++)
{
scanf("%s", &mp[i][j][1]);
}
}
for(i = 0; i <= R + 1; i++)//init mp
for(j = 0; j <= C + 1; j++)
mp[0][i][j] = mp[L + 1][i][j] = '#';
for(i = 0; i <= L + 1; i++)
for(j = 0; j <= C + 1; j++)
mp[i][0][j] = mp[i][R + 1][j] = '#';
for(i = 0; i <= L + 1; i++)
for(j = 0; j <= R + 1; j++)
mp[i][j][0] = mp[i][j][C + 1] = '#';
for(i = 0; i <= L + 1; i++)//find 'S' &&''E'
for(j = 0; j <= R + 1; j++)
for(k = 0; k <= C + 1; k++)
{
if(mp[i][j][k] == 'S')
{
p0.l = i;
p0.r = j;
p0.c = k;
}
else if(mp[i][j][k] == 'E')
{
p1.l = i;
p1.r = j;
p1.c = k;
}
}
qf = 0;// init queue
qr = 1;
q[qf].l = p0.l;
q[qf].r = p0.r;
q[qf].c = p0.c;
find = 0;
st[p0.l][p0.r][p0.c] = 0;
while(qf != qr && find == 0)
{
int l, r, c;
int l2, r2, c2;
l = q[qf].l;
r = q[qf].r;
c = q[qf].c;
qf++;// deQueue
for(i = 0; i < 6; i++)
{
l2 = l + d[i][0];
r2 = r + d[i][1];
c2 = c + d[i][2];
if(mp[l2][r2][c2] == 'E')// find 'E'
{
st[l2][r2][c2] = st[l][r][c] + 1;
find = 1;
break;
}
else if(mp[l2][r2][c2] == '.')// can walk
{
st[l2][r2][c2] = st[l][r][c] + 1;
mp[l2][r2][c2] = '#';//change mp
q[qr].l = l2;//inQueue
q[qr].r = r2;
q[qr].c = c2;
qr++;
}
}
}
if(find == 1)
{
printf("Escaped in %d minute(s).\n", st[p1.l][p1.r][p1.c]);
}
else
printf("Trapped!\n");
scanf("%d%d%d", &L, &R, &C);
}
//system("pause");
}posted on 2012-06-05 12:55
小鼠标 阅读(225)
评论(0) 编辑 收藏 引用 所属分类:
图论