Page 1 of 4

10307 - Killing Aliens in Borg Maze

Posted: Fri Sep 06, 2002 10:22 am
by Even
there are 1 S and at most 100 A

I find all pairs distance( include S and A )

and use Prim to find MST, minimum cost

in my method...S and A are treat as the same.

but WA..

is there any tricky??

or I misunderstand something ??

please help ~~ thank you :)

Sorry

Posted: Fri Sep 06, 2002 10:28 am
by Even
stupid as me...

I find my mistake...

for there are 1 S and 100 A... there should be total 101 points

but my array size has only 100....so WA /.\

but... why WA not Rutime Error?

Hi!

Posted: Tue Sep 10, 2002 8:42 am
by cyfra
Hi!

This is not the first time when program should gave RE and it gives WA.

When I m writing a program in Pascal and I turn off Range checking then it sometimes happen that if I use array[1..100] and I want to write something to [101] place it writes it there !! But there can be other varaible and the whole program whill produce Wrong Answer...

I think that programs should be tested with Range checking but on the other hand it means that they will be working a little bit slower...

And I think that's all...

Good Luck :wink:

PS.
Did you write this program in C or in Pascal ??

10307 Killing Aliens in Borg Maze

Posted: Tue Mar 25, 2003 2:07 pm
by ahanys
I have curently wrong answer and on the test data I get the correct output. May somebody give some INPUT/OUTPUT or look at the code what's wrong on it.


Thanks in advance ahanys.
[cpp]
/* @JUDGE_ID: 9072XC 10307 C++ */
#include <stdio.h>
#include <stdlib.h>

const int MAX=100;
char p[MAX+1][MAX+1];
int map[MAX+1][MAX+1];
int used[MAX+1][MAX+1];
int m[101][101];

int cena=0;


struct point {
int x;
int y;
int val;
};

int cmp(const void *a, const void *b) {
point c = *((point *)a);
point d = *((point *)b);
if (c.val > d.val) {
return 1;
} else if (c.val < d.val) {
return -1;
} else {
return 0;
}
}




point body[101];
point fronta[(MAX+7) * (MAX+7)];
int velikost;

int main() {
int n;
scanf("%i", &n);
for (int a=0; a<n; a++) {
int x,y;
scanf("%i %i\n", &x, &y);
for (int i=0; i<y; i++) {
gets(p);
}

int uzel = 0;
for (int c=0; c<y; c++) {
for (int d=0; d<x; d++) {
if (p[c][d] == 'A' || p[c][d] == 'S') {
if (p[c][d] == 'S') p[c][d]='A';
body[uzel].x = d;
body[uzel].y = c;
body[uzel].val = 0;
map[c][d] = uzel++;
} else {
map[c][d] = -1;
}
}
}

for (int r=0; r<uzel; r++) {// pro kazdy uzel
fronta[0] = body[r];
velikost = 1;
int akt = 0;
for (int e=0; e<y; e++)
for (int f=0; f<x; f++) used[e][f]=0;


while (velikost > akt) {
point prvni = fronta[akt++];
if (p[prvni.y][prvni.x] == 'A' && !used[prvni.y][prvni.x]) {
m[r][map[prvni.y][prvni.x]] = prvni.val;
}
used[prvni.y][prvni.x] = 1;
prvni.val++;
if (p[prvni.y][prvni.x+1] != '#') {
if (!used[prvni.y][prvni.x+1]) {
fronta[velikost++] = prvni;
fronta[velikost-1].x++;
}

}
if (p[prvni.y][prvni.x-1] != '#') {
if (!used[prvni.y][prvni.x-1]) {
fronta[velikost++] = prvni;
fronta[velikost-1].x--;
}
}
if (p[prvni.y-1][prvni.x] != '#') {
if (!used[prvni.y-1][prvni.x]) {
fronta[velikost++] = prvni;
fronta[velikost-1].y--;
}
}
if (p[prvni.y+1][prvni.x] != '#') {
if (!used[prvni.y+1][prvni.x]) {
fronta[velikost++] = prvni;
fronta[velikost-1].y++;
}
}
}
}

point seznam[(MAX+7) * (MAX+7)];
int pocet=0;
for (int t=0; t<uzel; t++) {
for (int u=0; u<uzel; u++) {
if (t != u && m[t] != 0) {
point p1;
p1.x = t;
p1.y = u;
p1.val = m[t];
seznam[pocet++] = p1;
}
}
}
qsort(seznam, pocet, sizeof(point), cmp);



int kused[MAX+1];

int zbyva=uzel-1;
int komponenta=1;
for (int g=0; g<uzel; g++) kused[g]=0;

for (int q=0; q<pocet; q++) {
int pridej = 0;
if (zbyva == 0) break;
if (!kused[seznam[q].x]) {
pridej = 1;
}
if (!kused[seznam[q].y]) {
pridej += 2;
}
if (kused[seznam[q].y] != 0 && kused[seznam[q].x] != 0) {
if (kused[seznam[q].y] != kused[seznam[q].x]) {
pridej = 4;
}
}

if (pridej == 1) {
kused[seznam[q].x] = kused[seznam[q].y];
cena+=seznam[q].val;
zbyva--;
} else if (pridej == 2) {
kused[seznam[q].y] = kused[seznam[q].x];
cena+=seznam[q].val;
zbyva--;
} else if (pridej == 3) {
kused[seznam[q].x] = komponenta;
kused[seznam[q].y] = komponenta++;
cena+=seznam[q].val;
zbyva--;
} else if (pridej == 4) {
if (kused[seznam[q].y] > kused[seznam[q].x]) {
int mensi = kused[seznam[q].x];
int vetsi = kused[seznam[q].y];
for (int za=0; za<uzel; za++) {
if (kused[za]==vetsi) {
kused[za] = mensi;
}
}
} else {
int vetsi = kused[seznam[q].x];
int mensi = kused[seznam[q].y];
for (int z=0; z<uzel; z++) {
if (kused[z]==vetsi) {
kused[z] = mensi;
}
}
}
cena+=seznam[q].val;
zbyva--;
}
}

printf("%i\n", cena);
}

return 0;
}

