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; }