Page 4 of 4
Posted: Sat Jul 02, 2005 1:44 pm
by A1
test
10307 - Killing Aliens in Borg Maze
Posted: Tue Dec 13, 2005 11:23 pm
by erikw
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!
Posted: Tue Dec 13, 2005 11:43 pm
by little joey
It's probably not the answer you want to get: I have the same output as you.
Posted: Tue Dec 13, 2005 11:49 pm
by erikw
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?
Posted: Wed Mar 15, 2006 7:34 pm
by roticv
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 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[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];
}
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
Posted: Sun Oct 26, 2008 5:54 am
by stcheung
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.
Re: 10307 - Killing Aliens in Borg Maze
Posted: Wed Jul 28, 2010 9:53 pm
by mubashwir
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
Re: 10307 - Killing Aliens in Borg Maze
Posted: Thu Jul 29, 2010 7:43 pm
by mubashwir
Re: 10307 - Killing Aliens in Borg Maze
Posted: Fri Nov 16, 2012 3:47 pm
by Muftee_Ruet
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.
Re: 10307 - Killing Aliens in Borg Maze
Posted: Fri Jan 03, 2014 1:36 pm
by dhruba07
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
