10307  Killing Aliens in Borg Maze
Moderator: Board moderators
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.
I get the following output:
Thanks!
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 #
# #
########################
Code: Select all
>./10307 <borgmaze.txt
8
11
1
4
5
87
10
61
90
8
0
0
106

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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
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 qhead, qtail, queue[MAX];
int isempty(){
if (qhead==qtail)
return 1;
return 0;
}
void enqueue(int a){
if ((qtail+1)%MAX == qhead){
printf("Overflow\n");
}
queue[qtail++] = a;
if (qtail >= MAX)
qtail = 0;
return;
}
int dequeue(){
int a;
if (qhead == qtail)
printf("Underflow\n");
a = queue[qhead++];
if (qhead >= MAX)
qhead = 0;
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[row1][col] == 0){
tmp = (row1) * 1000 + col;
enqueue(tmp);
visit[row1][col] = visit[row][col]+1;
}
if (col > 0 && visit[row][col1] == 0){
tmp = row* 1000 + col  1;
enqueue(tmp);
visit[row][col1] = visit[row][col]+1;
}
if (row < y1 && visit[row+1][col] == 0){
tmp = (row+1)*1000 + col;
enqueue(tmp);
visit[row+1][col] = visit[row][col]+1;
}
if (col < x1 && 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];
}
return total;
}
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;
}
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.
(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.
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 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......................................
.......................................AIUBCSE......................................
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......................................
.......................................AIUBCSE......................................

 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 #
# #
########################
Code: Select all
>./10307 <borgmaze.txt
8
11
1
4
5
87
10
61
90
8
0
0
106
My Accepted code gives the same output for your input.
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 :
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
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
Accept who you are