[/cpp][/cpp]

10307

Posted: Mon Jul 21, 2003 4:05 pm
by hank
I cannot understand why the answer of the following input is "11"?

Code: Select all

#####  
#AAA###
#    A#
# S ###
#     #
#AAA###
##### 

Code: Select all

and why it said , "That is, if the original group walks five steps, then splits into two groups each walking three steps, the total distance is 11=5+3+3. " ?
please help me understand this "sample input"!
Thanks a lot! :D

Posted: Mon Jul 21, 2003 5:42 pm
by Per
I'm not sure what they mean by the text, but I'll show why the output is 11.

Let the borgs split once in the beginning, one group going upwards, one group going downwards, so we get (where B denotes a borg group):

Code: Select all

##### 
#ABA###
#    A#
#   ###
#     #
#ABA###
##### 
having walked a total of four steps (both groups take two steps). The groups then split again, each group taking one step left/right, and we get:

Code: Select all

##### 
#B B###
#    A#
#   ###
#     #
#B B###
##### 
having walked a total of eight steps (each of the four groups take one step). Finally, the group in the upper right walks the three steps to the last alien, and the total is now 11 steps.

Posted: Thu Jul 24, 2003 8:28 am
by Dominik Michniewski
But what about this (first sample) case ? Second is easy. But hw can I get 8 in this case ? Could anyone explain me ?

Code: Select all

6 5
##### 
#A#A##
# # A#
#S  ##
##### 
I always get 7!!!!!

Best regards
DM

Posted: Thu Jul 24, 2003 9:07 am
by Per
The borgs can only split at aliens, not in arbitrary cells!

Posted: Thu Jul 24, 2003 1:30 pm
by Dominik Michniewski
Off course - I miss this :)
Thanks

DM

Posted: Thu Jul 24, 2003 4:34 pm
by Larry
You can also split in the beginning, of course

Posted: Sat Jul 26, 2003 9:13 am
by Dominik Michniewski
I try to solve this problem using MST , but I got WA. Could anyone help me and tell me some special cases ??

Best regards
DM

faster algorithm

Posted: Sat Jul 26, 2003 10:59 am
by Faizur
I use bfs to get the distance btw them.and then i construct kruskal mst with them.But i recieved time limit exceed. I get accepted with my kruskal implementation in other mst problems.Is there any other faster algorithm to find the shortest distance in a maze.Help me...

Re: faster algorithm

Posted: Sat Jul 26, 2003 3:15 pm
by hank
Faizur wrote:I use bfs to get the distance btw them.and then i construct kruskal mst with them.But i recieved time limit exceed. I get accepted with my kruskal implementation in other mst problems.Is there any other faster algorithm to find the shortest distance in a maze.Help me...
I think Prim algorithm is better than kruskal in this problem.
And it it fast!
You don't have to get all the distance between them.
you just get the distance if needed.

Posted: Mon Jul 28, 2003 4:09 pm
by Larry
I use BFS to calculate the distance between all nodes, then I use Prim MST.. and my solution is ranked ~66th, so it isn't so bad...

Posted: Tue Jul 29, 2003 8:59 am
by Faizur
Thanks for the help. But i dont know which one will be more efficient in which case. Is there any documents or resources.Pls send me some hints