UVa : 534 (Frogger)


Link: http://uva.onlinejudge.org/external/5/534.html

Tricky Lines:

a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence

The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

Put a blank line after each test case, even after the last one.

Analysis:

Suppose, Source = A
Destination = Z
there are 3 paths to reach from A to Z
path 1 : A → B → C → Z
path 2 : A → E → Z
path 3 : A → Z
distances are follows,
A → B = 5
B → C = 5
C → Z = 5

A → E = 6
E → Z = 8

A → Z = 20

distance wise,
path 1 : 5 → 5 → 5
path 2 : 6 → 8
path 3 : 20

which path should u take ? 1, 2 or 3 ?
minimum distance = 6 + 8 = 14 → path 2

U r asked to find shortest jump distance
that is, if u take path : 2 then minimum jump distance is 6
if u take path : 1 then minimum jump distance is 5
though path 1 is not the shortest distance to reach from A to Z but it contains minimum jump distance

Use any shortest distance algorithm and modify it according to minimax distance

I have used floyd warshall. Count all the distances between the stones and store it in array D

then run floyd warshall and update the distance as follows,
d [i] [j] = min (d [i] [j], max (d [i] [k], d [k] [j]));

Runtime: 0.064s

Critical input : 
5
0 0
0 9
5 5
6 6
7 7

5
0 0
0 2
9 9
100 2
2 100

7
0 0
0 20
0 5
0 10
0 15
0 6
1 6

0

Critical output :
Scenario #1
Frog Distance = 7.071

Scenario #2
Frog Distance = 2.000

Scenario #3
Frog Distance = 5.000
< --- blank line --- >
// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

double power (int b, int p)
{
    double ret = 1;

    for ( int i = 1; i <= p; i++ )
        ret *= b;

    return ret;
}

int main ()
{
    int stones;
    int cases = 0;

    while ( scanf ("%d", &stones) && stones ) {
        int x [200 + 10];
        int y [200 + 10];

        for ( int i = 0; i < stones; i++ ) scanf ("%d %d", &x [i], &y [i]);

        double d [200 + 10] [200 + 10];

        for ( int i = 0; i < stones; i++ ) {
            for ( int j = i + 1; j < stones; j++ )
                d [i] [j] = d [j] [i] = sqrt (power (x [i] - x [j], 2) + power (y [i] - y [j], 2));
        }

        for ( int k = 0; k < stones; k++ ) {
            for ( int i = 0; i < stones; i++ ) {
                for ( int j = 0; j < stones; j++ )
                    d [i] [j] = min (d [i] [j], max (d [i] [k], d [k] [j]));
            }
        }

        printf ("Scenario #%d\n", ++cases);
        printf ("Frog Distance = %.3lf\n\n", d [0] [1]);

    }

	return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s