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

怎么在杭电能过 北大就过不了啊

Posted by jincp at 2010-12-22 17:23:42 on Problem 2225
#include <stdio.h>
#include <queue>
using namespace std;

bool flag[15][15][15];
char map[15][15][15];
char ss[10];
int p[6][3]={{-1,0,0},{1,0,0},{0,-1,0,},{0,1,0},{0,0,1},{0,0,-1}};
       
int c;
int n;

struct node
{
       int x;
       int y;
       int z;
       bool operator==(const node & b)
       {
           return (x==b.x&&y==b.x&&z==b.z);
       }
};

queue <node> Q;
bool ok(node q)
{
     if(q.x<0||q.x>=n||q.y<0||q.y>=n||q.z<0||q.z>=n)
           return false;
     else
           return true;
}
int main()
{
    int i,j,k;
    while(scanf("%s",ss)!=EOF)
    {
         scanf("%d",&n);
         node s,e;
         getchar();
         for(i=0;i<n;i++)
         {
              for(j=0;j<n;j++)
              {
                 for(k=0;k<n;k++)
                 {
                     scanf("%c",&map[i][j][k]);
                 }
                 getchar();
              }                        
         }

         scanf("%d%d%d",&s.x,&s.y,&s.z);
         scanf("%d%d%d",&e.x,&e.y,&e.z);
         
         
         memset(flag,0,sizeof(flag));
         //BFS
         //printf("d");
         while(!Q.empty())
         {
            Q.pop();
         }
         
         Q.push(s);
         int t=1,u=1,w,c=0;
         flag[s.z][s.x][s.y]=1;
         
         if(s.x==e.x&&s.y==e.y&&s.z==e.z)
         {
            printf("%d 0\n",n);
            continue;
         }
         
         while(t)
         {
            w=0;
            c++;
            if(u==0){c=0;break;}
            for(i=1;i<=u;i++)
            {
              node m=Q.front();
              node m1;
              Q.pop();
              for(j=0;j<6;j++)
              {              
                  m1.x=m.x+p[j][0];
                  m1.y=m.y+p[j][1];
                  m1.z=m.z+p[j][2];
                  
                  if(ok(m1)&&flag[m1.z][m1.x][m1.y]==0&&map[m1.z][m1.x][m1.y]=='O')
                  {
                       w++;
                       flag[m1.z][m1.x][m1.y]=1;
                       Q.push(m1); 
                       //printf("%c\n",map[m1.x][m1.y][m1.z]);
                       //printf("%d %d %d\n",m1.x,m1.y,m1.z); system("pause");                   
                  }
                  
                  if(m1.x==e.x&&m1.y==e.y&&m1.z==e.z)
                  {
                     t=0;
                     break;             
                  }
               }
               //printf("d");
             }
             u=w; 
            }
            //getchar();
           // scanf("%s",s);
           scanf("%s",ss);
           if(c==0)
           printf("NO ROUTE\n");
           else
           printf("%d %d\n",n,c);
    }
    return 0;
}


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