10500 - Robot maps

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

Moderator: Board moderators

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

10500 - Robot maps

Post by Alexander Kozlov »

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?

Many thanks in advance!!

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro »

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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

Post by Alexander Kozlov »

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?

Post by titid_gede »

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

Post by titid_gede »

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

Post by Alexander Kozlov »

Read the post of Adrian Kuegel!

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

Post by titid_gede »

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?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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

Post by titid_gede »

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

Post by windows2k »

I have read Adrian Kuegel's post
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

Post by Alexander Kozlov »

windows2k wrote:I have read Adrian Kuegel's post
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

Post by windows2k »

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?

Post by medv »

I read everything what is told here about this problem, but got WA. Help me, 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
readln(x,y);
if ((x = 0) and (y = 0)) then break;
readln(px,py);
for i:=1 to x do
begin
for j:=1 to y do
begin
read(ch);
while not(ch in ['X','0']) do read(ch);
map[i,j] := ch;
end;
end;
readln;
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:

Post by Larry »

I still get WA too, can someone post some inputs?

Post Reply

Return to “Volume 105 (10500-10599)”