Write a program that finds out a path in a maze. For example, a 4*7 maze can be represented as follows:
1011110
1011000
1000011
0010110
Here, ‘0’ represents that there is no obstacle (and ‘1’ otherwise), so one can only visit the ‘0’-locations. The bottom-left and top-right locations are always ‘0’, indicating there is always an entrance and an exit in the maze.
Your program needs to find a way from the bottom-left to the top-right and output the results as follows (The path must be marked as '2'):
0000002
0000222
0222200
2200000
We will provide the main function that deals with I/O. The input will be saved in the one-dimensional dynamic character array called maze consisting of only ‘1’ and ‘0’. The element of (i , j) will be saved at maze+i*n+j. All you need to do is find its path and save it at another one-dimensional character array called result_maze, which is declared in the main function. The element (i , j) also corresponds to the element result_maze+i*n+j, as shown in the sample output. Note that you don’t need to deal with the output. We already did that for you. Just save your results in the array result_maze. If there is no way to the destination, save ‘X’ at the beginning address of result_maze.
What you need to do?
You may need the following tools to do this assignment:
You may need to use a stack that stores all past history up to the current location. Your stack may need to double its size because the input may be more than its size.
You may need to use another dynamic array to mark the locations you have already visited just to avoid possibly looping around forever and never finding the exit.
(Using "stack" to solve this problem is a good idea, but it's not required, it's up to you.)
Attention!!!
We have provided the partial judge code (13035.c) below for you.
All you need to do is complete the find_path() function.
void find_path(const char *maze, const int m, const int n, char *result_maze){
...
...
}
By the way, you are also allowed to use other functions that you design if you need. For example :
void Function1(){
...
}
void Function2(){
...
}
void find_path(const char *maze, const int m, const int n, char *result_maze){
...
Function1()
...
Function2()
...
}
Finally, submit the find_path() function and other functions that you design to NTHU Online Judge.
You don't need to submit int main(){...} function, just submit the find_path() function and other functions that you design.