【搜索之BFS】杭电 hdu 1240 Asteroids!
?
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------// Copyright (c) 2012 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=1240 Name : 1240 Asteroids! Date : Wednesday, April 4, 2012 Time Stage : half an hour Result:57033432012-04-04 15:07:36Accepted12400MS296K2347 BC++pyyTest Data :Review :水题一枚//----------------------------------------*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#include <vector>#include <algorithm>#include <iostream>#include <queue>using namespace std ;#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value#define max(x, y) ((x) > (y) ? (x) : (y))#define min(x, y) ((x) < (y) ? (x) : (y))#define INF (0x3f3f3f3f)#define MAXN (12)#define DB /##/#define LL __int64struct NODE {int x, y, z;int step;bool operator== (const NODE &nd) {return x == nd.x && y == nd.y && z == nd.z;}};#define SPACE(nd)space[(nd).z][(nd).y][(nd).x]#define MAP(nd)map[(nd).z][(nd).y][(nd).x]#define BEGSPACE(beg)#define ENDSPACE(end)#define _IN_S(x)(0 <= (x) && (x) < n)#define _IN(nd)(_IN_S(nd.x) && _IN_S(nd.y) && _IN_S(nd.z))const int dir[6][3] = {0,0,1, 0,0,-1, 0,1,0, 0,-1,0, 1,0,0, -1,0,0};charmap[MAXN][MAXN][MAXN];intn;NODEspace[MAXN][MAXN][MAXN], beg, end;void bfs(){int i, j, k;queue<NODE>q;NODEt, nn;beg.step = 0;q.push(beg);while (!q.empty()){t = q.front();q.pop();SPACE(t) = t;if (t == END)break;for (i = 0; i < 6; ++i){nn = t;nn.z += dir[i][0];nn.y += dir[i][1];nn.x += dir[i][2];if (!_IN(nn) || 'X' == MAP(nn))continue;++nn.step;MAP(nn) = 'X';q.push(nn);}}}int main(){int i, j, k;char st[MAXN], en[MAXN];while (scanf("%s %d", st, &n) != EOF){MEM(space, INF);for (i = 0; i < n; ++i){for (j = 0; j < n; ++j){getchar();for (k = 0; k < n; ++k){scanf("%c", &map[i][j][k]);}}}scanf("%d %d %d", &beg.x, &beg.y, &beg.z);scanf("%d %d %d", &end.x, &end.y, &end.z);getchar();scanf("%s", en);bfs();if (INF == END.step)printf("NO ROUTE\n");elseprintf ("%d %d\n", n, END.step);}return 0;}?