PKU 1383 Labyrinth
http://poj.org/problem?id=1383
ある地点とある地点を結ぶ経路が必ず一つだけあるような迷路が入力される。
この中で最も遠い地点同士の長さを求めろというような問題。
BFS*2な問題。
char in[1000][2000]; bool vis[1000][1000]; main(){ int T; scanf("%d",&T); while(T--){ int r,c; scanf("%d%d",&c,&r); rep(i,r)scanf(" %s ",in[i]); rep(i,r){ rep(j,c){ if(in[i][j]=='#')continue; queue<PI>q; memset(vis,0,sizeof(vis)); q.push(mp(i,j)); int lx,ly; while(!q.empty()){ int cx=q.front().F,cy=q.front().S; q.pop(); if(vis[cx][cy])continue; vis[cx][cy]=true; lx=cx; ly=cy; rep(i,4){ int nx=cx+dx[i],ny=cy+dy[i]; if(nx<0 || r<=nx || ny<0 || c<=ny || vis[nx][ny] || in[nx][ny]=='#')continue; q.push(mp(nx,ny)); } } queue<pair<int,PI> >qq; memset(vis,0,sizeof(vis)); qq.push(mp(0,mp(lx,ly))); int ans=0; while(!qq.empty()){ int cx=qq.front().S.F,cy=qq.front().S.S; int cc=qq.front().F; qq.pop(); if(vis[cx][cy])continue; vis[cx][cy]=true; ans=cc; rep(i,4){ int nx=cx+dx[i],ny=cy+dy[i]; if(nx<0 || r<=nx || ny<0 || c<=ny || vis[nx][ny] || in[nx][ny]=='#')continue; qq.push(mp(cc+1,mp(nx,ny))); } } printf("Maximum rope length is %d.\n",ans); goto END; } } END:; } }