首页 > ACM题库 > HDU-杭电 > hdu 2170 Frogger-最短路径-[解题报告]C++
2013
12-30

hdu 2170 Frogger-最短路径-[解题报告]C++

Frogger

问题描述 :

Philip J. Frog just wanted to go for a mid-afternoon swim, but in typical frog fashion he’s ended up in the middle of a busy street. Help Phil figure out how long he’ll be hopping on hot asphalt before he finds his way to the nice cool water.

Phil may hop one square horizontally or vertically per second. He may only hop onto road, grass, or water. Additionally, he cannot occupy any square occupied by a car. Phil and the cars move at the same time, meaning Phil can “hop over” an oncoming car. Phil can also remain in the same square if he wishes. All horizontal movement wraps (e.g., a rightward hop from the rightmost column places Phil in the leftmost column). Cars move horizontally in the direction indicated on the map (‘<’ means leftward, ‘>’ means rightward) at a rate of one square per second and never collide with anything.

输入:

Input begins with a single integer specifying the number of test maps. Each map begins with two integers R and C (0 < R, C <= 30) specifying the number of rows and columns, respectively, followed by R lines each C characters long, specifying the map. The possible map characters are:

Phil (‘&’) – Phil’s starting location. Each map contains exactly one. Always indicates road underneath.
Tree (‘T’) – Impassable.
Grass (‘.’) – Phil can move freely in the grass.
Road (‘-’) – Hot!
Car (‘<’, ‘>’) – Always indicates road underneath.
Water (‘~’) – Phil’s goal.

输出:

Input begins with a single integer specifying the number of test maps. Each map begins with two integers R and C (0 < R, C <= 30) specifying the number of rows and columns, respectively, followed by R lines each C characters long, specifying the map. The possible map characters are:

Phil (‘&’) – Phil’s starting location. Each map contains exactly one. Always indicates road underneath.
Tree (‘T’) – Impassable.
Grass (‘.’) – Phil can move freely in the grass.
Road (‘-’) – Hot!
Car (‘<’, ‘>’) – Always indicates road underneath.
Water (‘~’) – Phil’s goal.

样例输入:

3
2 1
~
&
4 7
~TTTTTT
.------
-->-<--
---&---
3 5
~~~~~
..T..
>>&<<

样例输出:

1
6
Impassable

 

转载请注明出处:優YoU 

http://user.qzone.qq.com/289065406/blog/1299339470

 

提示:唉。。不说了,又是Floyd…注意精度就是了

 

题目大意:

给出两只青蛙的坐标A、B,和其他的n-2个坐标,任一两个坐标点间都是双向连通的。显然从A到B存在至少一条的通路,每一条通路的元素都是这条通路中前后两个点的距离,这些距离中又有一个最大距离。

现在要求求出所有通路的最大距离,并把这些最大距离作比较,把最小的一个最大距离作为青蛙的最小跳远距离。

 

Floyd算法

用Floyd算法求出两两最短路,再求出从每个点开始的最长路,最后从这n个最长路中求出最小的那个即为所求。

 

 

//Memory Time 
//584K   63MS 

#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;

class coordinate
{
public:
	double x,y;
}point[201];

double path[201][201];   //两点间的权值

int main(void)
{
	int i,j,k;

	int cases=1;
	while(cases)
	{
		/*Read in*/

		int n;   //numbers of stones;
		cin>>n;
		if(!n)break;

		for(i=1;i<=n;i++)
			cin>>point[i].x>>point[i].y;

		/*Compute the weights of any two points*/

		for(i=1;i<=n-1;i++)
			for(j=i+1;j<=n;j++)
			{
				double x2=point[i].x-point[j].x;
				double y2=point[i].y-point[j].y;
				path[i][j]=path[j][i]=sqrt(x2*x2+y2*y2);  //双向性
			}

		/*Floyd Algorithm*/

		for(k=1;k<=n;k++)    //k点是第3点
			for(i=1;i<=n-1;i++)    //主要针对由i到j的松弛,最终任意两点间的权值都会被分别松弛为最大跳的最小(但每个两点的最小不一定相同)
				for(j=i+1;j<=n;j++)
					if(path[i][k]<path[i][j] && path[k][j]<path[i][j])    //当边ik,kj的权值都小于ij时,则走i->k->j路线,否则走i->j路线
						if(path[i][k]<path[k][j])               //当走i->k->j路线时,选择max{ik,kj},只有选择最大跳才能保证连通
							path[i][j]=path[j][i]=path[k][j];
						else
							path[i][j]=path[j][i]=path[i][k];

		cout<<"Scenario #"<<cases++<<endl;
		cout<<fixed<<setprecision(3)<<"Frog Distance = "<<path[1][2]<<endl;
		//fixed用固定的小数点位数来显示浮点数(包括小数位全为0)
		//setprecision(3)设置小数位数为3
		cout<<endl;
	}
	return 0;
}

 

解题转自:http://blog.csdn.net/lyy289065406/article/details/6645854


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }