program in c.

Maze Solving For this project, write a C program that will find its way through a maze using the depth-first search algorithm. This program takes input from a file where the filename is specified in the command line arguments. The input file will only contain two integer values per line of input: The first valid line gives the size of the 2-D maze (the number of rows given by the first number, then the number of columns given by the second number), valid values are >-1 . The second valid line gives the coordinates of the starting position in the maz Invalid: column 20 is outside range from 1 to 7 -> Starting position is at position 5, .1 24 2 Invalid: row 24 is outside of range from 1 to 15 -> Ending position is at position 3, 3 1 10 Invalid: column 10 is outside range from 1 to7 Invalid: column 9 is outside range from 1 to7 Invalid: column 8 is outside range from 1 to7 Invalid: attempting to block starting position CS211 - Programming Practicum Spring 2019 The algorithm you are to use to find a path through the maze is a Depth First Search. You MUST use the following form Depth First Search. You are NOT allowed to use a recursive version of the depth first search (since you are required to use your own linked list stack to solve this) * * . Mark all unblocked positions in the maze as "UNVISITED" push the start position's coordinates on the stack mark the start position as "VISITED While (stack is not empty and end has not been found) o if the coordinate at the Top of the Stack is the end position then end has been found (break out of loop) * o if the coordinate at the Top of the Stack has an unvisited (and unblocked) neighbor push the coordinates of one unvisited neighbor on the stack mark that one unvisited neighbor as visited * o else pop the coordinate at the Top of the Stack * If the stack is empty o The maze has no solution . else The items on the stack contain the coordinates of the solution from the end of the maze to the start of the maze. o When referring to neighbors, those positions will be the ones above, below, left or right of the current position (not diagonal). So for position x,y its neighbors are at +1 * x, y-1 Your program is to first output the size of the maze, the start and ending coordinates and an ASCII drawing of the maze. The code maze.c does this for any maze of size 30X30 or less. The maze.c program uses a static sized 2-D array; however, your program MUST use a dynamic 2-D array sized to reflect the maze size given in the input file. You must also dynamically deallocate this array at the end of your program. The maze.c program also does not do any error checking for invalid input, your program MUST check for invalid input Once the maze solving algorithm is run, you must then print out a message stating either: the maze has no solution or listing the coordinates of the locations of the path in the maze from the start of the maze to the end of the maze that was found by the algorithm. Note this means printing out the contents of the stack in reverse order. " The stack MUST use a linked list of coordinate values. The head of the linked list MUST NOT be global. It must be declared as a local variable in main) or some other function. You may create a structure to contain the head of the stack if you desire but again the initial instance of the structure must be a local variable. The code for each stack operation MUST be done in its own function where the head is passed in as a parameter. The only exception to this is that the initializing function may return a newly created instance CS211 - Programming Practicum Spring 2019 You MUST write functions for the following operations (these are the "same" functions as Project 2) e initializing the stack, * checking if the stack is empty, e pushing an element onto the stack, e popping an element off of the stack, e accessing the top element on the stack, and resetting the stack so that it is empty and ready to be used again These functions must NOT contain memory leaks! Expect points deducted if your code fails in this regard. (Valgrind will be used when grading.) Command Line Argument: Debug Mode Your program must be able to take one optional command line argument, the -d flag. When this flag is given, your program is to run in "debug" mode. When in this mode, your program is to display the coordinates of the maze positions as they are pushed onto the stack and popped off the stack if the Top of Stack coordinate does not have an unvisited (and unblocked) neighbor. When the flag is not given, this debugging information should not be displayed. Since the input file for the maze also comes from the command line arguments, you may not assume which order in which the command line arguments are given. Thus the command line arguments may be given as: ../a.out mazeInput.txt . /a.out mazeInput.txt -d ./a.out -d mazeInput.txt One simple way to set up a "debugging" mode is to use a boolean variable which is set to true when debugging mode is turned on but false otherwise. Then using a simple if statement controls whether information should be output or not. if ( debugMode-TRUE) printf(" Debugging Information In"); Optional ways for writing this code can be seen on the course website. #include #include typedef struct mazeStruct char arr[32] [32]; /* allows for a maze of size 30x30 plus outer walls int xsize, ysize; int xstart, ystart; int xend, yend; maze; int main (int argc, char "argv) maze m1; int xpos, ypos; int i.j FILE src verify the proper number of command line arguments were given if(argc!- 2) printf("Usage: %s ", argv[0]); exit(-1); /* Try to open the input file. if ((src fopen( argv[1], "r"NULL) printf ( "can't open input file: %s", argv[1] ); exit(-1) *read in the size, starting and ending positions in the maze fscanf (src, "%d %d", &ml.xsize, &m1.ys.ze); fscanf (src, "%d %d", &ml.xstart, &m1.ystart); fscanf (src, "%d %d", &m1.xend. &m1.yend); print them out to verify the input printf (''size: %d, %d ", ml.xsize, m1.ys.ze); printf (start: %d, %d ", ml.xstart, m1.ystart); printf (''end: %d, %d ", ml.xend, m1.yend): initialize the maze to empty for (i = 0: i