题意：

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

要点：

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

15566071

Accepted

5128K

719MS

1157B

2016-05-29 09:33:38

#include
    
     #include
     
      #include
      
       #include
       
        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
        
          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);		//先以任意点搜索一次找到最长段的一端v		ans = bfs(fx, fy);	//再以v搜索找到最长段的另一端w		printf("Maximum rope length is %d.\n", ans);	}	return 0;}