10500 - Robot maps

[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]

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.

[Adrian Kuegel]

The input is wrong.
Look here:
http://acm.uva.es/board/viewtopic.php?t=3224

[Alexander Kozlov]

The input is wrong.
Look here:
http://acm.uva.es/board/viewtopic.php?t=3224

You are right!!!

Thank you very much!

[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?

[titid_gede]

seems easy, but what's wrong with this code?
[c]
--- cut after AC---
[/c]

[Alexander Kozlov]

Read the post of Adrian Kuegel!

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

[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

[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]

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

titid

[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]

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]

My method is the same as above method.
But still get WA@@

[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]

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