## 10500 - Robot maps

Moderator: Board moderators

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

### 10500 - Robot maps

The problem seems to be easy but I got WA many times.

So some questions:

1. What character is used to mark an empty cell of the map:
is it a zero digit '0'
or
is it a letter 'O'?

I tried both and always got WA.

2. What may be the trick? Can somebody give us a hint?

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:
There's no big deal with this problem, you should just DFS from the beginning being careful NOT TO GO BACK. Just choose one of the four options and go. That's it.

There's no tricky input. This problem was the easier of the contest, but it was bad written ... now it's fixed.
[]s
Mauricio Oliveira Carneiro

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
The input is wrong.
Look here:
http://acm.uva.es/board/viewtopic.php?t=3224

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine
Adrian Kuegel wrote:The input is wrong.
Look here:
http://acm.uva.es/board/viewtopic.php?t=3224
You are right!!!

Thank you very much!

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

### 10500 - what is the meaning of number of movements?

looks easy but still got WA. i've also read thread before this. now i' m in doubt with "number of movements". what is it? is it " the most deepest level search?
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
seems easy, but what's wrong with this code?
[c]
--- cut after AC---
[/c]
Last edited by titid_gede on Tue Jul 22, 2003 5:20 pm, edited 1 time in total.
Kalo mau kaya, buat apa sekolah?

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

Try to mark initial cell as empty '0' before output the result.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
i've read adrian's post. that's why i set initial grid always to '0', dont care what it is.. (look at statement before i call flood fill function).

thank you,

titid
Kalo mau kaya, buat apa sekolah?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
You must make a difference between visiting a cell and determining the state of adjacent cells. Your flood_fill function is wrong for this problem.
Just realise, you don't have to maximize the number of visited cells, you only have to simulate according to the given rules. The robot takes the first unvisited cell in the given order no matter if he would be able to visit more cells if he uses another direction.
I marked visited cells with 'V', all unknown cells with '?' and all known cells with '0' or 'X'. Before printing I changed the 'V' to '0'.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
ugh.. i misunderstood the problem.. now got AC. thank you very much..

titid
Kalo mau kaya, buat apa sekolah?

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
and I set start position to 0,then simulate the problem
Still get wrong anwser
Could you give me some tricky input/output?
thx

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine
and I set start position to 0,then simulate the problem
Still get wrong anwser
Could you give me some tricky input/output?
thx
I got AC after the following steps:

1. Simulate the problem.
2. Set start position to 0.
3. Output the result.

I do not understand why but when I set start position to 0 and then simulate then problem my program get WA.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
My method is the same as above method.
But still get WA@@

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### 10500 WA! Why?

program p10500;
var
moves,x,y,px,py,i,j:integer;
map,robot:array[1..10,1..10] of char;
ch:char;

function canmove(xx,yy:integer):boolean;
begin
if ((xx < 1) or (yy < 1) or (xx > x) or (yy > y) or
(robot[xx,yy] <> '?') or (map[xx,yy] = 'X'))
then canmove := False
else canmove := True;
if(map[xx,yy] = 'X') then robot[xx,yy] := 'X';
end;

procedure go(xx,yy:integer);
begin
Inc(moves);
robot[xx,yy] := map[xx,yy];
if canmove(xx-1,yy) then go(xx-1,yy) else
if canmove(xx,yy+1) then go(xx,yy+1) else
if canmove(xx+1,yy) then go(xx+1,yy) else
if canmove(xx,yy-1) then go(xx,yy-1);
end;

begin
while True do
begin
if ((x = 0) and (y = 0)) then break;
for i:=1 to x do
begin
for j:=1 to y do
begin
while not(ch in ['X','0']) do read(ch);
map[i,j] := ch;
end;
end;
for i:=1 to x do
for j:=1 to y do
robot[i,j] := '?';
moves := -1; map[px,py] := '0';
go(px,py);
writeln;
for i:=1 to x do
begin
for j:=1 to y do write('|---');writeln('|');
for j:=1 to y do
write('| ',robot[i,j],' ');
writeln('|');
end;
for j:=1 to y do write('|---');writeln('|');
writeln;
writeln('NUMBER OF MOVEMENTS: ',moves);
end;
end.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I still get WA too, can someone post some inputs?