10307 - Killing Aliens in Borg Maze

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Sat Jul 02, 2005 1:44 pm

test

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

10307 - Killing Aliens in Borg Maze

Post by erikw » Tue Dec 13, 2005 11:23 pm

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!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Dec 13, 2005 11:43 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

Post by erikw » Tue Dec 13, 2005 11:49 pm

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

Post by roticv » Wed Mar 15, 2006 7:34 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

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;
}

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

Re: 10307 - Killing Aliens in Borg Maze

Post by stcheung » Sun Oct 26, 2008 5:54 am

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
Location: Dhaka, Bangladesh
Contact:

Re: 10307 - Killing Aliens in Borg Maze

Post by mubashwir » Wed Jul 28, 2010 9:53 pm

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
Location: Dhaka, Bangladesh
Contact:

Re: 10307 - Killing Aliens in Borg Maze

Post by mubashwir » Thu Jul 29, 2010 7:43 pm

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). :lol: :lol: :lol: :lol:
........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

Post by Muftee_Ruet » Fri Nov 16, 2012 3:47 pm

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

Post by dhruba07 » Fri Jan 03, 2014 1:36 pm

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 :cry:

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 :D
Accept who you are :)

Post Reply

Return to “Volume 103 (10300-10399)”