10500 - Robot Maps

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

Moderator: Board moderators

10500 - Robot Maps

Postby Alexander Kozlov » Sun Jun 15, 2003 4:57 pm

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!!
Alexander Kozlov
New poster
 
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

Postby carneiro » Sun Jun 15, 2003 7:24 pm

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
carneiro
Learning poster
 
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil

Postby Adrian Kuegel » Sun Jun 15, 2003 7:40 pm

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

Postby Alexander Kozlov » Tue Jun 17, 2003 4:04 pm

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!
Alexander Kozlov
New poster
 
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

10500 - what is the meaning of number of movements?

Postby titid_gede » Tue Jun 17, 2003 5:28 pm

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

Postby titid_gede » Wed Jun 18, 2003 5:04 pm

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?
titid_gede
Experienced poster
 
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Postby Alexander Kozlov » Thu Jun 19, 2003 3:52 pm

Read the post of Adrian Kuegel!

Try to mark initial cell as empty '0' before output the result.
Alexander Kozlov
New poster
 
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

Postby titid_gede » Thu Jun 19, 2003 4:55 pm

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?
titid_gede
Experienced poster
 
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Postby Adrian Kuegel » Thu Jun 19, 2003 9:29 pm

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'.
Adrian Kuegel
Guru
 
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Postby titid_gede » Fri Jun 20, 2003 5:25 pm

ugh.. i misunderstood the problem.. now got AC. thank you very much..

titid
Kalo mau kaya, buat apa sekolah?
titid_gede
Experienced poster
 
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Postby windows2k » Mon Jun 23, 2003 1:44 am

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
windows2k
Experienced poster
 
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Postby Alexander Kozlov » Mon Jun 23, 2003 9:43 am

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.
Alexander Kozlov
New poster
 
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

Postby windows2k » Mon Jun 23, 2003 4:58 pm

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

10500 WA! Why?

Postby medv » Fri Jun 27, 2003 7:21 pm

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.
medv
Learning poster
 
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

Postby Larry » Sat Jul 05, 2003 4:42 am

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

Next

Return to Volume CV

Who is online

Users browsing this forum: No registered users and 2 guests