## 534 - Frogger

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

### 534 - Frogger

Could anyone help me?
I use to solve this problem following algorith:

2. build full graph - compute connections to all other stones from any.
3. use BFS to find minimal distance which is necessary to reach every stone from all other.
4. output result

What do I miss?
Could anyone send me some special cases?
Is there a problem with rouding errors ?

Best regards
Dominik

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
BFS to find minimal distance?

I don't understand, may be you implement it differently. But a BFS will reach all vertices and stop, right, which you only compute the distance from one stone to all others, but nothing about inter-connection?

Or Am I misunderstanding?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Is there another way of doing this problem by MST, Prims?

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
I just got this AC-ed this morning ... I used Floyd-Warshall for this problem ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I change my implementation to Floyd and got Acc too ....

Thanks all
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
i also used dfs for the first time and got TLE..
then i just changed it to floyd and got ac..
actually the statement of the problem is confusing...
---
anupam
"Everything should be made simple, but not always simpler"

sunkist
New poster
Posts: 5
Joined: Sun Jun 15, 2003 2:11 am
Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long min(long a,long b) {
if (a > b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k))
if (matrix[k] > min(matrix[j],matrix[j][k]))
matrix[k] = min(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist
New poster
Posts: 5
Joined: Sun Jun 15, 2003 2:11 am
Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long min(long a,long b) {
if (a > b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k))
if (matrix[k] > min(matrix[j],matrix[j][k]))
matrix[k] = min(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist
New poster
Posts: 5
Joined: Sun Jun 15, 2003 2:11 am
Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long max(long a,long b) {
if (a < b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k) && (i != k))
if (matrix[k] > max(matrix[j],matrix[j][k]))
matrix[k] = max(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist
New poster
Posts: 5
Joined: Sun Jun 15, 2003 2:11 am
Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long max(long a,long b) {
if (a < b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k) && (i != k))
if (matrix[k] > max(matrix[j],matrix[j][k]))
matrix[k] = max(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist
New poster
Posts: 5
Joined: Sun Jun 15, 2003 2:11 am
Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

Code: Select all

``````#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long max(long a,long b) {
if (a < b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[i][0],&coord[i][1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[i][0] - coord[j][0]);
l = (long) (coord[i][1] - coord[j][1]);
matrix[i][j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k) && (i != k))
if (matrix[i][k] > max(matrix[i][j],matrix[j][k]))
matrix[i][k] = max(matrix[i][j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
``````

bigbit
New poster
Posts: 4
Joined: Fri Jun 27, 2003 3:39 pm

### 534-frogger- help!

What is output for:

5
1 0
2 0
3 0
4 0
4 1

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### 534

I use Floyd Warshal's algoritm.
[pascal] Deleted...[/pascal]
Last edited by Eduard on Thu Apr 08, 2004 6:23 pm, edited 1 time in total.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
I find my bag ... at the beginning matrix must be infinity(like a maxlongint) not 0.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

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

### 534: Why wrong? Is MST solution?

Hi,

I tried to solve the 534 and implemented MST-Kruskal and nothing.

Do Problem want to know the minimax jumpy? Ok?

Have Someone input for test?

My Code:

[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_VERTICES 205
#define MAX_ARESTAS 206*206
#define INFINITO 1000000000000.0

typedef struct {
int x, y;
} Ponto;

typedef struct {
int u, v;