1. Using the above class map, write function void map::mapToGraph(graph &g){...} to create a graph g that represents thelegal moves in the map m. Each vertex should represent a cell, and each edge should represent a legal move betweenadjacent cells.2. Write a recursive function findPathRecursive(graph &g, stack &moves) that looks for a path from the start islandto the destination island. If a path from the start to the destination exists, your function should call the map::printPath()function that should print a sequence of correct moves (Go left, Go right, Go down, Go up, etc.). If no path from thestart to the destination exists, the program should print, "No path exists". If a solution exists the solver should alsosimulate the solution to each map by calling the map::print() function. The map::print() function prints out a mapvisualization, with the goal and current position of the car in the map at each move, marked to show the progress. Hint:consider recursive-DFS.3. Write a function find PathNonRecursive1(graph &g, stack &moves) that does the same thing as in 2, but by usingstack and without using recursion. If a path from the start to the destination exists, your function should call themap::printPath() function that should print a sequence of correct moves (Go left, Go right, Go down, Go up, etc.). If nopath from the start to the destination exists, the program should print, "No path exists". If a solution exists the solvershould also simulate the solution to each map by calling the map::print() function. The map::print() function prints out amap visualization, with the goal and current position of the car in the map at each move, marked to show the progress.Hint: consider stack-based DFS.4. Write a function find PathNonRecursive2(graph &g, queue &moves) that does the same thing as in 2, but byusing queue and without using recursion. If a path from the start to the destination exists, your function should call themap::printPath() function that should print a sequence of correct moves (Go left, Go right, Go down, Go up, etc.). If nopath from the start to the destination exists, the program should print, "No path exists". If a solution exists the solvershould also simulate the solution to each map by calling the map::print() function. The map::print() function prints out amap visualization, with the goal and current position of the car in the map at each move, marked to show the progress.Hint: consider queue-based BFS.The code you submit should apply all three findPath functions to each map, one after the other.The map input files named map1.txt, map2.txt, and map3.txt can be downloaded from the canvas. Example of a mapinput file:710Start-OXXXXXXXX00000000XXOXOXOXOXXXOXOXOX0000XXOXXXOXXXX0000000XXXXXXXXX000Z - Destination In this project, you will develop algorithms that find road routes through the bridges to travel between islands.The input is a text file containing data about the given map. Each file begins with the number of rows and columns inthe map considered as maximum latitudes and maximum longitudes respectively on the map. The character "X" in thefile represents the water that means if a cell contains "X" then the traveler is not allowed to occupy that cell as this car isnot drivable on water. The character "0" in the file represents the road connected island. That means if a cell contains"0" then the traveler is allowed to occupy that cell as this car can drive on roads.The traveler starts at the island located at latitude = 0 and longitude = 0 (i.e., (0,0)) in the upper left comer, and the goalis to drive to the island located at (MaxLattitude-1, MaxLongitudes-1) in the lower right corner. A legal move from anisland is to move left, right, up, or down to an immediately adjacent cell that has road connectivity which means a cellthat contains "0". Moving off any edge of the map is not allowed.Input: The map filesOutput: Print paths as explicitly specified for all the functions in Part AYou should have single main function that calls all the required functions for Part A for all the 3 given input map filesone by one.Please use the graph.h file provided in this module for this project rather than the standard library file downloadedonline as it is specially modified to ease you work in this project. You do not have to use this file mandatory, but if youare struggling to even start the project then this should definitely make your life much easier.Part AConsider the following class map,class map{public:map(ifstream &fin):void print(int,int,int,int);bool isLegal(int i, int j);void setMaplint i, int j, int n);int getMap(int i, int j) const;int getReverseMapl(int n) const;int getReverseMapJ(int n) const;void mapToGraph(graph &g);bool findPathRecursive(graph &g, stack &moves);bool findPathNonRecursive1(graph &g, stack&moves);bool findPathNonRecursive2(graph &g, queue &moves);bool findShortestPath1(graph &g, stack &bestMoves);bool findShortestPath2(graph &, vector &bestMoves);void map::printPath(stack &s);int numRows(){return rows;};int numCols(){return cols;};private:int rows; // number of latitudes/rows in the mapint cols; // number of longitudes/columns in the mapmatrix value;matrix mapping: // Mapping from latitude and longitude co-ordinates (ij) values to node index valuesvector reverseMapl; // Mapping from node index values to map latitude i valuevector reverseMapJ; // Mapping from node index values to map longitude j value};

Question

