Page 1 of 3
534 - Frogger
Posted: Wed Sep 25, 2002 8:10 am
by Dominik Michniewski
Could anyone help me?
I use to solve this problem following algorith:
1. read data
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
Posted: Tue Apr 08, 2003 6:12 am
by yiuyuho
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?
Posted: Tue Apr 08, 2003 6:16 am
by yiuyuho
Is there another way of doing this problem by MST, Prims?
Posted: Tue Apr 08, 2003 7:34 am
by turuthok
I just got this AC-ed this morning ... I used Floyd-Warshall for this problem ...
-turuthok-
Posted: Tue Apr 08, 2003 7:45 am
by Dominik Michniewski
I change my implementation to Floyd and got Acc too ....
Thanks all
DM
Posted: Sun Jun 15, 2003 2:27 am
by sunkist
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]
Posted: Sun Jun 15, 2003 2:31 am
by sunkist
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]
Posted: Sun Jun 15, 2003 2:41 am
by sunkist
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]
Posted: Sun Jun 15, 2003 2:47 am
by sunkist
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]
Posted: Sun Jun 15, 2003 2:48 am
by sunkist
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++;
}
}
534-frogger- help!
Posted: Fri Jun 27, 2003 3:44 pm
by bigbit
What is output for:
5
1 0
2 0
3 0
4 0
4 1
I need more test cases. Please help!
534
Posted: Wed Apr 07, 2004 9:54 pm
by Eduard
Please help me.Tell me where I'm worong.
I use Floyd Warshal's algoritm.
[pascal] Deleted...[/pascal]
Posted: Thu Apr 08, 2004 6:19 pm
by Eduard
I find my bag ... at the beginning matrix must be infinity(like a maxlongint) not 0.
534: Why wrong? Is MST solution?
Posted: Wed Sep 01, 2004 12:20 pm
by wanderley2k
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;
bool usada;
double peso;
} Aresta;
Aresta arestas[MAX_ARESTAS]; // Conjunto de Arestas
int id[MAX_VERTICES]; // id da componente que o vertice esta
int sz[MAX_VERTICES]; // Tamanho da componente
int numArestas; // N
