1253 胜利大逃亡.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

int a,b,c,t,ut;
bool map[51][51][51];

struct infor
{
	int x,y,z;
	int nt;
	inline void maketag()
	{
		map[x][y][z]=true;
	}
	inline bool isOK()
	{
		if(map[x][y][z] || x<0 || y<0 || z<0 || x>=a || y>=b || z>=c)
			return false;
		return true;
	}
	inline bool isEnd()
	{
		if(x==a-1 && y==b-1 && z==c-1)
			return true;
		return false;
	}
};
queue<infor> SQ;


void bfs()
{
	infor it,now;
	
	while(!SQ.empty())
	{
		now=SQ.front();
		SQ.pop();
		if(now.nt>t)
			return;
		if(now.isEnd())
		{
			ut=now.nt;
			return;
		}
		
		//now.maketag();注意标记时间 
		
		it=now;
		it.x++;it.nt++;
		if(it.isOK())
			SQ.push(it) , it.maketag();
			
		it=now;
		it.x--;it.nt++;
		if(it.isOK())
			SQ.push(it) , it.maketag();
			
		it=now;
		it.y++;it.nt++;
		if(it.isOK())
			SQ.push(it) , it.maketag();
			
		it=now;
		it.y--;it.nt++;
		if(it.isOK())
			SQ.push(it) , it.maketag();
			
		it=now;
		it.z++;it.nt++;
		if(it.isOK())
			SQ.push(it) , it.maketag();
			
		it=now;
		it.z--;it.nt++;
		if(it.isOK())
			SQ.push(it) , it.maketag();
	}
}

int main()
{
	int i,j,k,ct,roads;
	infor s;
	scanf("%d",&ct);
	while(ct--)
	{
		roads=0;
		scanf("%d %d %d %d",&a,&b,&c,&t);
		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])
						roads++;
				}
				
		ut=-1;
		s.x=s.y=s.z=s.nt=0;
		while(!SQ.empty())	
			SQ.pop();
		
		if(a+b+c<=t && a+b+c<=roads-1)
		{
			SQ.push(s);
			s.maketag();
			bfs();
		}

		printf("%d\n",ut);
	}
	return 0;
}