## Thursday, January 1, 2015

### UVa Problem 534 - Frogger

Problem:

Solution:

Thanks competitive programming for teaching me this. The minimax path can be found using Floyd Warshall's algorithm by changing the relaxation from

distance[x, y] = min(distance[x, y], distance[x,k] + distance[k, y])

to

minimax_distance[x, y] = min(minimax_distance[x, y], max(minimax_distance[x, k], minimax_distance[k, y]))

Looks like as long as we can come up with a metric on a particular path that can be computed part by part in an associative manner, then we can use Floyd Warshall to optimize it.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=810

#include "UVa534.h"

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

int UVa534()
{
int test_case = 0;

while (true)
{
test_case++;
int number_of_stones;
cin >> number_of_stones;
if (number_of_stones == 0)
{
break;
}
vector<pair<int, int>> stones;
stones.resize(number_of_stones);
for (int i = 0; i < number_of_stones; i++)
{
int x;
int y;
cin >> x;
cin >> y;
stones[i] = pair<int, int>(x, y);
}

int number_of_nodes = number_of_stones;

vector<vector<double> > minimax_distances;
minimax_distances.resize(number_of_nodes);
for (int src = 0; src < number_of_nodes; src++)
{
minimax_distances[src].resize(number_of_nodes);

for (int dst = 0; dst < number_of_nodes; dst++)
{
int x_diff = stones[src].first - stones[dst].first;
int y_diff = stones[src].second - stones[dst].second;
adjacency_matrix[src][dst] = sqrt(x_diff * x_diff + y_diff * y_diff);
}
}

for (int k = 0; k < number_of_nodes; k++)
{
for (int src = 0; src < number_of_nodes; src++)
{
for (int dst = 0; dst < number_of_nodes; dst++)
{
double current_minimax_distance = minimax_distances[src][dst];
double propose_minimax_distance = max(minimax_distances[src][k], minimax_distances[k][dst]);
if (propose_minimax_distance < current_minimax_distance)
{
minimax_distances[src][dst] = propose_minimax_distance;
}
}
}
}

cout << "Scenario #" << test_case << endl;
cout << "Frog Distance = " << setprecision(3) << fixed << minimax_distances[0][1] << endl;
cout << endl;
}
return 0;
}