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
小鼠標 閱讀(239)
評論(0) 編輯 收藏 引用 所屬分類:
圖論