Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

麻烦帮我看下为什么BFS也TLE了,先谢了

Posted by ye11ow_ca at 2010-09-26 22:05:30 on Problem 2251
#include<stdio.h>
#include<queue>
using namespace std;
struct node
{
   int xx,yy,zz;       
};
int dir[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
int main()
{
   int x,y,z;
   while(scanf("%d%d%d%*c",&x,&y,&z)&&(x||y||z))
   {
      int i,j,k;
      char map[34][34][34];
      node start;
      for(i=0;i<=x+1;++i)
         for(j=0;j<=y+1;++j)
            for(k=0;k<=z+1;++k)
               map[i][j][k]='#';
      for(i=1;i<=x;++i)
      {
         for(j=1;j<=y;++j)
         {
            for(k=1;k<=z;++k)
            {
               scanf("%c",&map[i][j][k]);
               if(map[i][j][k]=='S') start.xx=i,start.yy=j,start.zz=k;
            }
            getchar(); 
         }  
         getchar();
      }
      int kk=1,tt=0,level=0;
      bool sign=false;
      queue<node>  bfs;
      bfs.push(start);
      while(!bfs.empty())
      {
         while(kk--)
         {
            node tmp;
            tmp.xx=(bfs.front()).xx;
            tmp.yy=(bfs.front()).yy;
            tmp.zz=(bfs.front()).zz;
            bfs.pop();
            if(map[tmp.xx][tmp.yy][tmp.zz]=='E')  {sign=true;break;}
            map[tmp.xx][tmp.yy][tmp.zz]='#';
            for(i=0;i<6;++i)
            {
               node tmp2;
               tmp2.xx=tmp.xx+dir[i][0];
               tmp2.yy=tmp.yy+dir[i][1];
               tmp2.zz=tmp.zz+dir[i][2];
               if(tmp2.xx<=0||tmp2.xx>x)  continue;
               if(tmp2.yy<=0||tmp2.yy>y)  continue;
               if(tmp2.zz<=0||tmp2.zz>z)  continue;
               if(map[tmp2.xx][tmp2.yy][tmp2.zz]!='#')  tt++,bfs.push(tmp2);                
            } 
         } 
         if(sign)  break;
         kk=tt;
         tt=0;
         level++; 
      }  
      if(sign)  printf("Escaped in %d minute(s).\n",level);
      else  printf("Trapped!\n");
   }    
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator