10307 - Killing Aliens in Borg Maze

[A1]

test

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

[little joey]

It's probably not the answer you want to get: I have the same output as you.

[erikw]

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]

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]

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]

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

[mubashwir]

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

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

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

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