这题暴力枚举每一点出发的最长路径显然不可行。
从任意点A出发的最长路径的另一个端点称为B，那么B就是全局最长路径的一个端点。那么，从B点开始一次广搜，到达的最远点叫C。BC即是图中的最长路径。
[cpp]
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int column,row;
int map[1002][1002];
int dis[1002][1002];
int disx[4] = {0,1,0,-1};
int disy[4] = {1,0,-1,0};
int maxX;
int maxY;
struct Point
{
int x;
int y;
};
int bfs(int startx,int starty)
{
queue p;
Point nex,temp;
maxX = startx;
maxY = starty;
int maxP = 0;
nex.x = startx;
nex.y = starty;
p.push(nex);
while(!p.empty())
{
temp = p.front();
p.pop();
for(int i=0; i<4; i++)
{
int tempx = temp.x + disx[i];
int tempy = temp.y + disy[i];
if(tempx>=0 && tempx=0 && tempy
{
if(map[tempx][tempy] == 1)
{
map[tempx][tempy] = 2;
dis[tempx][tempy] += dis[temp.x][temp.y] + 1;
nex.x = tempx;
nex.y = tempy;
p.push(nex);
if(dis[tempx][tempy]>maxP)
{
maxP = dis[tempx][tempy];
maxX = tempx;
maxY = tempy;
}
}
}
}
}
return maxP;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int t;
char c;
scanf(" %d ",&t);
int startx,starty;
while(t--)
{
memset(map,0,sizeof(map));
memset(dis,0,sizeof(dis));
scanf(" %d %d ",&column,&row);
for(int i=0; i
{
for(int j=0; j
{
scanf(" %c ",&c);
if(c == '.')
{
map[i][j] = 1;
}
}
}
for(int i=0; i
{
int flag = 0;
for(int j=0; j
{
if(map[i][j] == 1)
{
flag = 1;
startx = i;
starty = j;
break;
}
}
if(flag == 1)
{
break;
}
}
map[startx][starty] = 2;//标记为已访问过
bfs(startx,starty);
//还原原map
for(int i=0; i
{ www.2cto.com
for(int j=0; j
{
if(map[i][j] == 2)
{
map[i][j] = 1;
}
}
}
memset(dis,0,sizeof(dis));
printf("Maximum rope length is %d.\n",bfs(maxX,maxY));
}
return 0;
}