QuestionQuestion

Transcribed TextTranscribed Text

2. 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, each '@' represents a bottomless trap hole, 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 nRows – 1 and the column number is in the range 0 through nCols – 1. • The ending coordinates in the maze: er, ec; the row number is in the range 0 through nRows – 1, and the column number is in the range 0 through nCols – 1. 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 or bottomless trap holes; otherwise it must return false. The path may turn north, east, south, and west, but not diagonally. When the function returns, it is allowable for the maze to have been modified by the function. (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.) Here is pseudocode for your function: If the start location is equal to the ending location, then we've solved the maze, so return true. Mark the start location as visted. For each of the four directions, If the location one step in that direction (from the start location) is unvisited, then call pathExists starting from that location (and ending at the same ending location as in Return false. the current call). If that returned true, then return true. (If you wish, you can implement the pseudocode for loop with a series of four if statements instead of a loop.) Here is how a client might use your function: int main() { string maze[10] = { "XXXXXXXXXX", "X.......@X", "XX@X@@.XXX", "X..X.X...X", "X..X...@.X", "X....XXX.X", "X@X....XXX", "X..XX.XX.X", "X...X....X", "XXXXXXXXXX" }; if (pathExists(maze, 10, 10, 6, 4, 1, 1)) cout << "Solvable!" << endl; else cout << "Out of luck!" << endl; return 0; } Because the focus of this homework is on practice with recursion, we won't demand that your function be as robust as we normally would. 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, @s, 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 or bottomless trap holes) (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.) Project 3: The Eyes, They See! Some word games, like Scrabble, require rearranging a combination of letters to make a word. This type of arrangement is generally referred to as an anagram, it's known as a permutation in mathematics. This assignment will give you some experience thinking about and writing recursive functions. Write a C++ program that searches for ``anagrams'' in a dictionary. An anagram is a word obtained by scrambling the letters of some string. For example, the word ``pot'' is an anagram of the string `"otp." A sample run of the program is given below. Your output does not have to be formatted exactly the same as that shown in the sample, but it should be in a similar style. You can use words.txt as your dictionary file and anagram.cpp as an example of a main program. Since the purpose of this assignment is to give you experience using recursion, you may not use any of C++'s iteration constructs (do, while, for, and goto) or any STL algorithms (if you have no idea what this means, you're OK). All repetition must be accomplished using recursion. This applies to every operation in the program, even file operations. Obviously, you would never write a program like this in industry but as an exercise it should be useful to gain experience with recursion. Sample Runs Here are two examples of how the program might work: Please enter a string for an anagram: opt Matching word opt Matching word pot Matching word top Please enter a string for an anagram: blah No matches found Requirements You must write these three functions with the exact same function signature (include case): int dictionaryReader(istream &dictfile, string dict[]); Places each string in dictfile into the array dict. Returns the number of words read into dict. This number should not be larger than MAXDICTWORDS since that is the size of the array. int recurCombos(string word, const string dict[], int size, string results[]); Places all the combinations of word, which are found in dict into results. Returns the number of matched words found. This number should not be larger than MAXRESULTS since that is the size of the array. The size is the number of words inside the dict array. void recursiveDisp(const string results[], int size); Displays size number of strings from results. The results can be printed in any order. For words with double letters you may find that different permutations match the same word in the dictionary. For example, if you find all the permutations of the string kloo using the algorithm we've discussed you may find that the word look is found twice. The o's in kloo take turns in front. Your program should ensure that matches are unique, in other words, the results array returned from the recurCombos function should have no duplicates. A nice way to test this, and your function in general, might be to use the assert facility from the standard library. If done properly the following code should run without a runtime error being generated. string exampleDict[] = {"foster", "the", "people"}; int numResults = recurCombos("softer", exampleDict, 3, results); assert(numResults == 1 && results[0] == "foster"); Again, your solution must not use the keywords while, for, or goto or any STL algorithm functions. You must not use global variables or variables declared with the keyword static, and you must not modify the function parameter lists. You must use the integer constants MAXRESULTS and MAXDICTWORDS, as the declared sizes of your arrays, as in the anagram.cpp example provided to you. Helpful Tips In this project you will also have to deal with one of the drawbacks of using recursive functions. Repeated recursive calls may exhaust the stack space (we will talk about stacks soon) that's been allocated for your program. If you use the sample dictionary file provided, you are almost guaranteed to have a default stack size that is not large enough. Here is how to change the stack size on different platforms: Visual Studio In the Property Pages dialog, in the left panel, select Configuration Properties / Linker / System. In the right panel, select Stack Reserve Size, and in the drop-down list to its right, type in a new stack size (8000000 is approximately 8MB). Click OK. Xcode Click on the Project Name, Select Build Settings at the top then scroll below to find the Linker subsection. Add -Wl,-stack_size,8000000 to the Other Linker Flags field. Linux Run the command ulimit -s 8000 before compiling your program. While completing this assignment you may find it helpful to review file operations and using the substr function. The source file you turn in will contain all the functions and a main routine. You can have the main routine do whatever you want, because we will rename it to something harmless, never call it, and append our own main routine to your file. Our main routine will thoroughly test your functions. You'll probably want your main routine to do the same. If you wish, you may write functions in addition to those required here. We will not directly call any such additional functions.

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

/*
* File:   pathExists.cpp
* Author:
*
*
*/

#include <cstdlib>
#include <iostream>

using namespace std;


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

/*
*
*/
int main(int argc, char** argv) {

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

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$60.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available C-Family Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats