851 - Maze
Posted: Tue Jun 18, 2002 11:08 am
Do I need to walk UNTIL i reach a blocked location? or I can stop anywhere and continue to the next direction?
Page 1 of 3
Posted: Tue Jun 18, 2002 12:00 pm
You may always change direction after moving one field.
Posted: Tue Jun 18, 2002 12:51 pm
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
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
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
Is
west
north
a correct output for
OOO . .
. O . . .
. O . . .
. O . . .
?
west
north
a correct output for
OOO . .
. O . . .
. O . . .
. O . . .
?
851
Posted: Sat Sep 07, 2002 12:10 am
Sorry, i mean is
east
north
a correct output for
. . . . . .
. . .OO .
. . .OO .
.OOOO .
.O . . . .
. . . . . .
?
if not, how is the output should be?
thx
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
and how about
west
north
for
. . . . . .
.OO. O .
. . . . O.
.OO. . .
.O. . O.
. . . . . .
west
north
for
. . . . . .
.OO. O .
. . . . O.
.OO. . .
.O. . O.
. . . . . .
Re: 851
Posted: Tue Sep 10, 2002 1:53 pm
For the input
north
north
south
a correct output should bechchan3 wrote: . . . . . .
. . .OO .
. . .OO .
.OOOO .
.O . . . .
. . . . . .
thx
north
north
south
851 Maze II
Posted: Fri Dec 13, 2002 8:39 am
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 ???
but it takes too much time to pass the judge.
does anyone have a better solution ???
Posted: Tue Feb 04, 2003 10:05 am
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.
I used BFS, the program was slow (10+ sec), but it passed all test cases.
Posted: Tue Feb 04, 2003 6:12 pm
What do your BFS on? I can't seem to prune my BFS tree enough..
Posted: Fri Aug 01, 2003 8:05 am
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.
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
why "north" should 2x ?
isn't just
north
south
will work ?
isn't just
north
south
will work ?
Posted: Sat Apr 03, 2004 7:36 pm
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~
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~
851 Maze II
Posted: Fri Aug 05, 2005 6:54 am
I suffered from getting WA.
However, I tried to generate some test data.
Hope someone to verify this.
--
DJWS, a newbie in programming
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