What is the output for the following case: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...

Code: Select all

```
1
5
.....
ABC.X
....#
.....
...XX
```

Thanks in advance.

**Moderator:** Board moderators

This problem is good~ But I don't understand what the following line means:
Also, when one has entered an exit and then receive a leaving signal, will he move?

Thanks in advance.

What is the output for the following case: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...

Code: Select all

```
1
5
.....
ABC.X
....#
.....
...XX
```

Thanks in advance.

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

Code: Select all

```
.ABC
....
....
....
```

Code: Select all

```
ABC.
....
....
....
```

Code: Select all

`Case 1: 6`

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

Hope these help.

Ami ekhono shopno dekhi...

HomePage

HomePage

Thanks Jan. I have got Accepted.

My algorithm is a search.

My algorithm is a search.

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

Try the following I/O sets...

**Input:**
**Output:**
The moves are - down, left, left, down.

Hope it helps.

Code: Select all

```
1
3
.AC
#.B
XXX
```

Code: Select all

`Case 1: 4`

Hope it helps.

Ami ekhono shopno dekhi...

HomePage

HomePage

Heres some io test.

**Input:**
**Output:**
>>windbell

Please don't forget removing your cdoe after AC.

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
```

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.

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!

Code: Select all

```
5
XX#.B
#X##A
# ##C
#....
#####
```

till i understood whats going on!

it should be

Code: Select all

```
5
XX#.B
#X##A
#.##C
#....
#####
```

thanks anyway! and thanks jan for the last case!

fahim

#include <smile.h>

#include <smile.h>

Sorry for wasting your time

I edited the test case.

-----

Rio

I edited the test case.

-----

Rio