| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这题很郁闷...计划一小时之内...搞了三四小时。皆因两个问题!犯的错误是:
1 处理完一层结点后mid 应该指向队列的下一层结点的最后一个,也就是tail. 我却指向了下一层的第一个。
3 对某位置标志visited 要在放进队列前标志,而不是等到用head 从队列头取出才标志为visited. 后者会导致同一结点重复入列,内存畸形增长
#include <stdio.h>
#include <string.h>
struct map{ /* 三维节点坐标,队列用 */
char d;
char r;
char c;
};
char dun[30][30][30]; /* 地图 */
int d, r, c; /* 3D坐标界限 */
int dir[6][3] = { /* 移动方向 */
{1, 0, 0},
{0, 0, -1},
{0, -1, 0},
{0, 0, 1},
{0, 1, 0},
{-1, 0, 0},
};
int bfs(int sd, int sr, int sc)
{
struct map que[27000]; /* 队列 */
int mid, head, tail, step, nd, nr, nc, i; /* head, tail 队列的和尾,当head==mid时,处理完一层节点 */
memset(que, 0, sizeof(que)); /* nd, nr, nc当前节点的相邻节点, next d, next r,next c*/
step = mid = head = tail = 0;
que[head].d = sd; /* 初始化 */
que[head].r = sr;
que[head].c = sc;
for (tail ; head <= tail; head++)
{
if(dun[que[head].d][que[head].r][que[head].c] == 'E')
{
return step;
}
for (i = 0; i < 6; i++)
{
nd = que[head].d + dir[i][0];
nr = que[head].r + dir[i][1];
nc = que[head].c + dir[i][2];
if (dun[nd][nr][nc] == '#' ||
nd < 0 || nd >= d || nr < 0 || nr >= r || nc < 0 || nc >= c)
{
continue;
}
if (dun[nd][nr][nc] == '.')
{
dun[nd][nr][nc] = '#';
}
tail++;
que[tail].d = nd;
que[tail].r = nr;
que[tail].c = nc;
}
if (mid == head)
{
step++;
mid = tail;
}
}
return 0;
}
main()
{
int sd, sr, sc, i, j, k, sum;
scanf("%d%d%d", &d, &r, &c);
while (d)
{
memset(dun, 0, sizeof(dun));
for (i=0; i<d; i++)
{
for (j=0; j<r; j++)
{
scanf("%s", &dun[i][j]);
}
}
for (i=0; i<d; i++)
{
for (j=0; j<r; j++)
{
for (k=0; k<c; k++)
{
if (dun[i][j][k] == 'S')
{
sd = i, sr = j, sc = k;
goto here;
}
}
}
}
here:
sum = bfs(sd, sr, sc);
if (sum)
{
printf("Escaped in %d minute(s).\n", sum);
}
else
{
printf("Trapped!\n");
}
scanf("%d%d%d", &d, &r, &c);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator