题目链接：?space=1&num=1145
1145. Rope in the Labyrinth
Time limit: 0.5 secondMemory limit: 64 MB
A labyrinth with rectangular form and sizem×nis divided into square cells with sides’ length 1 by lines that are parallel with the labyrinth’s sides. Each cell of the grid is either occupied or free. It is possible to move from one free cell to another free cells that share a common side with the cell. One cannot move beyond the labyrinth’s borders. The labyrinth is designed pretty specially: for any two cells there is only one way to move from one cell to the other. There is a hook at each cell’s center. In the labyrinth there are two special free cells, such that if you can connect the hooks of those two cells with a rope, the labyrinth’s secret door will be automatically opened. The problem is to prepare a shortest rope that can guarantee, you always can connect the hooks of those two cells with the prepared rope regardless their position in the labyrinth.
Input
The first line contains integersnandm(3 ≤n,m≤ 820). The next lines describe the labyrinth. Each of the nextmlines containsncharacters. Each character is either "#" or ".", with "#" indicating an occupied cell, and "." indicating a free cell.
Output
Print out in the single line the length (measured in the number of cells) of the required rope.
Sample
inputoutput
7 6########.#.####.#.####.#.#.##…..########8
PS:
连续两次BFS求最长路径！
代码如下：
#include <cstdio>#include <cstring>#include <queue>#include <iostream>#include <algorithm>using namespace std;int xx[4] = {0,0,1,-1};int yy[4] = {1,-1,0,0};char mp[1047][1047];int n, m;int vis[1047][1047];struct node{int x, y;int step;};int judge(int x, int y){if(x>=0 && x<n && y>=0 && y<m && mp[x][y]=='.' && !vis[x][y])return 1;return 0;}node BFS(int x, int y){memset(vis,0,sizeof(vis));queue<node> q;while(!q.empty()){q.pop();}node rear, front, p;front.x = x, front.y = y;front.step = 0;p.x = x, p.y = y;p.step = 0;q.push(front);vis[x][y] = 1;while(!q.empty()){front = q.front();q.pop();if(front.step > p.step){p = front;}for(int i = 0; i < 4; i++){int dx = front.x+xx[i];int dy = front.y+yy[i];if(judge(dx,dy)){vis[dx][dy] = 1;rear.x = dx,rear.y = dy;rear.step = front.step+1;q.push(rear);}}}return p;}int main(){while(~scanf("%d%d",&m,&n)){getchar();for(int i = 0; i < n; i++){gets(mp[i]);}int flag = 0;int x = 0, y = 0;for(int i = 0; i < n; i++)//随机寻找一个'.'{for(int j = 0; j < m; j++){if(mp[i][j] == '.'){x = i;y = j;flag = 1;break;}}if(flag)break;}node tt = BFS(x, y);node ans = BFS(tt.x, tt.y);printf("%d\n",ans.step);}return 0;}
，人生的路无需苛求。只要你迈步，路就在你的脚下延伸。
