POJ1383 Labyrinth(树的直径：两次BFS)

题意：

给一个迷宫，要求迷宫中最长的路径（就是两点之间的距离最大）

要点：

树的直径问题，有两种方法：第一种就是两次BFS：先以任意点搜索一次找到最长段的一端v，再以v搜索找到最长段的另一端w，第二次搜索出的就是最长路径。第二种就是DP，用记忆化搜索应该可以写，以后再说。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
char map[1005][1005];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int d[1005][1005];
int col, row,fx,fy;int bfs(int x,int y)
{int ans = 0;memset(d, -1, sizeof(d));queue<int> que;que.push(x);que.push(y);d[x][y] = 0;while (!que.empty()){x = que.front(); que.pop();y = que.front(); que.pop();for (int i = 0; i < 4; i++){int xx = x + dx[i];int yy = y + dy[i];if (d[xx][yy]==-1 && map[xx][yy]=='.' && xx >= 1 && xx <= row&&yy >= 1 && yy <= col){que.push(xx);que.push(yy);d[xx][yy] = d[x][y] + 1;if (ans < d[xx][yy])//记录最长的位置{ans = d[xx][yy];fx = xx;fy = yy;}}}}return ans;
}int main()
{int t,i,j;scanf("%d", &t);while (t--){scanf("%d%d", &col, &row);for (i = 1; i <= row; i++)scanf("%s", map[i] + 1);for (i = 1; i <= row; i++)for (j = 1; j <= col; j++)if (map[i][j] == '.'){fx = i;fy = j;break;}int ans;bfs(fx, fy);		//先以任意点搜索一次找到最长段的一端vans = bfs(fx, fy);	//再以v搜索找到最长段的另一端wprintf("Maximum rope length is %d.\n", ans);}return 0;
}