PKU 1383-Labyrinth

問題概要

マス目上に木となっている地図が与えられる。最大の距離となる2点の距離を求めよ。

解法

木の2点間最長距離を求めるには、任意の頂点から探索を行ない一番遠かった点から再度探索を行なう。
これをBFSで実装した。

実装(C++)

#include <cstdio>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
typedef pair<int,int> P;
queue<P> que;
int H,W;
int T;
char in[1001];
char MAP[1001][1001];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int sx,sy;
int cost[1001][1001];
int calc(int &sx,int &sy){
  memset(cost,0x3F,sizeof(cost));
  cost[sx][sy]=0;
  que.push(P(sx,sy));
  while(!que.empty()){
    P now=que.front();que.pop();
    sx=now.first;sy=now.second;
    int time=cost[sx][sy];
    for(int i=0;i<4;i++){
      int nx=sx+dx[i],ny=sy+dy[i];
      if(MAP[nx][ny]=='.'){
        if(cost[nx][ny]>time+1){
          cost[nx][ny]=time+1;
          que.push(P(nx,ny));
        } 
      }
    }
  }
  return cost[sx][sy];
}
int main(){
  scanf("%d",&T);
  for(;T--;){
    scanf("%d%d",&W,&H);
    for(int y=0;y<H;y++){
      scanf("%s",in);
      for(int x=0;x<W;x++){
        MAP[x][y]=in[x];
      }
    }
    for(int y=1;y<H-1;y++){
      for(int x=1;x<W-1;x++){
        if(MAP[x][y]=='.'){
          int cnt=0;
          for(int k=0;k<4;k++){
            if(MAP[x+dx[k]][y+dy[k]]=='.')cnt++;
          }
          if(cnt<=1){
            sx=x;sy=y;
            x=W;
            y=H;
            break;
          }
        }
      }
    }
    calc(sx,sy);
    printf("Maximum rope length is %d.\n",calc(sx,sy));
  }   
}