851 - Maze

Moderator: Board moderators

851 - Maze

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

Posts: 5
Joined: Tue Jun 18, 2002 11:05 am

You may always change direction after moving one field.

Christian Schuster
Learning poster

Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

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
CelebiX
New poster

Posts: 5
Joined: Tue Jun 18, 2002 11:05 am

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

Code: Select all
`  OOAO  A..O  OO.A  OAAO`

Christian Schuster
Learning poster

Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

851

Is

west
north

a correct output for

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

?
chchan3
New poster

Posts: 3
Joined: Fri Sep 06, 2002 11:53 pm

851

Sorry, i mean is

east
north

a correct output for

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

?
if not, how is the output should be?

thx
chchan3
New poster

Posts: 3
Joined: Fri Sep 06, 2002 11:53 pm

west
north

for
. . . . . .
.OO. O .
. . . . O.
.OO. . .
.O. . O.
. . . . . .
chchan3
New poster

Posts: 3
Joined: Fri Sep 06, 2002 11:53 pm

Re: 851

For the input

chchan3 wrote: . . . . . .
. . .OO .
. . .OO .
.OOOO .
.O . . . .
. . . . . .
thx

a correct output should be

north
north
south
Yarin
Problemsetter

Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume

851 Maze II

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 ???
LTH
New poster

Posts: 12
Joined: Fri Feb 08, 2002 2:00 am
Location: Taiwan

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.

cytse
Learning poster

Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong

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

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

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
New poster

Posts: 4
Joined: Fri Aug 01, 2003 7:45 am

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

Posts: 4
Joined: Fri Aug 01, 2003 7:45 am

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~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

851 Maze II

I suffered from getting WA.
However, I tried to generate some test data.
Hope someone to verify this.
Code: Select all
`205OOOOOO...OO.OOOO...OOOO.O5OOOOOO....O.OOOO...OOOOOO5OOOOOO....OOOOO....OOOOOO5OOOOOO...OOO.OO.....OOOOO5O.O.OO.O.O.....O.O.OO.O.O5......O.O.......O.O......5.......OO..O....O........5............O............5..........OOOOO..........5OO.OOOO......OOOO.OOOO.OO5OOOOOOOO.....OOOO.OOOO.OO5OOOOOOOO.....OOOO...OOOOO5O.OOOO.O..OOOOO..O.OOOO.O5O.O.O..O..OOOOO..O..O.O.O5OOOOOO...OO...OO...OOOO.O5OOOOOO...OO...OO...OOO.OO5OOOOOO...OO...OO...OO...O5OOOOOOOOOOOOOOOO...OOO.OO5OOOOOOOOOOOOOOOOOOOOOOOOO5.........................`

--
DJWS, a newbie in programming
DJWS
Learning poster

Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan

Next