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

1楼longshengguoji前天 08:15

不错，学习了

Re: creazierHIT昨天 12:48

回复longshengguojin两个BFS其实是写多啦，完全可以在一个函数中！懒得写啦！