## 534 - Frogger

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Use a shortest path algorithm..

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm
But the problem don't want the max of minimun?

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
In this problem, you have to find the minimum "jump range" needed by the frog to get from stone #1 to stone #2. Because his goal is to reach the lovely Fiona. So if there are stones kilometers away, it does him no good to reach them if he could just make a short jump to her stone.
I'm always willing to help, if you do the same.

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm
Thanks Ryan,

I got AC... min and max!!! I used flody changed to minimax http://www.comp.nus.edu.sg/~stevenha/pr ... raph6.html

Wanderley

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

### 534 Frogger WA

I think that this is a FW problem
and it is a minimax problem

algorithm

- first initialized the cost matrix INF = 20000000
- then i have created a graph
- then i have used a minimax FW algorithm

some part of my code

initialize
[cpp]
for ( i = 0; i < N; i++ ) {
for ( j = 0; j < N; j++ ) {
cost[j] = -INF;
}
cost = INF;
}
[/cpp]

graph A is a node type array
[cpp]
while ( M-- ) {
scanf("%d %d", &A.x, &A[i++].y);
}
for ( i = 0; i < N; i++ ) {
for ( j = i + 1; j < N; j++ ) {
cost[j] = length(A.x, A.y, A[j].x, A[j].y );
}
}
[/cpp]

minimax FW
[cpp]
for ( k = 0; k < N; k++ ) {
for ( i = 0; i < N; i++ ) {
for ( j = 0; j < N; j++ ) {
cost[j] = cost[j] = mini( cost[j], maxi ( cost[i][k], cost[k][j]));
}
}
}
[/cpp]

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
This part of your code is confusing. Can you explain it ? Why are you doing
[cpp]cost[j] = -INF;[/cpp]
and
[cpp]cost = INF;[/cpp]
in the initialization ?

And also, are you using sqrt() or pow() in your length() function? This can lead to a precision error.

zahid_noname00
New poster
Posts: 2
Joined: Fri Jan 14, 2005 9:43 pm i think u have made the problem more critical than it is

simply initialize the cost matrix like this

//cost[][] is of double type
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cost[j]=sqrt(pow((A.x-A[j].x),2) + pow((A.y-A[j].y),2))

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
I'm pretty sure that
cost[j]=sqrt(pow((A.x-A[j].x),2) + pow((A.y-A[j].y),2))

leads to a "Time Length Exceeded" message.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
You can use
for(i = 0; i < n; ++i)
for(j = i; j < n; ++j)
if(i == j)
cost[j] = 0;
else
cost[j] = cost[j] = length(A.x, A.y, A[j].x, A[j].y );

and the length can be used as:
sqrt((A.x-A[j].x)*(A.x-A[j].x) + (A.y-A[j].y)* (A.y-A[j].y))

rafagiu
New poster
Posts: 12
Joined: Sat Sep 24, 2005 8:30 pm

### 534 Frogger - I/O

Greetings, everyone.

I've seend one or two requests in previous past and I had a bad time with UVA 534 (Frogger) myself. Because of that, I took the liberty to post a few I/O for this problem. May this rest here, peacefully waiting for someone in need. The I/O I present here is not very long. No problem, one of the test cases has 20 stones. That's enough to break your legs if you don't have a nice algorithm, so you'll know your solution will certainly experience Time Limit when UVA attempts to give it an input with ten times more stones! So here they go. I hope you'll find that useful!

Input:

Code: Select all

``````7
1 0
1 3
1 1
0 1
2 2
2 1
2 3

4
0 0
4 0
0 2
3 0

8
0 0
2 3
0 1
3 1
3 0
2 0
3 2
1 1

20
0 0
20 0
19 0
18 0
17 0
16 0
15 0
14 0
13 0
12 0
11 0
10 0
9 0
8 0
7 0
6 0
5 0
4 0
3 0
2 0
1 0

0
``````
Output:

Code: Select all

``````Scenario #1
Frog Distance = 1.000

Scenario #2
Frog Distance = 3.000

Scenario #3
Frog Distance = 1.414

Scenario #4
Frog Distance = 1.000

``````

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am
Floyd warshall is sufficient for the problem Szendwich
New poster
Posts: 1
Joined: Wed Feb 01, 2006 1:53 pm
Hello!
This problem bothers me .... I use Dijkstra algorithm to solve this problem, but the tester always said: WA. Where is the problem? Please help me.

Code: Select all

``````#include <stdio.h>
#include <math.h>
#define VEGTELEN 100000

typedef struct {
int x, y;
double tav;
int kesz;
} pont;

typedef struct {
int n;
pont p;
} graf;

graf G;

double maxd(double A, double B) {
if(A > B)
return A;

return B;
}

double etav(int u, int v) {
return (G.p[u].x - G.p[v].x) * (G.p[u].x - G.p[v].x) + (G.p[u].y - G.p[v].y) * (G.p[u].y - G.p[v].y);
}

void kozelit(int u, int v) {
double du;

if(u == 0)
du = etav(0,v);
else
du = maxd(G.p[u].tav, etav(u,v));

if(du < G.p[v].tav)
G.p[v].tav = du;

return;
}

void dijkstra() {
int mi, i;
double me;

while(1) {
me = VEGTELEN;
mi = -1;

for(i = 0; i < G.n; i++) {
if(G.p[i].tav < me && G.p[i].kesz == 0) {
me = G.p[i].tav;
mi=i;
}
}

if(mi==-1 || mi==1)
break;

G.p[mi].kesz++;
for(i = 0; i < G.n; i++) {
if(G.p[i].kesz == 0)
kozelit(mi,i);
}
}

return;
}

int main(int argc, char *argv[]) {
int tovabb, hip, hop, i, j;

j = 0;

while(1) {
scanf("%i", &tovabb);

if(tovabb == 0)
break;

j++;
G.n = tovabb;

for(i = 0; i < tovabb; i++) {
scanf("%i %i", &hip, &hop);

G.p[i].x    = hip;
G.p[i].y    = hop;
G.p[i].kesz = 0;
G.p[i].tav  = i == 0 ? 0 : VEGTELEN;
}

dijkstra();

printf("\nScenario #%i\n", j);
printf("Frogg distance = %.3lf\n\n", sqrt(G.p.tav));
}

return 0;
}
``````     sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

### 534 Frogger

I'm going crazy with this task. I've implemented the Floyd Warshall minimax algorithm and it still won't work. Maybe I'm just sleepy but could anyone take a look at this code and see if there's a stupid bug somewhere in it.

Code: Select all

``````#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int N, n = 1;
long long adj = { 0 };
int stones;

long long calc_dist( int i, int j ) {
long long x = stones[i] - stones[j];
long long y = stones[i] - stones[j];
return x*x + y*y;
}

int floyd_warshall() {
int ret = 0;
for( int k = 0; k < N; ++k )
for( int j = 0; j < N; ++j )
for( int i = 0; i < N; ++i )
}
for( int i = 0; i < N; ++i )
for( int j = 0; j < N; ++j )
return ret;
}

int main() {
scanf( "%d", &N );

while( N != 0 ) {
int res = 0;

for( int i = 0; i < N; ++i ) for( int j = 0; j < N; ++j ) adj[i][j] = 0;
for( int i = 0; i < N; ++i ) scanf( "%d %d", &stones[i], &stones[i] );
for( int i = 0; i < N-1; ++i )
for( int j = i+1; j < N; ++j )  {
}

printf( "Scenario #%d\n", n );
n++;

int tmp = floyd_warshall();
if( tmp < res && tmp != 0 ) res = tmp;

printf( "Frog Distance = %.3lf\n\n", sqrt( double(res) ) );

scanf( "%d", &N );
}

return 0;
}
``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
You need to find minimax distance between the stones #1 and #2, not between all pairs; e.g. output for the following input is the same as for sample #1.

Code: Select all

``````3
0 0
3 4
1000 1000
``````

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm
Thank you it worked.

Maybe the text should say it more explicitly.