Project #9 requires you to find an escape path from a given starting point in a
ID: 3813750 • Letter: P
Question
Project #9 requires you to find an escape path from a given starting point in a maze. The maze (or swamp or mine field etc.) is a square 2D array of int. A value of zero in any cell represents a wall (land mine or quicksand etc.) while a value of one represents a possible step to take. Each input file will have a line at the top of the file that has the square dimension of the matrix followed by the drop in point. The drop in point is the row/col pair indicating where you are dropped into the swamp. You escape the swamp by taking one step at a time to any adjacent square that is a 1. You are not allowed to step on a zero cell. You must somehow remember which squares you have already stepped on in a path so that you don't get into an infinite loop. The first input file, swamp0.txt is a simple swamp that has only one path and that path lead directly to the edge of the swamp (escape) with no alternative paths, dead ends or cycles to get caught up ion. If you solve that one you get a 70% for project #8. It is easy to write a solution for swamp0 that does not use recursion. The other 3 input files (swamp1,2 and 3) contain paths that are of incresing complexity containing dead ends and/or cycles. These swamps cannot be easily solved without using recursion.
The starter file that you are given has two methods already written for you. The first given method loads the grid values and generates the 2D int array to hold the 1s and 0s. The second method echo's out the swamp to the screen before calling the method that you must fill in - which will print all the escape paths.
What You'll Need
Here are your input files. You cannot get credit for a higher (more difficult) input file unless your program correctly solves the lower (easier) files.
70% credit: input0.txt 1 simple path out. No dead ends. No cycles
80% credit: input1.txt 1 path out + dead ends. No cycles
90% credit: input2.txt multiple paths + dead ends. No cycles
100% credit: input3.txt multiple paths + dead ends + cycles
Here is what the output should look like for the above inputs:
expectedOutputs.txt
The Assignment
You are given this starter file: Project9.java
Try not to modify main any more than needed.
Do not modify the methods that load or print the grid.
You are just to write and call the method(s) that print all escape paths.
the only output you are to write is one line per escape path and it must be in the exact format as my sample output. If there are no escape paths then your code prints out no additional output.
Your escape path lines may be in a different order than mine but the row,col values must match exactly in matching lines.
Your program must find and print ALL the escape paths. Lines may be in any order though.
Do not print any other output of any kind other than what my solution demo does.
DO NOT PRINT "DEAD END" OR *ANY* OUTPUT IF THERE ARE NO PATHS OUT.
Explanation / Answer
Two-dimensional Arrays
Daniel Shiffman
An array keeps track of multiple pieces of information in linear order, a one-dimensional list. However, the data associ-
ated with certain systems (a digital image, a board game, etc.) lives in two dimensions. To visualize this data, we need a
multi-dimensional data structure, that is, a multi-dimensional array. A two-dimensional array is really nothing more than
an array of arrays (a three-dimensional array is an array of arrays of arrays). Think of your dinner. You could have a
one-dimensional list of everything you eat:
(lettuce, tomatoes, steak, mashed potatoes, cake, ice cream)
Or you could have a two-dimensional list of three courses, each containing two things you eat:
(lettuce, tomatoes) and (steak, mashed potatoes) and (cake, ice cream)
In the case of an array, our old-fashioned one-dimensional array looks like this:
int[] myArray = {0,1,2,3};
And a two-dimensional array looks like this:
int[][] myArray = { {0,1,2,3}, {3,2,1,0}, {3,5,6,1}, {3,8,3,4} };
For our purposes, it is better to think of the two-dimensional array as a matrix. A matrix can be thought of as a grid of
numbers, arranged in rows and columns, kind of like a bingo board. We might write the two-dimensional array out as follows
to illustrate this point:
int[][] myArray = { {0, 1, 2, 3},
{3, 2, 1, 0},
{3, 5, 6, 1},
{3, 8, 3, 4} };
We can use this type of data structure to encode information about an image. For example, the following grayscale image
could be represented by the following array:
int[][] myArray = { {236, 189, 189, 0},
{236, 80, 189, 189},
{236, 0, 189, 80},
{236, 189, 189, 80} };
To walk through every element of a one-dimensional array, we use a for loop, that is:
int[] myArray = new int[10];
for (int i = 0; i < myArray.length; i++) {
myArray[i] = 0;
}
For a two-dimensional array, in order to reference every element, we must use two nested loops. This gives us a counter
variable for every column and every row in the matrix.
int cols = 10;
int rows = 10;
int[][] myArray = new int[cols][rows];
// Two nested loops allow us to visit every spot in a 2D array.
// For every column I, visit every row J.
for (int i = 0; i < cols; i++) {
for (int j = 0; j < rows; j++) {
myArray[i][j] = 0;
}
}
For example, we might write a program using a two-dimensional array to draw a grayscale image.
size(200,200);
int cols = width;
int rows = height;
// Declare 2D array
int[][] myArray = new int[cols][rows];
// Initialize 2D array values
for (int i = 0; i < cols; i++) {
for (int j = 0; j < rows; j++) {
myArray[i][j] = int(random(255));
}
}
// Draw points
for (int i = 0; i < cols; i++) {
for (int j = 0; j < rows; j++) {
stroke(myArray[i][j]);
point(i,j);
}
}
A two-dimensional array can also be used to store objects, which is especially convenient for programming sketches that involve some sort of "grid" or "board." The following example displays a grid of Cell objects stored in a two-dimensional array. Each cell is a rectangle whose brightness oscillates from 0-255 with a sine function.
// 2D Array of objects
Cell[][] grid;
// Number of columns and rows in the grid
int cols = 10;
int rows = 10;
void setup() {
size(200,200);
grid = new Cell[cols][rows];
for (int i = 0; i < cols; i++) {
for (int j = 0; j < rows; j++) {
// Initialize each object
grid[i][j] = new Cell(i*20,j*20,20,20,i+j);
}
}
}
void draw() {
background(0);
// The counter variables i and j are also the column and row numbers and
// are used as arguments to the constructor for each object in the grid.
for (int i = 0; i < cols; i++) {
for (int j = 0; j < rows; j++) {
// Oscillate and display each object
grid[i][j].oscillate();
grid[i][j].display();
}
}
}
// A Cell object
class Cell {
// A cell object knows about its location in the grid
// as well as its size with the variables x,y,w,h
float x,y; // x,y location
float w,h; // width and height
float angle; // angle for oscillating brightness
// Cell Constructor
Cell(float tempX, float tempY, float tempW, float tempH, float tempAngle) {
x = tempX;
y = tempY;
w = tempW;
h = tempH;
angle = tempAngle;
}
// Oscillation means increase angle
void oscillate() {
angle += 0.02;
}
void display() {
stroke(255);
// Color calculated using sine wave
fill(127+127*sin(angle));
rect(x,y,w,h);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.