[1253]胜利大逃亡-bfs.cpp

HDUOJ_ACM题目集合~~希望各位能用得上

// [1253]胜利大逃亡-wfs.cpp : 定义控制台应用程序的入口点。
//

//#include "stdafx.h"
//#include<iostream>
//using namespace std;
//#include<queue>
//
//struct node
//{
//	int x,y,z;
//	int t;
//};
//int dir[6][3]={
//	-1,0,0,
//	1,0,0,
//	0,-1,0,
//	0,1,0,
//	0,0,-1,
//	0,0,1
//};
//int map[51][51][51];
//
//int main()
//{
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
//	int  i,j,k,n;
//	int a,b,c,time;
//	scanf("%d",&n);
//	while(n--)
//	{
//		int wall=0;
//		scanf("%d%d%d%d",&a,&b,&c,&time);
//		for(i=0;i<a;i++)
//		{
//			for(j=0;j<b;j++)
//			{
//				for(k=0;k<c;k++)
//				{
//					scanf("%d",&map[i][j][k]);
//					if(map[i][j][k]!=0)
//						wall++;
//				} 
//			}
//		}
//		if(a*b*c-wall<a+b+c-2||time<a+b+c-3)
//			cout<<-1<<endl;
//		else
//		{
//			node N,P;
//			N.x=0;N.y=0;N.z=0;N.t=0;
//			queue<node> Q;
//			Q.push(N);
//			map[0][0][0]=1;
//			bool f=0;
//			while(!Q.empty())
//			{
//				N=Q.front();Q.pop();
//				if(N.t<=time&& N.x == a-1 && N.y == b-1 && N.z == c-1)
//				{f=1;break;}
//				if(N.t>time)
//				{
//					f=0;break;
//				}
//    
//				for(i=0;i<6;i++)
//				{
//					int tx=N.x+dir[i][0];
//					int ty=N.y+dir[i][1];
//					int tz=N.z+dir[i][2];
//					if(tx>=0 && tx<a && ty>=0 && ty<b && tz>=0 && tz<c && !map[tx][ty][tz] )
//					{
//						P.x=tx;P.y=ty;P.z=tz;P.t=N.t+1;
//						if(P.t+a-1-P.x+b-1-P.y+c-1-P.z>time)
//						{
//							map[tx][ty][tz]=1;
//							continue;
//						}
//						Q.push(P);
//						map[tx][ty][tz]=1;  
//					}
//				}
//			}
//			if(!f) cout<<-1<<endl;
//			else cout<<N.t<<endl;
//		}
//	}
//}

#include "stdafx.h"
#include "stdio.h"
#include <queue>
using namespace std;

int map[51][51][51];
int a, b, c, t;
int dir[6][3] = {{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}};

class Node
{
public:
	int x, y, z, t;
};

int wfs()
{
	Node node, temp;
	queue<Node> q;
	map[0][0][0] = 1;
	node.x = node.y = node.z = node.t = 0;
	q.push(node);
	while (!q.empty())
	{
		node = q.front(); q.pop();
		if (node.x == a-1 && node.y == b-1 && node.z == c-1 && node.t <= t)
		{
			return node.t;
		}
		if (node.t > t)
			break;
		if (t - node.t < a + b + c - (node.x + node.y + node.z) - 3)
			continue;
		for (int i = 0; i < 6; i++)
		{
			temp.x = node.x + dir[i][0];
			temp.y = node.y + dir[i][1];
			temp.z = node.z + dir[i][2];
			temp.t = node.t + 1;
			if (map[temp.x][temp.y][temp.z] == 0 && temp.x >= 0 && temp.x < a && temp.y >=0 && temp.y < b && temp.z >=0 && temp.z < c)
			{
				q.push(temp);
				map[temp.x][temp.y][temp.z] = 1;
			}
		}
	}
	return -1;
}

int main()
{
	int ca;
	int i, j, k;
	int wall;
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);

	scanf("%d",&ca);
	while (ca--)
	{
		scanf("%d%d%d%d",&a,&b,&c,&t);
		wall = 0;
		for (i = 0; i < a; i++)
		{
			for (j = 0; j < b; j++)
			{
				for (k = 0; k < c; k++)
				{
					scanf("%d",&map[i][j][k]);
					if (map[i][j][k] != 0)
						wall++;
				}
			}
		}
		if (a+b+c-3>t || a*b*c < wall + a + b + c - 3)
		{
			printf("-1\n");
			continue;
		}
		printf("%d\n",wfs());
	}
	return 0;
}