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,为啥会T

Posted by shaochang123 at 2024-11-08 22:58:56 on Problem 2251
#include<iostream>
#include<queue>
#include<stdio.h>
using namespace std;
char g[35][35][35];
int vis1[35][35][35],vis2[35][35][35];
int l,n,m,dir[6][3]={
  1,0,0,
  -1,0,0,
  0,1,0,
  0,-1,0,
  0,0,1,
  0,0,-1,
};
struct place{
  int x,y,z,st;
  place(int xx,int yy,int zz,int ss){
    x=xx;
    y=yy;
    z=zz;
    st=ss;
  }
};
bool check1(place cur){
  if(g[cur.x][cur.y][cur.z]=='#'||cur.x==0||cur.x==n+1||cur.y==0||cur.z==0||cur.y==m+1||cur.z==l+1||g[cur.x][cur.y][cur.z]=='1')return false;
  return true;
}
bool check2(place cur){
  if(g[cur.x][cur.y][cur.z]=='#'||cur.x==0||cur.x==n+1||cur.y==0||cur.z==0||cur.y==m+1||cur.z==l+1||g[cur.x][cur.y][cur.z]=='2')return false;
  return true;
}
int main(){
  while(true){
    int f=0;
    scanf("%d%d%d",&l,&n,&m);
    if(l==0&&n==0&&m==0)break;
    queue<place>q,q1;
    for(int i=1;i<=l;i++){
      for(int j=1;j<=n;j++){
        for(int k=1;k<=m;k++){
          vis1[j][k][i]=0;
          vis2[j][k][i]=0;
          char ch=getchar();
          while(ch==' '||ch=='\n')ch=getchar();
          g[j][k][i]=ch;
          if(g[j][k][i]=='S'){
            place s(j,k,i,0);
            q.push(s);
          }
          if(g[j][k][i]=='E'){
            place s(j,k,i,0);
            q1.push(s);
          }
        }
      }
    }
    while(!q.empty()&&!q1.empty()){
      if(q.size()<=q1.size()){
        place cur=q.front();
        int st=cur.st;
        q.pop();
        if(g[cur.x][cur.y][cur.z]=='E'||vis2[cur.x][cur.y][cur.z]){
          st+=vis2[cur.x][cur.y][cur.z];
          printf("Escaped in %d minute(s).",st);
          f=1;
          break;
        }
        g[cur.x][cur.y][cur.z]='1';
        vis1[cur.x][cur.y][cur.z]=st;
        for(int i=0;i<6;i++){
          place now(cur.x+dir[i][0],cur.y+dir[i][1],cur.z+dir[i][2],st+1);
          if(check1(now))q.push(now);
        }
      }
      else{
        place cur=q1.front();
        int st=cur.st;
        q1.pop();
        if(g[cur.x][cur.y][cur.z]=='S'||vis1[cur.x][cur.y][cur.z]){
          st+=vis1[cur.x][cur.y][cur.z];
          printf("Escaped in %d minute(s).",st);
          f=1;
          break;
        }
        g[cur.x][cur.y][cur.z]='2';
        vis2[cur.x][cur.y][cur.z]=st;
        for(int i=0;i<6;i++){
          place now(cur.x+dir[i][0],cur.y+dir[i][1],cur.z+dir[i][2],st+1);
          if(check2(now))q1.push(now);
        }
      }
    }
    if(f==0)printf("Trapped");
  }
  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