11160 - Going Together

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

Moderator: Board moderators

Post Reply
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

11160 - Going Together

Post by Observer »

This problem is good~ But I don't understand what the following line means:
A robot will move to a new position if it is an empty cell within the maze or it is one of the target cells...
What is the output for the following case:

Code: Select all

1
5
.....
ABC.X
....#
.....
...XX
Also, when one has entered an exit and then receive a leaving signal, will he move?

Thanks in advance.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11160 Going Together

Post by Jan »

Observer wrote:This problem is good~ But I don't understand what the following line means:
A robot will move to a new position if it is an empty cell within the maze or it is one of the target cells...
It means a robot will move to a new cell if the cell is empty(ie no obstacles, no robots, and you cant go outside the grid). Or if its a target cell and if no robot is in that cell then a robot can go to the cell. And all of them will move simultaneously.

Code: Select all

.ABC
....
....
....
If the move is left then the new position will be

Code: Select all

ABC.
....
....
....
And the output of your input is
Output:

Code: Select all

Case 1: 6
Observer wrote:Also, when one has entered an exit and then receive a leaving signal, will he move?
Yes. He will move, too.

Hope these help.
Ami ekhono shopno dekhi...
HomePage

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny »

isnt it backtracking?
i got TLE.
any hint pls 2 make it faster.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Thanks Jan. I have got Accepted. :wink:

My algorithm is a search.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

windbells
New poster
Posts: 2
Joined: Sun Jan 21, 2007 6:28 pm

Post by windbells »

Can you test my program plz?
It gets WA since the contest, but I don't know why, I just use Bfs to solve it. Thanks!

Code: Select all

#include <stdio.h>
#include <string.h>

const int Max = 1000000;
const int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

char flag[Max], map[10][12];
int dp[Max], queue[Max], n, tail, tag, start;

void sort(int pos[]) {
	for(int i = 0;i < 3;i ++)
		for(int j = i+1;j < 3;j ++)
			if(pos[i] > pos[j]) {
				int tmp = pos[i];
				pos[i] = pos[j];
				pos[j] = tmp;
			}
}

void input() {
	scanf("%d",&n);
	int pos[3], t, i;
	for(i = 0;i < n;i ++) scanf("%s",map[i]);
	for(i = t = 0;i < n;i ++)
		for(int j = 0;j < n;j ++)
			if(map[i][j] == 'X') {
				pos[t ++] = i*n + j;
				map[i][j] = '.';
			}
	sort(pos);
	tag = pos[0]*10000+pos[1]*100+pos[2];
	for(i = t = 0;i < n;i ++)
		for(int j = 0;j < n;j ++)
			if(map[i][j] == 'A'||map[i][j] == 'B'||map[i][j] == 'C') {
				pos[t ++] = i*n + j;
				map[i][j] = '.';
			}
	sort(pos);
	start = pos[0]*10000+pos[1]*100+pos[2];
}

int move(int t,int k) {
	int i = t/n, j = t%n;
	i += dir[k][0]; j += dir[k][1];
	if(i >= 0&&i < n&&j >= 0&&j < n&&map[i][j] != '#')
		t = i*n + j;
	return t;
}

void solve() {
	memset(flag, 0, sizeof(flag));
	queue[0] = start; tail = 1;
	flag[start] = 1; dp[start] = 0;
	for(int i = 0;i < tail;i ++) {
		int pos[3], tpos[3];
		pos[0] = queue[i]/10000; pos[1] = queue[i]%10000/100; pos[2] = queue[i]%100;
		for(int j = 0;j < 4;j ++) {
			for(int k = 0;k < 3;k ++)
				tpos[k] = move(pos[k], j);
			sort(tpos);
			if(tpos[0] == tpos[1]||tpos[1] == tpos[2]) continue;
			int tmp = tpos[0]*10000+tpos[1]*100+tpos[2];
			if(!flag[tmp]) {
				flag[tmp] = 1;
				queue[tail ++] = tmp;
				dp[tmp] = dp[queue[i]] + 1;
			}
		}
		if(flag[tag]) { printf("%d\n", dp[tag]); return ; }
	}
	printf("trapped\n");
}

int main() {
	int t;
	scanf("%d",&t);
	for(int cas = 1;cas <= t;cas ++) {
		input();
		printf("Case %d: ",cas);
		solve();
	}
	return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Try the following I/O sets...

Input:

Code: Select all

1
3
.AC
#.B
XXX
Output:

Code: Select all

Case 1: 4
The moves are - down, left, left, down.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

windbells
New poster
Posts: 2
Joined: Sun Jan 21, 2007 6:28 pm

Post by windbells »

Thanks!

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Post by cypressx »

Can you share more tests , please ? I pass all the tests on the board and from the problem statement , and still I can't AC it.

Thanks in advance !

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

Heres some io test.
Input:

Code: Select all

8
5
..#.B
.#..A
#...C
.X.X.
.#X#.
5
..#.B
..#.A
..#.C
.X.X.
.#X#.
5
..#.B
..#.A
...#C
.X.X.
.#X#.
5
XX#.B
..#.A
..X#C
.....
.#.#.
5
XX#.B
#.#.A
#.X#C
.....
#####
5
XX#.B
#X##A
#.##C
#....
#####
5
X...B
#..#A
####C
X...X
#####
5
X....
B..#A
#C##.
X...X
#####
Output:

Code: Select all

Case 1: 6
Case 2: 7
Case 3: 8
Case 4: 11
Case 5: 14
Case 6: 13
Case 7: 7
Case 8: trapped
>>windbell
Please don't forget removing your cdoe after AC.
Last edited by rio on Mon Jun 23, 2008 7:28 am, edited 1 time in total.

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Re: 11160 - Going Together

Post by smilitude »

i wasted half an hour in rio's 6th case

Code: Select all

5
XX#.B
#X##A
# ##C
#....
#####
(with an unwanted space instead of '.', which was not supposed to be there)
till i understood whats going on!

it should be

Code: Select all

5
XX#.B
#X##A
#.##C
#....
#####
yeah, it clogged up what i was doing with cin , and really crushed my spirit! :(
thanks anyway! :P and thanks jan for the last case! :)
fahim
#include <smile.h>

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Re: 11160 - Going Together

Post by rio »

:oops: Sorry for wasting your time :oops:

I edited the test case.
-----
Rio

Post Reply

Return to “Volume 111 (11100-11199)”