 # Path finding Problem description A maze may be represented as a ...

## Question

Show transcribed text

## Transcribed Text

Path finding Problem description A maze may be represented as a two-dimensional array of characters; the “*” the character represents a wall, and a space “ “ represents an open square. One open square on the top wall represents the start square, and one open square on the bottom wall represents the finish square. Finding a path through the maze means finding a path of open squares (where each square is denoted by its row and column) that connect the start and finish squares. (The path usually includes the start and finish squares, too). The only moves allowed on a path from any given square are up, down, left and right (respectively row-1, row+1, column-1, column+1). A maze file is a text file containing all details of a maze but without indicating the path through the maze. In the example that follows (corresponding to maze01.txt) the first three lines indicate that the maze described in the file is 9 rows tall and 11 columns wide; the start square is at row 0, column 1; and the end square is at row 8, column 9. After these first three lines are the details of the maze’s squares. 9 11 0 1 8 9 * ********* * * * *** * *** * * * * * ******* * * * * * * ******* * * * ********* * We could also represent this maze Java as a 2D-array of booleans: The mazes we will consider in this assignment have a single path from start to finish. A path is represented by this sequence of row and column coordinates, such as the following: (0, 1) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (2, 5) (3, 5) (3, 6) (3, 7) (4, 7) (5, 7) (5, 8) (5, 9) (6, 9) (7, 9) (8, 9) This path is represented by the line shown in the following diagram: true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true true false falsefalsefalsefalsefalse falsefalsefalse false false false falsefalsefalse falsefalsefalse false false false falsefalsefalsefalsefalse falsefalsefalse false false falsefalsefalsefalsefalsefalsefalsefalsefalse false 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 When representing such a path, each of the squares is stored as a MazeLocation instance, and the sequence of squares comprising the path can be stored in a MazeLocationList (with is itself made up of MazeLocationListNodes each containing a MazeLocation). In such a list the head node stores information indicating the starting square, and the tail node stores information indicating the ending square. If the list is null, then this can indicate the absence of path. The code for the three classes mention above is provided to you. What you are to do You are to write the code for a class named Maze.java that will be used to find a path through a maze. The code provided in RunSolver will therefore invoke methods on the implementation of Maze that you provide. The class must have the following methods: • A constructor that accepts five parameters: an array of Strings containing details of each maze square, the row and column of the starting square (ints), and the row and column of the finish square (ints). The constructor will also create any other data structures you will need to complete the assignment. The constructor’s signature will be: public Maze(String[] textmaze, int startRow, int startCol, int finishRow, int finishCol) • A public method named solve() that takes no parameter and returns an instance of MazeLocationList. If there is no path through the maze, then 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 solve() returns null. The method solve() will call the recursive method. The signature of solve() must be: public MazeLocationList solve() • A private method named findPath() taking four parameters (starting row and column, finish row and column), returning true if a path is found between the two square and false otherwise. The signature for findPath() must be: private boolean findPath(int fromRow, int fromCol, int toRow, int toCol) • A public method named toString() that will print a representation of the data stored in your instance of Maze. You will use this primarily when developing and debugging your solution. Therefore the output produced by the method must be in some format that helps you understand your own code. (No particular output format is required.) The signature for toString() must be: public String toString() What you are to write 1. Please keep all code within a single directory. We will take advantage of what is called the default package in Java, i.e., all Java files in the same directory are considered to be in the same package. This will permit you to use packageh private access for the assignment without a complex directory structure. 2. Write Maze.java as specified earlier in this assignment description. 3. Use the MazeLocation, MazeLocationList, and MazeLocationListNode files. An implementation of a reference based linked list is also provided for you (MazeLocationListRefBased). 4. As you complete the work for step 2, you must write tests in MazeTester.java. These tests will be in order of increasing difficulty and this order should reflect your implementation strategy. Ideally you will write a test in MazeTester.java before adding relevant implementation code in Maze.java. (An appendix at the end of this assignment description gives an example a test suggesting how you could write such tests.) You must have at least six tests, and none may be equivalent to the five sets of test files. Files to submit (three in total): 1. Maze.java 2. MazeTester.java 3. A file named test_output.txt (which also includes a description of what each test is checking followed by the test input and output) Appendix Example of a test case suitable for MazeTester.java boolean passed = true; String testcase[] = {"* ****", "* *", "**** *"}; Maze maze = new Maze(testcase, 0, 1, 2, 4); MazeLocation expected[] = new MazeLocation; expected = new MazeLocation(0, 1); expected = new MazeLocation(1, 1); expected = new MazeLocation(1, 2); expected = new MazeLocation(1, 3); expected = new MazeLocation(1, 4); expected = new MazeLocation(2, 4); MazeLocationList result = maze.solve(); if (result == null) { passed = false; } else if (result.isEmpty() == true) { passed = false; } else { for (int i = 0; i < result.getLength(); i++) { MazeLocation loc = result.retrieve(i); if (loc.equals(expected[i]) == false) { passed = false; break; } } } if (passed) { System.out.println("Test (horizonal path): passed"); } else { System.out.println("Test (horizonal path): FAILED"); }

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

public class MazeTester {

private static void test1(){
boolean passed = true;
String testcase[] = {"* ****",
"*    *",
"**** *"};
Maze maze = new Maze(testcase, 0, 1, 2, 4);
MazeLocation expected[] = new MazeLocation;
expected = new MazeLocation(0, 1);
expected = new MazeLocation(1, 1);
expected = new MazeLocation(1, 2);
expected = new MazeLocation(1, 3);
expected = new MazeLocation(1, 4) ;
expected = new MazeLocation(2, 4);
MazeLocationList result = maze.solve();
if (result == null) {
passed = false;
} else if (result.isEmpty() == true) {
passed = false;
} else {
for (int i = 0; i < result.getLength(); i++) {
MazeLocation loc = result.retrieve(i);
if (loc.equals(expected[i]) == false) {
passed = false;
break;
}
}
}
if (passed) {
System.out.println("Test (horizonal path): passed");
} else {...

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

\$30.00
for this solution

or FREE if you
register a new account!

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

### Find A Tutor

View available Java 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.