Hoj 1030 Labyrinth
要求在图中找出距离最远的两个点的距离。这题暴力枚举每一点出发的最长路径显然不可行。
从任意点A出发的最长路径的另一个端点称为B，那么B就是全局最长路径的一个端点。那么，从B点开始一次广搜，到达的最远点叫C。BC即是图中的最长路径。
[cpp]
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <stack>
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<Point> 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<row && tempy>=0 && tempy<column)
{
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<row; i++)
{
for(int j=0; j<column; j++)
{
scanf(" %c ",&c);
if(c == '.')
{
map[i][j] = 1;
}
}
}
for(int i=0; i<row; i++)
{
int flag = 0;
for(int j=0; j<column; 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<row; i++)
{ www.zzzyk.com
for(int j=0; j<column; j++)
{
if(map[i][j] == 2)
{
map[i][j] = 1;
} &n
补充：软件开发 , C++ ,
- 更多C/C++疑问解答：
- 关于c++的cout输出的问题。
- 在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
- c++数据结构内部排序问题，整数排序
- 2012九月计算机二级C语言全国题库，，急求急求
- 如果assert只有一个字符串作为参数，是什么意思呢?
- C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
- 为什么用结构体编写的程序输入是，0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
- 为什么这个程序求不出公式？
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