题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1145
| input | output |
|---|---|
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;
}
URAL 1145. Rope in the Labyrinth（两次BFS啊 ）
原文：http://blog.csdn.net/u012860063/article/details/43645415