851 - Maze

[CelebiX]

Do I need to walk UNTIL i reach a blocked location? or I can stop anywhere and continue to the next direction?

[Christian Schuster]

You may always change direction after moving one field.

[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

[Christian Schuster]

The locations which are considered as "escaped" are those you marked with "A":

Code: Select all

  OOAO
  A..O
  OO.A
  OAAO

[chchan3]

Is

west
north

a correct output for

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

?

[chchan3]

Sorry, i mean is

east
north

a correct output for

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

?
if not, how is the output should be?

thx

[chchan3]

and how about

west
north

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

[Yarin]

For the input

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

a correct output should be

north
north
south

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

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

[Larry]

What do your BFS on? I can't seem to prune my BFS tree enough..

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

[Riku]

why "north" should 2x ?
isn't just
north
south
will work ?

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

[DJWS]

I suffered from getting WA.
However, I tried to generate some test data.
Hope someone to verify this.

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