1. Using the above class map, write function void map::mapToGraph(graph &g){...} to create a graph g that represents thelegal moves in the map m. Each vertex should represent a cell, and each edge should represent a legal move betweenadjacent cells.2. Write a recursive function findPathRecursive(graph &g, stack &moves) that looks for a path from the start islandto the destination island. If a path from the start to the destination exists, your function should call the map::printPath()function that should print a sequence of correct moves (Go left, Go right, Go down, Go up, etc.). If no path from thestart to the destination exists, the program should print, &#34;No path exists&#34;. If a solution exists the solver should alsosimulate the solution to each map by calling the map::print() function. The map::print() function prints out a mapvisualization, with the goal and current position of the car in the map at each move, marked to show the progress. Hint:consider recursive-DFS.3. Write a function find PathNonRecursive1(graph &g, stack &moves) that does the same thing as in 2, but by usingstack and without using recursion. If a path from the start to the destination exists, your function should call themap::printPath() function that should print a sequence of correct moves (Go left, Go right, Go down, Go up, etc.). If nopath from the start to the destination exists, the program should print, &#34;No path exists&#34;. If a solution exists the solvershould also simulate the solution to each map by calling the map::print() function. The map::print() function prints out amap visualization, with the goal and current position of the car in the map at each move, marked to show the progress.Hint: consider stack-based DFS.4. Write a function find PathNonRecursive2(graph &g, queue &moves) that does the same thing as in 2, but byusing queue and without using recursion. If a path from the start to the destination exists, your function should call themap::printPath() function that should print a sequence of correct moves (Go left, Go right, Go down, Go up, etc.). If nopath from the start to the destination exists, the program should print, &#34;No path exists&#34;. If a solution exists the solvershould also simulate the solution to each map by calling the map::print() function. The map::print() function prints out amap visualization, with the goal and current position of the car in the map at each move, marked to show the progress.Hint: consider queue-based BFS.The code you submit should apply all three findPath functions to each map, one after the other.The map input files named map1.txt, map2.txt, and map3.txt can be downloaded from the canvas. Example of a mapinput file:710Start-OXXXXXXXX00000000XXOXOXOXOXXXOXOXOX0000XXOXXXOXXXX0000000XXXXXXXXX000Z - Destination In this project, you will develop algorithms that find road routes through the bridges to travel between islands.The input is a text file containing data about the given map. Each file begins with the number of rows and columns inthe map considered as maximum latitudes and maximum longitudes respectively on the map. The character &#34;X&#34; in thefile represents the water that means if a cell contains &#34;X&#34; then the traveler is not allowed to occupy that cell as this car isnot drivable on water. The character &#34;0&#34; in the file represents the road connected island. That means if a cell contains&#34;0&#34; then the traveler is allowed to occupy that cell as this car can drive on roads.The traveler starts at the island located at latitude = 0 and longitude = 0 (i.e., (0,0)) in the upper left comer, and the goalis to drive to the island located at (MaxLattitude-1, MaxLongitudes-1) in the lower right corner. A legal move from anisland is to move left, right, up, or down to an immediately adjacent cell that has road connectivity which means a cellthat contains &#34;0&#34;. Moving off any edge of the map is not allowed.Input: The map filesOutput: Print paths as explicitly specified for all the functions in Part AYou should have single main function that calls all the required functions for Part A for all the 3 given input map filesone by one.Please use the graph.h file provided in this module for this project rather than the standard library file downloadedonline as it is specially modified to ease you work in this project. You do not have to use this file mandatory, but if youare struggling to even start the project then this should definitely make your life much easier.Part AConsider the following class map,class map{public:map(ifstream &fin):void print(int,int,int,int);bool isLegal(int i, int j);void setMaplint i, int j, int n);int getMap(int i, int j) const;int getReverseMapl(int n) const;int getReverseMapJ(int n) const;void mapToGraph(graph &g);bool findPathRecursive(graph &g, stack &moves);bool findPathNonRecursive1(graph &g, stack&moves);bool findPathNonRecursive2(graph &g, queue &moves);bool findShortestPath1(graph &g, stack &bestMoves);bool findShortestPath2(graph &, vector &bestMoves);void map::printPath(stack &s);int numRows(){return rows;};int numCols(){return cols;};private:int rows; // number of latitudes/rows in the mapint cols; // number of longitudes/columns in the mapmatrix value;matrix mapping: // Mapping from latitude and longitude co-ordinates (ij) values to node index valuesvector reverseMapl; // Mapping from node index values to map latitude i valuevector reverseMapJ; // Mapping from node index values to map longitude j value};

Accepted Answer

solution