851 - Maze

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

Moderator: Board moderators

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

851 - Maze

Post by 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
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster »

You may always change direction after moving one field.

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

Post 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

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post 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


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

851

Post by chchan3 »

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

Post 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

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

Post by chchan3 »

and how about

west
north

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

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

Re: 851

Post by Yarin »

For the input
chchan3 wrote: . . . . . .
. . .OO .
. . .OO .
.OOOO .
.O . . . .
. . . . . .
thx
a correct output should be

north
north
south

LTH
New poster
Posts: 12
Joined: Fri Feb 08, 2002 2:00 am
Location: Taiwan
Contact:

851 Maze II

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

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

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

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

Post by Larry »

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

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

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

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

Post by Riku »

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

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

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

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

851 Maze II

Post 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:

Post Reply

Return to “Volume 8 (800-899)”