2973408_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

struct node
{
	char map[13][13];
}slice[13];

struct pos
{
	int x, y, z;
	int way;
};

int n, mark[13][13][13];
pos st, ed;
int mov[][3] = {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};

int valid(pos t)
{
	if(t.x < 0 || t.y < 0 || t.z < 0)
		return 0;
	if(t.x >= n || t.y >= n || t.z >= n)
		return 0;
	return 1;
}

void bfs()
{
	queue <pos> que;
	pos t, q;
	int i;

	que.push(st);
	mark[st.x][st.y][st.z] = 1;
	while(!que.empty())
	{
		t = que.front();
		que.pop();
		for(i = 0; i < 6; i++)
		{
			q = t;
			q.x += mov[i][0];
			q.y += mov[i][1];
			q.z += mov[i][2];
			if(valid(q)&&slice[q.x].map[q.y][q.z]=='O'&&mark[q.x][q.y][q.z]==0)
			{
				mark[q.x][q.y][q.z] = 1;
				q.way++;
				if(q.x==ed.x&&q.y==ed.y&&q.z==ed.z)
				{
					printf("%d %d\n",n,q.way);
				}
				que.push(q);
			}
		}
	}
	puts("NO ROUTE");
}

int main()
{
	int i, j;
	string s;	

	while(cin>>s)
	{
		cin >> n;
		memset(mark,0,sizeof(mark));
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
			{
				cin >> slice[i].map[j];
			}
		}
		st.way = ed.way = 0;
		cin >> st.z >> st.y >> st.x;
		cin >> ed.z >> ed.y >> ed.x;
		cin >> s;
		if(st.z==ed.z&&st.y==ed.y&&st.x==ed.x)
		{
			printf("%d 0\n",n);
			continue;
		}
		bfs();
	}
	return 0;
}