## 10307 - Killing Aliens in Borg Maze

Moderator: Board moderators

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
test

erikw
New poster
Posts: 2
Joined: Tue Dec 13, 2005 10:37 pm
Location: Sweden

### 10307 - Killing Aliens in Borg Maze

Have been trying to solve this problem by using a graph theory approach. Assuming each alien (and start position) is a vertex in a graph I first build a set of edges between all vertices using BFS. From the set of vertices and edges I build a MST using Prim's algorithm (counting the total cost while building it). I get the expected output for the example test cases and some other cases I found in previous threads regarding this problem. I gathered a couple of test cases and I would be grateful if someone with an accepted solution would post their output.

Code: Select all

``````13
6 5
#####
#A#A##
# # A#
#S  ##
#####
7 7
#####
#AAA###
#    A#
# S ###
#     #
#AAA###
#####
4 3
####
#SA#
####
8 3
########
#A S A #
########
8 3
########
#ASAAAA#
########
20 24
###################
#      #     #    #
#   ####A   A#### #
#   A  # # # #  A #
#     A# # # #A   #
#   A  # #A# #  A #
#    # ### ### #  #
######A A S A A####
#AA A# ### ### #  #
# A    # #A# #  A #
####AAA# # # #A   #
#   A A# # # #  A #
#   ####A   A#### #
#      #     #    #
#      #     #    #
#                 #
# AA  A           #
#                 #
#                 #
#  A              #
#                 #
#                 #
# AA  A           #
###################
5 9
###
#A#
# #
# ###
#  S#
# ###
# #
#A#
###
5 50
#####
# S #
### #
#   #
# ###
#   #
#  A#
#   #
#   #
#   #
#A  #
#A  #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
# # #
# # #
#   #
#  A#
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
##  #
#A  #
#   #
#   #
# #A#
#   #
#   #
##  #
# A##
#####
50 6
#################################################
#  A#       A                                   #
#  A#    ###############    A###########     A  #
#   # A  # A           ###### A        ######   #
#        #        AAA                       SA  #
#################################################
8 8
#######
#     #
#     #
# AAA #
# ASA #
# AAA #
#     #
#######
1 1
#
3 3
###
#S#
###
25 14
########################
#                      #
# AAAAA         AAAAA  #
#  AAAAA       AAAAA   #
# AAAAA         AAAAA  #
#  AAAAA       AAAAA   #
# AAAAA         AAAAA  #
#  AAAAA   S   AAAAA   #
# AAAAA         AAAAA  #
#  AAAAA       AAAAA   #
# AAAAA         AAAAA  #
#  AAAAA       AAAAA   #
#                      #
########################
``````
I get the following output:

Code: Select all

``````>./10307 <borgmaze.txt
8
11
1
4
5
87
10
61
90
8
0
0
106
``````
Thanks!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
It's probably not the answer you want to get: I have the same output as you.

erikw
New poster
Posts: 2
Joined: Tue Dec 13, 2005 10:37 pm
Location: Sweden
little joey wrote:It's probably not the answer you want to get: I have the same output as you.
Doh.. I wonder why I get WA. I double checked that I did submit it as the correct problem (10307). Can anyone think of any other critical cases which i didn't cover in my test input?

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am
I encountered the same problem. I keep getting WA.

Just a question, is it possible that the A appear outside the perimeter? How do you handle such cases?

My code looks like this

Code: Select all

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

int x,y,z,i,j,cnt;
char map[105][105];
char map2[105][105];
char visit[105][105];

int graph[105][105];
int dis[105];
char intree[105];

#define MAX 10000

int isempty(){
return 1;
return 0;
}

void enqueue(int a){
printf("Overflow\n");
}
queue[qtail++] = a;
if (qtail >= MAX)
qtail = 0;
return;
}

int dequeue(){
int a;
printf("Underflow\n");
return a;
}

void BFS(int source){
int tmp, row, col,u;
while (!isempty()){
tmp = dequeue();
row = tmp / 1000;
col = tmp % 1000;
if (map2[row][col] == -1)
continue;
if (map2[row][col] > 0){
u = map2[row][col];
graph[source][u] = visit[row][col]-1;
graph[u][source] = visit[row][col]-1;
}
if (row > 0 && visit[row-1][col] == 0){
tmp = (row-1) * 1000 + col;
enqueue(tmp);
visit[row-1][col] = visit[row][col]+1;
}
if (col > 0 && visit[row][col-1] == 0){
tmp = row* 1000 + col - 1;
enqueue(tmp);
visit[row][col-1] = visit[row][col]+1;
}
if (row < y-1 && visit[row+1][col] == 0){
tmp = (row+1)*1000 + col;
enqueue(tmp);
visit[row+1][col] = visit[row][col]+1;
}
if (col < x-1 && visit[row][col+1] == 0){
tmp = row* 1000 + col + 1;
enqueue(tmp);
visit[row][col+1] = visit[row][col]+1;
}
}
return;
}

int prim(int nvert){
int ii,jj,mindis,treesize = 2, start = 0, total = 0;
for (ii=1; ii < nvert; ii++){
dis[ii] = 1000000000;
intree[ii] = 0;
}
intree[1] = 1;
for (ii=2; ii < nvert; ii++)
dis[ii] = graph[1][ii];
while (treesize < nvert){
mindis = 1000000000;
for (jj=1; jj<nvert; jj++){
if (dis[jj] < mindis && intree[jj]==0){
mindis = dis[jj];
ii = jj;
}
}
treesize++;
total += mindis;
intree[ii] = 1;
for (jj = 1; jj < nvert; jj++)
if (dis[jj] > graph[ii][jj] && intree[jj] == 0)
dis[jj] = graph[ii][jj];
}
}

