Page 1 of 3

851 - Maze

Posted: Tue Jun 18, 2002 11:08 am
by CelebiX
Do I need to walk UNTIL i reach a blocked location? or I can stop anywhere and continue to the next direction?

Posted: Tue Jun 18, 2002 12:00 pm
by Christian Schuster
You may always change direction after moving one field.

Posted: Tue Jun 18, 2002 12:51 pm
by CelebiX
thx for ur reply.

Another question:
You have ``escaped" whenever you reach a square on an outside edge of the grid.
squares on outside edge are those marked with X or those with A?? (plz refer to the sample input)

XXXXXX
XOOAOX
XA..OX
XOO.AX
XOAAOX
XXXXXX

Posted: Tue Jun 18, 2002 3:21 pm
by Christian Schuster
The locations which are considered as "escaped" are those you marked with "A":

Code: Select all

  OOAO
  A..O
  OO.A
  OAAO


851

Posted: Fri Sep 06, 2002 11:57 pm
by chchan3
Is

west
north

a correct output for

OOO . .
. O . . .
. O . . .
. O . . .

?

851

Posted: Sat Sep 07, 2002 12:10 am
by chchan3
Sorry, i mean is

east
north

a correct output for

. . . . . .
. . .OO .
. . .OO .
.OOOO .
.O . . . .
. . . . . .

?
if not, how is the output should be?

thx

Posted: Sat Sep 07, 2002 12:36 am
by chchan3
and how about

west
north

for
. . . . . .
.OO. O .
. . . . O.
.OO. . .
.O. . O.
. . . . . .

Re: 851

Posted: Tue Sep 10, 2002 1:53 pm
by Yarin
For the input
chchan3 wrote: . . . . . .
. . .OO .
. . .OO .
.OOOO .
.O . . . .
. . . . . .
thx
a correct output should be

north
north
south

851 Maze II

Posted: Fri Dec 13, 2002 8:39 am
by LTH
i cant imagine any other method except bute force search
but it takes too much time to pass the judge.
does anyone have a better solution ???

Posted: Tue Feb 04, 2003 10:05 am
by cytse
The one who is on top of the ranklist used A* search.

I used BFS, the program was slow (10+ sec), but it passed all test cases.

Posted: Tue Feb 04, 2003 6:12 pm
by Larry
What do your BFS on? I can't seem to prune my BFS tree enough..

Posted: Fri Aug 01, 2003 8:05 am
by Riku
mine is BFS, I'm using linked list to store information before processing, but I got memory limit :(

I've tried to count how many times I allocating memory and how many times I deallocating it, and they are the same.

the program runs very slow too, I just store the path, so I need to calculate everytime from the beginning. I use this method to save memory used, but still memory limit.

Posted: Tue Aug 05, 2003 2:24 am
by Riku
why "north" should 2x ?
isn't just
north
south
will work ?

Posted: Sat Apr 03, 2004 7:36 pm
by Observer
Hi everyone.

I suggest you solve this problem with A* search. It's easy to code, and it runs in reasonable time. (Mine runs for ~2 sec. How I wish I know IDA*...)

Hint: the number of moves required in the cases doesn't seem to exceed 30. :)

Have fun~ :D

851 Maze II

Posted: Fri Aug 05, 2005 6:54 am
by DJWS
I suffered from getting WA.
However, I tried to generate some test data.
Hope someone to verify this. :D

Code: Select all

20

5
OOOOO
O...O
O.OOO
O...O
OOO.O

5
OOOOO
O....
O.OOO
O...O
OOOOO

5
OOOOO
O....
OOOOO
....O
OOOOO

5
OOOOO
O...O
OO.OO
.....
OOOOO

5
O.O.O
O.O.O
.....
O.O.O
O.O.O

5
.....
.O.O.
.....
.O.O.
.....

5
.....
..OO.
.O...
.O...
.....

5
.....
.....
..O..
.....
.....

5
.....
.....
OOOOO
.....
.....

5
OO.OO
OO...
...OO
OO.OO
OO.OO

5
OOOOO
OOO..
...OO
OO.OO
OO.OO

5
OOOOO
OOO..
...OO
OO...
OOOOO

5
O.OOO
O.O..
OOOOO
..O.O
OOO.O

5
O.O.O
..O..
OOOOO
..O..
O.O.O

5
OOOOO
O...O
O...O
O...O
OOO.O

5
OOOOO
O...O
O...O
O...O
OO.OO

5
OOOOO
O...O
O...O
O...O
O...O

5
OOOOO
OOOOO
OOOOO
O...O
OO.OO

5
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO

5
.....
.....
.....
.....
.....
--
DJWS, a newbie in programming :wink: