534 - Frogger
Moderator: Board moderators
-
- New poster
- Posts: 28
- Joined: Mon Mar 01, 2004 11:29 pm
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.
-
- New poster
- Posts: 28
- Joined: Mon Mar 01, 2004 11:29 pm
Thanks Ryan,
I got AC... min and max!!!![:)](./images/smilies/icon_smile.gif)
I used flody changed to minimax![:)](./images/smilies/icon_smile.gif)
http://www.comp.nus.edu.sg/~stevenha/pr ... raph6.html
Wanderley
I got AC... min and max!!!
![:)](./images/smilies/icon_smile.gif)
I used flody changed to minimax
![:)](./images/smilies/icon_smile.gif)
http://www.comp.nus.edu.sg/~stevenha/pr ... raph6.html
Wanderley
-
- 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]
please help me
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]
please help me
-
- Experienced poster
- Posts: 106
- Joined: Thu Jan 29, 2004 12:07 pm
- Location: Bangladesh
- Contact:
-
- New poster
- Posts: 2
- Joined: Fri Jan 14, 2005 9:43 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:
Output:
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.
![:D](./images/smilies/icon_biggrin.gif)
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!
![:wink:](./images/smilies/icon_wink.gif)
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
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
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.
![:-?](./images/smilies/icon_confused.gif)
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[1000];
} 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[1].tav));
}
return 0;
}
![:-?](./images/smilies/icon_confused.gif)
![:-?](./images/smilies/icon_confused.gif)
![:-?](./images/smilies/icon_confused.gif)
![:-?](./images/smilies/icon_confused.gif)
![:-?](./images/smilies/icon_confused.gif)
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[200][200] = { 0 };
int stones[200][2];
long long calc_dist( int i, int j ) {
long long x = stones[i][0] - stones[j][0];
long long y = stones[i][1] - stones[j][1];
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 )
if( adj[i][k] != 0 && adj[k][j] != 0 ) {
adj[i][j] <?= max( adj[i][k], adj[k][j] );
adj[i][j] = adj[j][i] = min( adj[i][j], adj[j][i] );
}
for( int i = 0; i < N; ++i )
for( int j = 0; j < N; ++j )
if( adj[i][j] != 0 )
ret >?= adj[i][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][0], &stones[i][1] );
for( int i = 0; i < N-1; ++i )
for( int j = i+1; j < N; ++j ) {
adj[i][j] = adj[j][i] = calc_dist( i, j );
res >?= adj[i][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;
}
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