int main(){
scanf("%d ",&z);
while (z--){
scanf("%d %d ",&x,&y);
for (i=0;i<y;i++)
gets(&map[i][0]);
cnt = 1;
for (i=0;i<y;i++)
for (j=0;j<x;j++){
if (map[i][j] == 'A' || map[i][j] == 'S'){
map2[i][j] = cnt;
cnt++;
}
if (map[i][j] == ' ')
map2[i][j] = 0;
if (map[i][j] == '#')
map2[i][j] = -1;
}
for (i=0;i<y;i++)
for (j=0;j<x;j++)
if (map2[i][j] > 0){
memset(visit,0x0,sizeof(visit));
enqueue(j + 1000*i);
visit[i][j] = 1;
BFS(map2[i][j]);
}
printf("%d\n",prim(cnt));
}
return 0;
}
``````

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### Re: 10307 - Killing Aliens in Borg Maze

This problem is very lenient on the timing, so no need for any optimization at all. My Java solution did the most straightforward thing and still got AC in < 0.4 sec:
(1) For each starting point/alien location, do simple bfs to find distance to other aliens.
(2) Build mst using Prim's algorithm, starting with the starting point

There doesn't seem to be any tricky cases, and you can assume everything is surrounded by the walls as mentioned in the problem statement. I know others have already mentioned the algorithm above, but given there are also some posts about how to speed this up, I just want to reiterate that this algorithm is fast enough for you to get AC.

mubashwir
New poster
Posts: 5
Joined: Sat May 22, 2010 8:47 am
Contact:

### Re: 10307 - Killing Aliens in Borg Maze

I understood that in this problem I have to run BFS from all alien and generate a new graph....then using MST I can come up with the ANSWER. But in this method there is a problem arise nd I don't understand how can i fix it.

i described the problem with this pic bellow:

http://www.maam.99k.org/10307/index.html

please describe me elaborately how can i get rid of this kind of problem.

Thank u
........I am a simple man having a few simple dream........
.......................................AIUBCSE......................................

mubashwir
New poster
Posts: 5
Joined: Sat May 22, 2010 8:47 am
Contact:

### Re: 10307 - Killing Aliens in Borg Maze

When my concept was clear about the problem i understood that it is not a hard problem but the code would be large enough. Then start coding and after finishing code I found lots of Bugs. After fixing those bugs I got Accepted in 1st submission (0.064 sec).
........I am a simple man having a few simple dream........
.......................................AIUBCSE......................................

Muftee_Ruet
New poster
Posts: 10
Joined: Fri Sep 16, 2011 6:36 am

### Re: 10307 - Killing Aliens in Borg Maze

I gathered a couple of test cases and I would be grateful if someone with an accepted solution would post their output.

Code: Select all

``````13
6 5
#####
#A#A##
# # A#
#S  ##
#####
7 7
#####
#AAA###
#    A#
# S ###
#     #
#AAA###
#####
4 3
####
#SA#
####
8 3
########
#A S A #
########
8 3
########
#ASAAAA#
########
20 24
###################
#      #     #    #
#   ####A   A#### #
#   A  # # # #  A #
#     A# # # #A   #
#   A  # #A# #  A #
#    # ### ### #  #
######A A S A A####
#AA A# ### ### #  #
# A    # #A# #  A #
####AAA# # # #A   #
#   A A# # # #  A #
#   ####A   A#### #
#      #     #    #
#      #     #    #
#                 #
# AA  A           #
#                 #
#                 #
#  A              #
#                 #
#                 #
# AA  A           #
###################
5 9
###
#A#
# #
# ###
#  S#
# ###
# #
#A#
###
5 50
#####
# S #
### #
#   #
# ###
#   #
#  A#
#   #
#   #
#   #
#A  #
#A  #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
# # #
# # #
#   #
#  A#
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
#   #
##  #
#A  #
#   #
#   #
# #A#
#   #
#   #
##  #
# A##
#####
50 6
#################################################
#  A#       A                                   #
#  A#    ###############    A###########     A  #
#   # A  # A           ###### A        ######   #
#        #        AAA                       SA  #
#################################################
8 8
#######
#     #
#     #
# AAA #
# ASA #
# AAA #
#     #
#######
1 1
#
3 3
###
#S#
###
25 14
########################
#                      #
# AAAAA         AAAAA  #
#  AAAAA       AAAAA   #
# AAAAA         AAAAA  #
#  AAAAA       AAAAA   #
# AAAAA         AAAAA  #
#  AAAAA   S   AAAAA   #
# AAAAA         AAAAA  #
#  AAAAA       AAAAA   #
# AAAAA         AAAAA  #
#  AAAAA       AAAAA   #
#                      #
########################
``````
I get the following output:

Code: Select all

``````>./10307 <borgmaze.txt
8
11
1
4
5
87
10
61
90
8
0
0
106
``````
Thanks!

My Accepted code gives the same output for your input.

dhruba07
New poster
Posts: 20
Joined: Tue May 21, 2013 9:02 pm
Location: BUET

### Re: 10307 - Killing Aliens in Borg Maze

I am getting time limit for this problem.
My algortihm is :
1.finding SSSP from all pairs (A to A and S).Create a graph by them using BFS.
2.Then Run the normal MST to find the answer.

My program is returning the correct value for all the testcases

Here goes my code :

Code: Select all

``got AC :D``
The main thing I did wrong was to take a map to store distance like map<pair<int,int>,int> for BFS. I replaced it with an 2d array to store distance and it gave me AC
Accept who you are