10307 - Killing Aliens in Borg Maze

Moderator: Board moderators

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

10307 - Killing Aliens in Borg Maze

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 ??

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Sorry

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?

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Hi!

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

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

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

10307 Killing Aliens in Borg Maze

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.

[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]

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

10307

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. " ?``
Thanks a lot!

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
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)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
The borgs can only split at aliens, not in arbitrary cells!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Off course - I miss this
Thanks

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)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
You can also split in the beginning, of course

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
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)

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

faster algorithm

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...

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Re: faster algorithm

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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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...

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm
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