Consider the following class map, class map { public: map(ifstream &fin); void print(int,int,int,int); bool isLegal(int i, int j); void setMap(int i, int j, int n); int getMap(int i, int j) const; int getReverseMapI(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 map int cols; // number of longitudes/columns in the map matrix value; matrix mapping; // Mapping from latitude and longitude co-ordinates (i,j) values to node index values vector reverseMapI; // Mapping from node index values to map latitude i value vector reverseMapJ; // Mapping from node index values to map longitude j value }; 1. Using the above class map, write function void 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 function findPathRecursive(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 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 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 function findPathNonRecursive1(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 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 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 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 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 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 map input file: 7 10 Start - 0XXXXXXXXX 00000000XX 0X0X0X0XXX 0X0X0X0000 XX0XXX0XXX X0000000XX XXXXXXX000Z - Destination

Consider the following class map, class map { public: map(ifstream &fin); void print(int,int,int,int); bool isLegal(int i, int j); void setMap(int i, int j, int n); int getMap(int i, int j) const; int getReverseMapI(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 map int cols; // number of longitudes/columns in the map matrix value; matrix mapping; // Mapping from latitude and longitude co-ordinates (i,j) values to node index values vector reverseMapI; // Mapping from node index values to map latitude i value vector reverseMapJ; // Mapping from node index values to map longitude j value }; 1. Using the above class map, write function void 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 function findPathRecursive(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 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 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 function findPathNonRecursive1(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 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 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 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 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 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 map input file: 7 10 Start - 0XXXXXXXXX 00000000XX 0X0X0X0XXX 0X0X0X0000 XX0XXX0XXX X0000000XX XXXXXXX000Z - Destination

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Consider the following class map,

class map

{

public:

map(ifstream &fin);

void print(int,int,int,int);

bool isLegal(int i, int j);

void setMap(int i, int j, int n);

int getMap(int i, int j) const;

int getReverseMapI(int n) const;

int getReverseMapJ(int n) const;

void mapToGraph(graph &g);

bool findPathRecursive(graph &g, stack<int> &moves);

bool findPathNonRecursive1(graph &g, stack<int> &moves);

bool findPathNonRecursive2(graph &g, queue<int> &moves);

bool findShortestPath1(graph &g, stack<int> &bestMoves);

bool findShortestPath2(graph &, vector<int> &bestMoves);

void map::printPath(stack<int> &s);

int numRows(){return rows;};

int numCols(){return cols;};

private:

int rows; // number of latitudes/rows in the map

int cols; // number of longitudes/columns in the map

matrix<bool> value;

matrix<int> mapping; // Mapping from latitude and longitude co-ordinates (i,j) values to node index values

vector<int> reverseMapI; // Mapping from node index values to map latitude i value

vector<int> reverseMapJ; // Mapping from node index values to map longitude j value

};

1. Using the above class map, write function void 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 function findPathRecursive(graph &g, stack<int> &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 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 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 function findPathNonRecursive1(graph &g, stack<int> &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 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 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<int> &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 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 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 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 map input file:

7
10
Start - 0XXXXXXXXX
00000000XX
0X0X0X0XXX
0X0X0X0000
XX0XXX0XXX
X0000000XX
XXXXXXX000Z - Destination

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.