1. Write a C++ function named pathExists that determines whether or not a there's a path from start to finish in a rectangular maze. Here is the prototype:

    bool pathExists(string maze[], int nRows, int nCols, int sr, int sc, int er, int ec); // Return true if there is a path from (sr,sc) to (er,ec) // through the maze; return false otherwise 

   The parameters are

   • A rectangular maze of Xs and dots that represents the maze. Each string of the array is a row of the maze. Each 'X' represents a wall, and each '.' represents a walkway.
   • The number of rows in the maze.
   • The number of columns in the maze. Each string in the maze parameter must be this length.
   • The starting coordinates in the maze: sr, sc; the row number is in the range 0 through nRows1, and the column number is in the range 0 through nCols1.
   • The ending coordinates in the maze: er, ec; the row number is in the range 0 through nRows1, and the column number is in the range 0 through nCols1.

   Here is an example of a simple maze with 5 rows and 7 columns:

    "XXXXXXX" "X...X.X" "XXX.X.X" "X.....X" "XXXXXXX" 

   The function must return true if in the maze as it was when the function was called, there is a path from maze[sr][sc] to maze[er][ec] that includes only walkways, no walls; otherwise it must return false. The path may turn west, south, east, and north, but not diagonally. When the function returns, it is allowable for the maze to have been modified by the function.

   Your solution must use the following simple class (without any changes), which represents an (r,c) coordinate pair:

    class Coord { public: Coord(int rr, int cc) : m_r(rr), m_c(cc) {} int r() const { return m_r; } int c() const { return m_c; } private: int m_r; int m_c; }; 

   (Our convention is that (0,0) is the northwest (upper left) corner, with south (down) being the increasing r direction and east (right) being the increasing c direction.)

   Your implementation must use a stack data structure, specifically, a stack of Coords. You may either write your own stack class, or use the stack type from the C++ Standard Library. Here's an example of the relevant functions in the library's stack type:

    #include  using namespace std; int main() { stack coordStack; // declare a stack of Coords Coord a(5,6); coordStack.push(a); // push the coordinate (5,6) coordStack.push(Coord(3,4)); // push the coordinate (3,4) ... Coord b = coordStack.top(); // look at top item in the stack coordStack.pop(); // remove the top item from stack if (coordStack.empty()) // Is the stack empty? cout << "empty!" << endl; cout << coordStack.size() << endl; // num of elements } 

   Here is pseudocode for your function:

    Push the starting coordinate (sr,sc) onto the coordinate stack and update maze[sr][sc] to indicate that the algorithm has encountered it (i.e., set maze[sr][sc] to have a value other than '.'). While the stack is not empty, { Pop the top coordinate off the stack. This gives you the current (r,c) location that your algorithm is exploring. If the current (r,c) coordinate is equal to the ending coordinate, then we've solved the maze so return true! Check each place you can move from the current cell as follows: If you can move WEST and haven't encountered that cell yet, then push the coordinate (r,c-1) onto the stack and update maze[r][c-1] to indicate the algorithm has encountered it. If you can move SOUTH and haven't encountered that cell yet, then push the coordinate (r+1,c) onto the stack and update maze[r+1][c] to indicate the algorithm has encountered it. If you can move EAST and haven't encountered that cell yet, then push the coordinate (r,c+1) onto the stack and update maze[r][c+1] to indicate the algorithm has encountered it. If you can move NORTH and haven't encountered that cell yet, then push the coordinate (r-1,c) onto the stack and update maze[r-1][c] to indicate the algorithm has encountered it. } There was no solution, so return false 

   Here is how a client might use your function:

    int main() { string maze[10] = { "XXXXXXXXXX", "X.X..X...X", "X....XXX.X", "X.XXXX.X.X", "X......XXX", "X.XX.X...X", "X.X..X.X.X", "X.X.XXXX.X", "X.X...X..X", "XXXXXXXXXX" }; if (pathExists(maze, 10,10, 4,6, 1,1)) cout << "Solvable!" << endl; else cout << "Out of luck!" << endl; } 

   In particular, your function may make the following simplifying assumptions (i.e., you do not have to check for violations):

   • the maze array contains nRows rows (you couldn't check for this anyway);
   • each string in the maze is of length nCols;
   • the maze contains only Xs and dots when passed in to the function;
   • the top and bottom rows of the maze contain only Xs, as do the left and right columns;
   • sr and er are between 0 and nRows-1, and sc and ec are between 0 and nCols-1;
   • maze[sr][sc] and maze[er][ec] are '.' (i.e., not walls)

   (Of course, since your function is not checking for violations of these conditions, make sure you don't pass bad values to the function when you test it.)

   (Do not leave out the Coord class and do not put it in a separate file.) If you use the library's stack type, your file should include the appropriate header.

2. Given the algorithm, main function, and maze shown at the end of problem 1, what are the first 12 (r,c) coordinates popped off the stack by the algorithm?