HOJ 1030 Labyrinth----------------兩次BFS求樹的直徑

[cpp]   //題意：求樹的直徑   //思路：   //   樹的直徑是指樹的最長簡單路。求法: 兩遍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 1010   struct 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;   }//同BFS1   int 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++)               {  www.2cto.com                 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;   }