简单的走迷宫，广搜求最短路径，要把坐标搞清楚。
#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，很是郁闷。刚开始以为自己的队列没有管理好，换成STL队列问题依旧，又怀疑输出格式的问题，修改后问题依旧。最后终于看到BFS（）中有一个break（写在了for循环里面），这样是跳不出while的，用标志find代替break后果然AC！
想和写之间的确有很大的差距，多些代码才是硬道理。
scanf("%s",s1)读取字符串时对前面的空白符有过滤作用，并且字符串中间的空白符将被认为字符串的结束标志，空白符不会被读入
gets(s1)读取字符串时对前面和中间的空白符都没有过滤，只有换行符才会被认为是字符串的结束标志，该换行符不被认为是字符串的一部分
posted on 2012-03-04 12:54
小鼠标 阅读(211)
评论(0) 编辑 收藏 引用