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:

10 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

80% credit: input1.txt 1 path out + dead ends. No cycles:

10 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

90% credit: input2.txt multiple paths + dead ends. No cycles:

9 4 4 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0

100% credit: input3.txt multiple paths + dead ends + cycles:

8 1 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0

Here is what the output should look like for the above inputs:

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.

Here is the starter file you must use:

import java.io.*; import java.util.*; // DO NOT!! IMPORT JAVA.LANG public class Swamp { // JUST FOR YOUR DEBUGGING - DELETE THIS METHOD AND ITS CALL BEFORE HANDIN // ---------------------------------------------------------------- private static void printSwamp(String label, int[][] swamp ) { System.out.println( label ); System.out.print(" "); for(int c = 0; c  "[2,3][3,4][3,5][4,6]" etc depthFirstSearch( swamp, row, col, path ); } // END MAIN static void depthFirstSearch( int[][] swamp, int r, int c, String path ) { // IMPLEMENT THE DFS ALGORITHM IN HERE } // END DFS }

Command Prompt C:\Users\tim\Desktop>java Swamp inpute.txt [2,3] [3,3][4,4][5,5][6,6][7,7][8,8117,9] C: \Users\tim\Desktop>java Swamp input1.txt C:\Users\tm\Desktop>java Swamp ?nput2.txt c: \users timlDesktop'java Swamp input3.txt C:\Users tim\Desktop> Command Prompt C:\Users\tim\Desktop>java Swamp inpute.txt [2,3] [3,3][4,4][5,5][6,6][7,7][8,8117,9] C: \Users\tim\Desktop>java Swamp input1.txt C:\Users\tm\Desktop>java Swamp ?nput2.txt c: \users timlDesktop'java Swamp input3.txt C:\Users tim\Desktop>