## 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[6];
expected[0] = new MazeLocation(0, 1);
expected[1] = new MazeLocation(1, 1);
expected[2] = new MazeLocation(1, 2);
expected[3] = new MazeLocation(1, 3);
expected[4] = new MazeLocation(1, 4);
expected[5] = 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");
}

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.

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[6];

expected[0] = new MazeLocation(0, 1);

expected[1] = new MazeLocation(1, 1);

expected[2] = new MazeLocation(1, 2);

expected[3] = new MazeLocation(1, 3);

expected[4] = new MazeLocation(1, 4) ;

expected[5] = 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 {...