Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

This problem requires you to find an escape path from a given starting point in a maze. The maze (or swamp or mine field etc.)

This problem 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 five input files you are given have cycles and dead ends and valid paths to the edge of the swamp.

The starter file that you are given has one method already written for you that print the grid out in rectangular format. The second method load the grid from the input file. You must write this method using the printSWamp for clues.

printSwamp is NOT to be called in the code you hand in. It is just for debugging. Remove any calls to it from your handin version.

You are given this starter file: Swamp.java

import java.io.*; import java.util.*;

// DO NOT!! IMPORT JAVA.LANG

public class Swamp { static int[][] swamp; // NOW YOU DON'T HAVE PASS THE REF IN/OUT METHODS

public static void main(String[] args) throws Exception { int[] dropInPt = new int[2]; // row and col will be on the 2nd line of input file; swamp = loadSwamp( args[0], dropInPt ); int row=dropInPt[0], col = dropInPt[1]; String path = ""; // with each step grows to => "[2,3][3,4][3,5][4,6]" etc dfs( row, col, path ); } // END MAIN

// 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 < swamp.length; c++) System.out.print( c + " " ) ; System.out.print( " "); for(int c = 0; c < swamp.length; c++) System.out.print("- "); System.out.print( " ");

for(int r = 0; r < swamp.length; r++) { System.out.print( r + "| "); for(int c = 0; c < swamp[r].length; c++) System.out.print( swamp[r][c] + " "); System.out.println("|"); } System.out.print( " "); for(int c = 0; c < swamp.length; c++) System.out.print("- "); System.out.print( " "); } // --YOU-- WRITE THIS METHOD (LOOK AT PRINTSWAMP FOR CLUES) // ---------------------------------------------------------------- private static int[][] loadSwamp( String infileName, int[] dropInPt ) throws Exception { // OPEN UP A SCANNER USING THE INCOMING FILENAME // THE FIRST NUMBER ON THE FIRST LINE WILL BE THE NUMBER OF ROWS & COLS // THE SECOND & THIRD NUMBER ON 1st LINE WILL BE THE DROP IN POINT X,Y // STORE SEOND NUMBER INTO dropInPt[0] THIRD # INTO dropInPt[1] // USING ROW, COL DEFINE A 2D ARRAY OF INT // USE A NESTED LOOP. OUTER LOOP ROWS, INNER LOOP COLS // READ IN THE GRID OF VALUES FROM THE INPUT FILE // CLOSE THE SCANNER // RETURN THE 2D ARRAY WITH VALUES LOADED INTO IT return null; // JUST TO MAKE IT COMPILE }

static void dfs( int row, int col, String path ) // dfs = DEPTH FIRST SEARCH { // IMPLEMENT THE DFS ALGORITHM IN HERE } }

Input File: Swamp.txt

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
  • Do not modify main any more than needed.
  • Do not modify the given 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. JUST PRINT NOTHING!

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

MySQL Crash Course A Hands On Introduction To Database Development

Authors: Rick Silva

1st Edition

1718503008, 978-1718503007

More Books

Students also viewed these Databases questions