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.zzzyk.com
&n

补充：软件开发 , C++ ,