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