PKU 1103 Maze

http://poj.org/problem?id=1103
／と＼で迷路の壁が入力されるので、サイクルが何個あるかと、最大のサイクルの長さを答えろというような問題。

/を
道道壁
道壁道
壁道道

＼を
壁道道
道壁道
道道壁
と置き換えれば、迷路の外に出る経路以外はサイクルになるのでBFSしました。

bool wall[300][300];
int w,h;

void solve(){
  memset(wall,0,sizeof(wall));
  rep(i,h)rep(j,w){
    char c;
    cin>>c;
    if(c=='/')
      wall[i*3+2][j*3]=wall[i*3+1][j*3+1]=wall[i*3][j*3+2]=1;
    else
      wall[i*3][j*3]=wall[i*3+1][j*3+1]=wall[i*3+2][j*3+2]=1;
  }
  int ans=0;
  int cycle=0;
  rep(i,3*h)rep(j,3*w){
    if(wall[i][j])continue;
    int tans=0;
    queue<PI> q;
    q.push(mp(i,j));
    while(!q.empty()){
      int cx=q.front().F;
      int cy=q.front().S;
      q.pop();
      if(wall[cx][cy])continue;
      wall[cx][cy]=true;
      ++tans;
      rep(i,4){
        int nx=cx+dx[i],ny=cy+dy[i];
        if(min(nx,ny)<0 || nx>=3*h || ny>=3*w){
          tans=-10000000;
          continue;
        }
        if(wall[nx][ny])continue;
        q.push(mp(nx,ny));
      }
    }
    ans=max(ans,tans/3);
    if(tans>0)++cycle;
  }
  if(cycle)
    printf("%d Cycles; the longest has length %d.\n",cycle,ans);
  else
    printf("There are no cycles.\n");
  cout<<endl;
}

main(){
  int ma=0;
  while(cin>>w>>h,w){
    printf("Maze #%d:\n",++ma);
    solve();
  }
}