【搜索之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:
5703343	2012-04-04 15:07:36	Accepted	1240
0MS	296K	2347 B
C++	pyy


Test 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 __int64

struct 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 BEG	SPACE(beg)
#define END	SPACE(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};

char	map[MAXN][MAXN][MAXN];

int		n;

NODE	space[MAXN][MAXN][MAXN], beg, end;

void bfs()
{
	int i, j, k;
	queue<NODE>	q;
	NODE	t, 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");
		else
			printf ("%d %d\n", n, END.step);
	}
	return 0;
}