poj 2251 Dungeon Master (三维bfs)

  1
  2   
  3   /*************************************************************************
  4   	> File Name: code/2015summer/searching/B.cpp
  5   	> Author: 111qqz
  6   	> Email: rkz2013@126.com 
  7   	> Created Time: 2015年07月17日 星期五 16时47分46秒
  8    ************************************************************************/
  9   
 10   #include<iostream>
 11   #include<iomanip>
 12   #include<cstdio>
 13   #include<algorithm>
 14   #include<cmath>
 15   #include<cstring>
 16   #include<string>
 17   #include<map>
 18   #include<set>
 19   #include<queue>
 20   #include<vector>
 21   #include<stack>
 22   using namespace std;
 23   #define REP(i, n) for (int i=0;i<int(n);++i)  
 24   typedef long long LL;
 25   typedef unsigned long long ULL;
 26   const int N=40;
 27   char st[N][N][N];
 28   int d[N][N][N];
 29   int l,r,c;
 30   int sx,sy,sz,tx,ty,tz;
 31   int dirx[6]={1,-1,0,0,0,0};
 32   int diry[6]={0,0,-1,1,0,0};
 33   int dirz[6]={0,0,0,0,1,-1};
 34   
 35   bool ok(int x,int y,int z)
 36   {
 37       if (z>=0&&z<l&&x>=0&&x<r&&y>=0&&y<c&&d[z][x][y]==-1&&st[z][x][y]!='#')
 38   	  return true;
 39       return false;
 40   }
 41   
 42   void bfs()
 43   {
 44       memset(d,-1,sizeof(d));
 45       queue<int>x;
 46       queue<int>y;
 47       queue<int>z;
 48       x.push(sx);
 49       y.push(sy);
 50       z.push(sz);
 51       d[sz][sx][sy]=0;
 52       while (!x.empty()&&!y.empty()&&!z.empty())
 53       {
 54   	  int prex = x.front();x.pop();
 55   	  int prey = y.front();y.pop();
 56   	  int prez = z.front();z.pop();
 57   	  for ( int  i = 0 ; i < 6 ; i++ )
 58   	  {
 59   		int newx = prex+dirx[i];
 60   		int newy = prey+diry[i];
 61   		int newz = prez+dirz[i];
 62   		bool flag = ok(newx,newy,newz);
 63   		if (flag)
 64   		{
 65   		    d[newz][newx][newy]=d[prez][prex][prey]+1;
 66   		    x.push(newx);
 67   		    y.push(newy);
 68   		    z.push(newz);
 69   		}
 70   	  }
 71   
 72       }
 73   }
 74   
 75   int main()
 76   {
 77       while (scanf("%d %d %d",&l,&r,&c))
 78       {
 79   	  if (l==0&&r==0&&c==0)
 80   		break;
 81   	  for ( int i = 0 ; i < l ; i++)
 82   	  {
 83   		for ( int j = 0 ; j < r; j++)
 84   		    scanf("%s",st[i][j]);
 85   	  }
 86   	  for ( int i = 0 ; i < l ; i++ )
 87   	  {
 88   		for ( int j = 0 ; j < r ; j ++)
 89   		{
 90   		    for ( int k =  0 ;  k < c ; k++ )
 91   		    {
 92   			  if (st[i][j][k]=='S')
 93   			  {
 94   				sx = j;
 95   				sy = k;
 96   				sz = i;
 97   			  }
 98   			  if (st[i][j][k]=='E')
 99   			  {
100   				tx = j;
101   				ty = k;
102   				tz = i;
103   			  }
104   				    
105   		    }
106   		}
107   	  }
108   	  bfs();
109   	  int ans = d[tz][tx][ty];
110   	  if (ans==-1)
111   	  {
112   		printf("Trapped!\n");
113   	  }
114   	  else
115   	  {
116   	//	if (ans==1)
117   	//	printf("Escaped in 1 minute.\n");
118   	//	else printf("Escaped in %d minutes.\n",ans);
119   		printf("Escaped in %d minute(s).\n",ans);
120   	  }
121   
122       }
123   }
124