求任意图的最长路。
其实思路很简单,两次bfs即可。
首先在图中任意选择一个点,对它进行bfs扩展,找到距该点最远的点,然后再一次bfs寻找最远点,此时找到的最远距离就是最长路的大小。
Pku 1383 Labyrinth 代码:
#include <iostream>
#include <queue>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dir[4][2] =
{
{0, 1},
{0, -1},
{1, 0},
{-1, 0}};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct point
{
int x;
int y;
int step;
}temp, tt;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n, m;
point q[1500000];
int hash[1002][1002];
char map[1002][1002];
int rear, front;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void bfs(point temp)
{
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(hash, 0, sizeof(hash));
rear = front = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
hash[ temp.x ][ temp.y ] = 0;
q[ rear ++ ] = temp;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(front < rear)
{
temp = q[ front++ ];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < 4; i++)
{
tt.x = temp.x + dir[i][0];
tt.y = temp.y + dir[i][1];
tt.step = temp.step + 1;
if(tt.x < 0 || tt.y < 0 || tt.x >= n || tt.y >= m)
continue;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(map[tt.x][tt.y] == '.' && !hash[ tt.x ][ tt.y ])
{
hash[ tt.x ][ tt.y ] = tt.step;
q[ rear ++ ] = tt;
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int t;
int i, j;
scanf("%d", &t);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(t--)
{
scanf("%d %d", &m, &n);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
scanf("%s", map[i]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int flag = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = 0; j < m; j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(map[i][j] == '.')
{
temp.x = i;
temp.y = j;
temp.step = 0;
flag = 1;
break;
}
}
if(flag)
break;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
bfs(temp);
temp.step = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = 0; j < m; j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(hash[i][j] > temp.step)
{
temp.step = hash[i][j];
temp.x = i;
temp.y = j;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
temp.step = 0;
bfs(temp);
temp.step = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = 0; j < m; j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(hash[i][j] > temp.step)
{
temp.step = hash[i][j];
temp.x = i;
temp.y = j;
}
}
}
printf("Maximum rope length is %d.\n", temp.step);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
}
Zju 3172 Extend 7-day Vacation 代码:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct point
{
int now;
int step;
}temp, tt;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
vector < int > vec[1001];
int hash[1001];
int n, m, x, y;
int i, j;
bool exsit[1001];
queue < point > q;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void bfs(point temp)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
while(!q.empty())
q.pop();
q.push( temp );
hash[ temp.now ] = 0;
memset(hash, -1, sizeof(hash));
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(!q.empty())
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
temp = q.front();
q.pop();
int size = vec[ temp.now ].size();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < size; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(hash[ vec[temp.now][i] ] == -1)
{
tt.now = vec[temp.now][i];
tt.step = temp.step + 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
hash[ vec[temp.now][i] ] = tt.step;
q.push( tt );
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(scanf("%d %d", &n, &m) != EOF)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(exsit, 0, sizeof(exsit));
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i = 0; i < n; i++)
vec[i].clear();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(m --)
{
scanf("%d %d", &x, &y);
vec[x].push_back( y );
vec[y].push_back( x );
exsit[x] = exsit[y] = 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
if(exsit[i] == 1)
break;
}
temp.now = i;
temp.step = 0;
bfs(temp);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(hash[i] > temp.step)
{
temp.step = hash[i];
temp.now = i;
}
}
temp.step = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
bfs(temp);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(hash[i] > temp.step)
{
temp.step = hash[i];
temp.now = i;
}
}
if(temp.step < 7)
printf("Impossible\n");
else
printf("%d\n", temp.step + 1);
}
return 0;
}