(120%) Write a program to solve the maze traversal problem
described in Exercise 7.25 (page 313) of Chapter 7.
You need to have a recursive function
mazeTraverse to traverse the maze, but you don't need
to follow the argument convention decribed in the exercise.
In particular, you need to have the following line
#include "maze.c"
in your program, where the contents of "maze.c" could be:
#define SIZE 12
int maze[SIZE][SIZE]={
{'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
{'1', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1'},
{'0', '0', '1', '0', '1', '0', '1', '1', '1', '1', '0', '1'},
{'0', '1', '1', '0', '1', '0', '0', '0', '0', '1', '0', '1'},
{'0', '0', '0', '0', '0', '1', '1', '1', '0', '1', '0', '0'},
{'0', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'0', '0', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'0', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1'},
{'0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '0', '1'},
{'0', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1'},
{'1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '1'},
{'0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'}};
int start_i, start_j; /* starting point */
int end_i, end_j; /* end point */
In other words, the variables maze, start_i, start_j, end_i,
and end_j are all global. When you demo your program to TA,
he will have another different "maze.c" (which contains a
different maze of different size) for your program to
solve. Moverover, your program should be in a loop that
gets the starting and end points from the user. The following
is a sample output list:
Please enter the starting point:
0 0
Given starting point is illegal! Please enter the starting point again:
9 0
Please enter the end point:
4 11
Bingo! I found the solution:
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 X X X X X X 1
0 0 1 0 1 X 1 1 1 1 X 1
0 1 1 0 1 X X X X 1 X 1
0 0 0 0 0 1 1 1 X 1 X E
0 1 0 1 0 1 0 1 X 1 0 1
0 0 0 1 0 1 0 1 X 1 0 1
0 1 0 1 0 1 0 1 X 1 0 1
X X X X X X X X X 1 0 1
S 1 1 1 1 1 0 1 1 1 0 1
1 0 0 0 0 0 0 1 0 0 0 1
0 1 1 1 1 1 1 1 1 1 1 1
Do you want to try this program again? (1:yes, 0:no)
1
Please enter the starting point:
1 1
Please enter the end point:
4 11
Bingo! I found the solution:
1 1 1 1 1 1 1 1 1 1 1 1
1 S 0 0 1 X X X X X X 1
X X 1 0 1 X 1 1 1 1 X 1
X 1 1 0 1 X X X X 1 X 1
X 0 0 0 0 1 1 1 X 1 X E
X 1 0 1 0 1 0 1 X 1 0 1
X 0 0 1 0 1 0 1 X 1 0 1
X 1 0 1 0 1 0 1 X 1 0 1
X X X X X X X X X 1 0 1
0 1 1 1 1 1 0 1 1 1 0 1
1 0 0 0 0 0 0 1 0 0 0 1
0 1 1 1 1 1 1 1 1 1 1 1
Do you want to try this program again? (1:yes, 0:no)
1
Please enter the starting point:
11 0
Please enter the end point:
4 9
Given end point is illegal! Please enter the end point again:
4 10
There is no path conncecting the given starting and end points.
Do you want to try this program again? (1:yes, 0:no)
0
Thanks for using the maze solver written by XXX
Note that:
- When you print the maze, put 'S' at the starting
points and 'E' at the end points.
- Your program should check the validity of the given starting
and end points.
- Your program should strictly follow the "right hand rule"
described in the exercise.
- Your program should be able to detect the situation when
there is no solution at all.