簡(jiǎn)單的走迷宮，廣搜求最短路徑，要把坐標(biāo)搞清楚。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LEN 14
#define QLEN 100000
typedef struct
{
int x;
int y;
int z;
}Point;
typedef struct
{
int f;
int r;
Point *p;
}Queue;
int d[6][3] =
{
0, 0, 1,
0, 0, -1,
1, 0, 0,
-1, 0, 0,
0, 1, 0,
0, -1, 0
};
char sp[LEN][LEN][LEN];//space map
int rl[LEN][LEN][LEN];//road length
Point bg, ed;
int N;
void BFS()
{
int i, j;
Point t;
int x, y, z;
int find = 0;
Queue q;
q.f = q.r = 0;
q.p = (Point*)malloc(sizeof(Point) * QLEN);
q.p[q.f] = bg;
q.r++;
while(q.f != q.r && !find)
{
t = q.p[q.f];
q.f = (q.f + 1) % QLEN;//DeQueue
for(i = 0; i < 6; i++)
{
x = t.x + d[i][0];
y = t.y + d[i][1];
z = t.z + d[i][2];
if(sp[z][y][x] == 'O')//can walk
{
sp[z][y][x] = 'X';//change mp
rl[z][y][x] = rl[t.z][t.y][t.x] + 1;//change rl
q.p[q.r].x = x;//EnQueue
q.p[q.r].y = y;
q.p[q.r].z = z;
q.r = (q.r + 1) % QLEN;
}
else if(sp[z][y][x] == 'E')
{
rl[z][y][x] = rl[t.z][t.y][t.x] + 1;//change rl
find = 1;
}
}
}
free(q.p);
}
int main()
{
int i, j, k, m;
char s1[LEN];
int gard = 100;
while(scanf("%s%d", s1, &N) == 2 && gard--)
{
getchar();
for(i = 1; i <= N; i++)//read space map
for(j = 1; j <= N; j++)
{
for(k = 1; k <= N; k++)
sp[i][j][k] = getchar();
getchar();
}
scanf("%d%d%d", &bg.x, &bg.y, &bg.z);//read point
scanf("%d%d%d", &ed.x, &ed.y, &ed.z);
getchar();
gets(s1);//read END
//getchar();
bg.x += 1;
bg.y += 1;
bg.z += 1;
ed.x += 1;
ed.y += 1;
ed.z += 1;
sp[bg.z][bg.y][bg.x] = 'B';
sp[ed.z][ed.y][ed.x] = 'E';
for(i = 0; i <= N + 1; i++)//init map
for(j = 0; j <= N + 1; j++)
{
sp[i][j][0] = sp[i][j][N + 1] = sp[N + 1][i][j] = '#';
sp[0][i][j] = sp[i][0][j] = sp[i][N +1][j] = '#';
}
for(i = 0; i < LEN; i++)//init road length
for(j = 0; j < LEN; j++)
for(k = 0; k < LEN; k++)
rl[i][j][k] = 0;
BFS();
if(rl[ed.z][ed.y][ed.x] != 0)
printf("%d %d\n", N, rl[ed.z][ed.y][ed.x]);
else if(bg.x == ed.x && bg.y == ed.y && bg.z == ed.z)
printf("%d 0\n", N);
else
printf("NO ROUTE\n");
}
}
這道題交了很多遍一直WA，很是郁悶。剛開(kāi)始以為自己的隊(duì)列沒(méi)有管理好，換成STL隊(duì)列問(wèn)題依舊，又懷疑輸出格式的問(wèn)題，修改后問(wèn)題依舊。最后終于看到BFS（）中有一個(gè)break（寫在了for循環(huán)里面），這樣是跳不出while的，用標(biāo)志find代替break后果然AC！
想和寫之間的確有很大的差距，多些代碼才是硬道理。
scanf("%s",s1)讀取字符串時(shí)對(duì)前面的空白符有過(guò)濾作用，并且字符串中間的空白符將被認(rèn)為字符串的結(jié)束標(biāo)志，空白符不會(huì)被讀入
gets(s1)讀取字符串時(shí)對(duì)前面和中間的空白符都沒(méi)有過(guò)濾，只有換行符才會(huì)被認(rèn)為是字符串的結(jié)束標(biāo)志，該換行符不被認(rèn)為是字符串的一部分
posted on 2012-03-04 12:54
小鼠標(biāo) 閱讀(229)
評(píng)論(0) 編輯 收藏 引用