Hints:
Maze Traversal - You can use the grid of ones and zeros as a double-
subscripted array representation of a maze. The ones represent the
walls of the maze, and the zeros represent squares in the possible
paths through the maze.
If you have trouble in implementing the algorithm, you can use the
following simple heuristic algorithm.
It walks you through the maze and guarantees finding the exit
(assuming there is one). If there is no exit, you will arrive
at the starting location again. Place your right hand on the wall
to your right and begin walking forward. Never remove your hand from
the wall. If the maze turns to the right, you follow the wall to the
right. As long as you do not remove your hand from the wall, eventually
you will arrive at the exit of the maze. There may be a shorter path
than the one you have taken, but you are guaranteed to get out of the
maze.
Write a recursive function mazeTraverse to walk through the maze. The
function should receive as arguments an i-by-i character array represen-
ting the maze, and the starting location of the maze. As the function
mazeTraverse attempts to locate the exit from the maze, it should place
the character X in each square of the path. The function should display
the maze after each move, so the user can watch as the maze is solved.
Further improvements:
1. Generating mazes randomly - write a function mazeGenerator that takes
as an argument a double-subscripted i-by-i character array and randomly
produces a maze. The function should also provide the starting and ending
locations of the maze. Try your function mazeTraverse using several randomly
generated mazes.
2. Mazes of any size - generalize functions mazeTraverse and mazeGenerator
to process mazes of any width and height.
這會有用嗎？
--
Wipe them out, all of them!
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: u21-90.user.giga.net.tw