POJ 1383 Labyrinth

問題

hxwマスの迷路が与えられる。
'#'のマスは壁で入ることができず、'.'のマスは立ち入ることのできるマスである。
任意の二つの'.'のマスは、それをつなぐパスがただ一つ存在する。


最も離れたマスとマスの距離を求めよ。

制約条件

h,w≦1000

方針

迷路のグラフは木である。
木において、最も離れた頂点対をひとつ求めるには、
ある頂点から出発して、最も遠い頂点をひとつ求め、
その頂点から再度出発して、最も遠い頂点を求めればいい。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
char in[1000][1001];
int h,w;
bool v[1000][1001];
int farx,fary,dist;
void rec(int y,int x,int d){
	v[y][x]=1;
	if(d>dist){
		dist=d; farx=x; fary=y;
	}
	rep(dir,4){
		int ny=y+dy[dir], nx=x+dx[dir];
		if(in[ny][nx]=='.'&&!v[ny][nx])rec(ny,nx,d+1);
	}
}

int main()
{
	int T; scanf("%d",&T);
	while(T--){
		scanf("%d%d ",&w,&h);
		rep(i,h)gets(in[i]);
		int y,x;
		rep(i,h)rep(j,w)if(in[i][j]!='#')y=i, x=j;
		
		dist=0;
		rep(i,h)rep(j,w)v[i][j]=0;
		rec(y,x,0);
		rep(i,h)rep(j,w)v[i][j]=0;
		dist=0;
		rec(fary,farx,0);
		printf("Maximum rope length is %d.\n",dist);
	}
	return 0;
}