534 - Frogger

[Larry]

Use a shortest path algorithm..

[wanderley2k]

But the problem don't want the max of minimun?

[Ryan Pai]

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.

[wanderley2k]

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]

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

[Raiyan Kamal]

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]

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

your FW seems nice

[WR]

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]

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]

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]

Floyd warshall is sufficient for the problem

[Szendwich]

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

[sklitzz]

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

[mf]

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]

Thank you it worked.

Maybe the text should say it more explicitly.