poj 1383 Labyrinth (树的直径裸题)

  1#include <cstdio>
  2#include <cstring>
  3#include <iostream>
  4#include <algorithm>
  5#include <vector>
  6#include <queue>
  7#include <set>
  8#include <map>
  9#include <string>
 10#include <cmath>
 11#include <cstdlib>
 12#include <ctime>
 13#define fst first
 14#define sec second
 15#define lson l,m,rt<<1
 16#define rson m+1,r,rt<<1|1
 17#define ms(a,x) memset(a,x,sizeof(a))
 18typedef long long LL;
 19#define pi pair < int ,int >
 20#define MP make_pair
 21using namespace std;
 22const double eps = 1E-8;
 23const int dx4[4]={1,0,0,-1};
 24const int dy4[4]={0,-1,1,0};
 25const int inf = 0x3f3f3f3f;
 26const int N=1E3+7;
 27char maze[N][N];
 28bool vis[N][N];
 29int ans;
 30int n,m;
 31struct Point
 32{
 33    int x,y;
 34    int d;
 35    bool ok ()
 36    {
 37	if (x<0||y<0||x>=n||y>=m) return false;
 38	if (maze[x][y]=='#') return false;
 39	if (vis[x][y]) return false;
 40	return true;
 41    }
 42    void out()
 43    {
 44	cout<<"x:"<<x<<" y:"<<y<<endl;
 45    }
 46}S,lst;
 47void bfs(Point S)
 48{
 49    queue<Point>q;
 50    S.d = 0;
 51    q.push(S);
 52    ms(vis,false);
 53    vis[S.x][S.y] = true;
 54    while (!q.empty())
 55    {
 56	Point cur = q.front();
 57	q.pop();
 58	for ( int i = 0 ; i < 4 ; i++)
 59	{
 60	    Point nxt;
 61	    nxt.x = cur.x + dx4[i];
 62	    nxt.y = cur.y + dy4[i];
 63	    nxt.d = cur.d + 1;
 64	    if (!nxt.ok()) continue;
 65	    q.push(nxt);
 66	    vis[nxt.x][nxt.y] = true;
 67	    if (ans<nxt.d)
 68	    {
 69		ans = nxt. d;
 70		lst = nxt;
 71	    }
 72	}
 73//	cout<<"ans:"<<ans<<endl;
 74    }
 75}
 76int main()
 77{
 78	#ifndef  ONLINE_JUDGE 
 79	freopen("code/in.txt","r",stdin);
 80  #endif
 81	int T;
 82	cin>>T;
 83	while(T--)
 84	{
 85	    ms(vis,false);
 86	    scanf("%d%d",&m,&n);
 87	    for ( int i =  0; i  < n ; i++) scanf("%s",maze[i]);
 88	    for ( int i = 0 ; i < n ; i++)
 89		for ( int j = 0 ; j < m ; j++)
 90		    if (maze[i][j]=='.')
 91		    {
 92			S.x = i ;
 93			S.y = j ;
 94		    }
 95	    ans  = 0;
 96	    bfs(S);
 97	    ans = 0 ;
 98	    bfs(lst);
 99	    printf("Maximum rope length is %d.\n",ans);
100	}
101  #ifndef ONLINE_JUDGE  
102  fclose(stdin);
103  #endif
104    return 0;
105}