HOJ 1030 Labyrinth----------------两次BFS求树的直径
Labyrinth
//题意：求树的直径//思路：// 树的直径是指树的最长简单路。求法: 两遍BFS :先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径；// 原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点// 证明: 1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾)// 2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了// 所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度//hint:。。。。。 #include<iostream>#include<cstring>#include<cstdio>#include<queue>#define maxlen 1010struct node{ int x,y,step;};char mat[maxlen][maxlen];int mat2[maxlen][maxlen],maxt;int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};using namespace std;node BFS1(node s,int a,int b)//任意一个点找到直径的另一点（以这个点为起点的最长路的终点）{ queue<node> q; node ol,ne,ans; while(!q.empty()) q.pop(); maxt=-1;//当前最大步子记录 s.step=0; mat[s.x][s.y]='#'; q.push(s); while(!q.empty()) { ol=q.front(); q.pop(); if(ol.step>maxt) { maxt=ol.step; ans=ol; }//出队就要判断 for(int l=0; l<4; l++) { ne.x=ol.x+dir[l][0]; ne.y=ol.y+dir[l][1]; ne.step=ol.step; if(ne.x>a||ne.y>b||ne.x<0||ne.y<0||mat[ne.x][ne.y]=='#')continue; else { mat[ne.x][ne.y]='#'; ne.step++; if(ne.step>maxt) { maxt=ne.step; ans=ne; }//更新之后要判断 q.push(ne); } } } return ans;}node BFS2(node s,int a,int b){ queue<node> q; node ol,ne,ans; while(!q.empty()) q.pop(); maxt=-1; s.step=0; mat2[s.x][s.y]=1; q.push(s); while(!q.empty()) { ol=q.front(); q.pop(); if(ol.step>maxt) { maxt=ol.step; ans=ol; } for(int l=0; l<4; l++) { ne.x=ol.x+dir[l][0]; ne.y=ol.y+dir[l][1]; ne.step=ol.step; if(ne.x>a||ne.y>b||ne.x<0||ne.y<0||mat2[ne.x][ne.y]==1)continue; else { mat2[ne.x][ne.y]=1; ne.step++; if(ne.step>maxt) { maxt=ne.step; ans=ne; } q.push(ne); } } } return ans;}//同BFS1int main(){ int n,a,b,i,j; node s; cin >> n; while(n--) { memset(mat,'0',sizeof(mat)); memset(mat2,0,sizeof(mat2)); cin >> b >> a; for(i=0;i<a;i++) for(j=0;j<b;j++) cin >> mat[i][j]; for(i=0; i<a; i++) for(j=0; j<b; j++) if(mat[i][j]=='#') mat2[i][j]=1; bool f=false; for(i=0; i<a; i++) { for(j=0; j<b; j++) { if(mat[i][j]=='.') { s.x=i; s.y=j; s.step=0; f=true;//用来跳出两层循环 break; } } if(f) break; } printf("Maximum rope length is %d.\n", BFS2(BFS1(s,a,b),a,b).step); } return 0;}