11160 - Going Together

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

[Jan]

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

Also, when one has entered an exit and then receive a leaving signal, will he move?

Yes. He will move, too.

Hope these help.

[sunny]

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

[Observer]

Thanks Jan. I have got Accepted.

My algorithm is a search.

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

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.

[windbells]

Thanks!

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

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.

[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! and thanks jan for the last case!

[rio]

Sorry for wasting your time

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