Project Solution In this project, you will develop algorithms that find road routes throug

Project Solution

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 in the map considered as maximum latitudes and maximum longitudes respectively on the map. The character "X" in the file represents the water that means if a cell contains "X" then the traveler is not allowed to occupy that cell as this car is not 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 corner, and the goal is to drive to the island located at (MaxLattitude-1, MaxLongitudes-1) in the lower right corner. A legal move from an island is to move left, right, up, or down to an immediately adjacent cell that has road connectivity which means a cell that contains "0". Moving off any edge of the map is not allowed.

Input: The map files

Output: Print paths as explicitly specified for all the functions in Part A, Part B, and extra credit on the console.

You should have single main function that calls all the required functions for Part A, Part B, and extra credit for all the 3 given input map files one by one.

Coded graph.h file for your reference and provided it for you to refer to and download on canvas. You do not have to use this file mandatory, but if you are struggling to even start the project then this should definitely make your life much easier.

Part A

Consider the following class map,

classmap{public:map(ifstream&fin);voidprint(int,int,int,int);boolisLegal(inti,intj);voidsetMap(inti,intj,intn);intgetMap(inti,intj)const;intgetReverseMapI(intn)const;intgetReverseMapJ(intn)const;voidmapToGraph(graph&g);boolfindPathRecursive(graph&g,stack&moves);boolfindPathNonRecursive1(graph&g,stack&moves);bool findPathNonRecursive2(graph &g, queue &moves);boolfindShortestPath1(graph&g,stack&bestMoves);boolfindShortestPath2(graph&,vector&bestMoves);voidmap::printPath(stack&s);intnumRows(){returnrows;};intnumCols(){returncols;};private:introws;// number of latitudes/rows in the mapintcols;// number of longitudes/columns in the mapmatrixvalue;matrixmapping;// Mapping from latitude and longitude co-ordinates (i,j) values to node index valuesvectorreverseMapI;// Mapping from node index values to map latitude i valuevectorreverseMapJ;// Mapping from node index values to map longitude j value};1. Using the above class map, write functionvoid map::mapToGraph(graph &g){...} to create a graph g that represents the legal moves in the map m. Each vertex should represent a cell, and each edge should represent a legal move between adjacent cells.2. Write a recursive functionfindPathRecursive(graph&g,stack&moves)that looks for a path from the start island to the destination island. If a path from the start to the destination exists, your function shouldcall the map::printPath() function that shouldprint a sequence of correct moves (Go left, Go right, Go down, Go up, etc.). If no path from the start to the destination exists, the program should print, "No path exists".If a solution exists the solver should also simulate the solution to each map by calling the map::print() function.The map::print() function prints out a map visualization, 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 functionfindPathNonRecursive1(graph&g,stack&moves)that does the same thing as in 2, but by using stack and without using recursion. If a path from the start to the destination exists, your function shouldcall the map::printPath() function that shouldprint a sequence of correct moves (Go left, Go right, Go down, Go up, etc.). If no path from the start to the destination exists, the program should print, "No path exists".If a solution exists the solver should also simulate the solution to each map by calling the map::print() function.The map::print() function prints out a map 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 findPathNonRecursive2(graph &g, queue &moves) that does the same thing as in 2, but by using queue and without using recursion. If a path from the start to the destination exists, your function shouldcall the map::printPath() function that shouldprint a sequence of correct moves (Go left, Go right, Go down, Go up, etc.). If no path from the start to the destination exists, the program should print, "No path exists".If a solution exists the solver should also simulate the solution to each map by calling the map::print() function.The map::print() function prints out a map visualization, with the goal and c