poj 2251 3D地牢

#include<iostream>
#include<vector>
using namespace std;
#define N 32

char dun[N][N][N];
int vis[N][N][N];
int c,res;
int L,R,C;

typedef struct dir
{
	int l;
	int r;
	int c;
};
vector<dir> towards;
void getTowards()
{
	dir d1,d2,d3,d4,d5,d6;
	d1.l=0;d1.r=-1;d1.c=0;
	d2.l=0;d2.r=0;d2.c=1;
	d3.l=0;d3.r=1;d3.c=0;
	d4.l=0;d4.r=0;d4.c=-1;
	d5.l=-1;d5.r=0;d5.c=0;
	d6.l=1;d6.r=0;d6.c=0;
	towards.push_back(d1);
	towards.push_back(d2);
	towards.push_back(d3);
	towards.push_back(d4);
	towards.push_back(d5);
	towards.push_back(d6);
}
bool comp(dir a,dir b)
{
	if(a.l==b.l&&a.r==b.r&&a.c==b.c)
		return true;
	return false;
}
bool addin(dir a,dir b)
{
	int l,r,c;
	l=a.l+b.l;
	r=a.r+b.r;
	c=a.c+b.c;
	if(l>=0&&l<=L-1&&r>=0&&r<=R-1&&c>=0&&c<=C-1&&dun[l][r][c]!='#'&&!vis[l][r][c])
		return true;
	return false;
}
void dfs(dir s,dir e)
{
	if(comp(s,e))
	{
		res=c;
		return ;
	}
	vis[s.l][s.r][s.c]=1;
	c++;
	for(int i=0;i<towards.size();++i)
	{
		if(addin(s,towards[i]))
		{
			s.l+=towards[i].l;
			s.r+=towards[i].r;
			s.c+=towards[i].c;
			dfs(s,e);
			s.l-=towards[i].l;
			s.r-=towards[i].r;
			s.c-=towards[i].c;
		}
	}
	c--;
	vis[s.l][s.r][s.c]=0;
}

int main()
{
	getTowards();
	while(cin>>L>>R>>C)
	{
		if(L==0&&R==0&&C==0)
			break;
		dir s,e;
		c=0,res=0;
		for(int i=0;i<L;i++)
			for(int j=0;j<R;j++)
				for(int k=0;k<C;k++)
				{
					cin>>dun[i][j][k];
					vis[i][j][k]=0;
					if(dun[i][j][k]=='S')
					{
						s.l=i;s.r=j;s.c=k;
					}
					if(dun[i][j][k]=='E')
					{
						e.l=i;e.r=j;e.c=k;
					}
				}
		dfs(s,e);
		if(res==0)
			cout<<"Trapped!"<<endl;
		else
			cout<<"Escaped in "<<res<<" minute(s)."<<endl;
	}
	return 0;
}

补充：软件开发 , C++ ,

上一个：hdu 1269 迷宫城堡 (Kosaraju+缩点)
下一个：棋盘覆盖问题 C++实现11