2013
12-30

# 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

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

Floyd算法

//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)
{

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;
}

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;
}