Page 1 of 1
11160 - Going Together
Posted: Sun Jan 21, 2007 12:29 pm
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:
Also, when one has entered an exit and then receive a leaving signal, will he move?
Thanks in advance.
Re: 11160 Going Together
Posted: Sun Jan 21, 2007 2:21 pm
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.
If the move is left then the new position will be
And the output of your input is
Output:
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.
Posted: Sun Jan 21, 2007 2:29 pm
by sunny
isnt it backtracking?
i got TLE.
any hint pls 2 make it faster.
Posted: Sun Jan 21, 2007 3:46 pm
by Observer
Thanks Jan. I have got Accepted.
My algorithm is a search.
Posted: Sun Jan 21, 2007 6:33 pm
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;
}
Posted: Sun Jan 21, 2007 11:08 pm
by Jan
Try the following I/O sets...
Input:
Output:
The moves are - down, left, left, down.
Hope it helps.
Posted: Mon Jan 22, 2007 4:19 am
by windbells
Thanks!
Posted: Mon Jan 22, 2007 12:56 pm
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 !
Posted: Fri Jan 26, 2007 8:40 am
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
#####
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.
Re: 11160 - Going Together
Posted: Sun Jun 22, 2008 7:20 pm
by smilitude
i wasted half an hour in rio's 6th case
(with an unwanted space instead of '.', which was not supposed to be there)
till i understood whats going on!
it should be
yeah, it clogged up what i was doing with cin , and really crushed my spirit!
thanks anyway!
and thanks jan for the last case!
Re: 11160 - Going Together
Posted: Mon Jun 23, 2008 7:29 am
by rio
Sorry for wasting your time
I edited the test case.
-----
Rio