Zip containing all necessary files.

Introduction

This program asks you to "Escape the swamp". It is very similar to the maze problem from last week, but after discussing that program with a few students, I think we can use some reinforcement.

The Assignment

As with the maze, we've got a grid. This time, certain cells are dry spots, while others are swamp-style quick sand. Also marked on the grid is a starting point. Your task is to find a path through the dry spots to any edge of the swamp.

Unlike the maze problem, where the path had to be contiguous, this time, you can jump over a certain number of quicksand cells to the next dry, path cell. This number is the "Jump" paramter specified in the "Jump:" field of the data file.

Specifically, we are asking you to write a program that uses recursion, not iteration, to find your way out of the swamp, given the starting point, swamp map, and jumping ability specified in the data file.

If you can escape, the solve() function should return true, if not false. Furthermore, if you are successful, you should print out the path you took as you escaped the swamp -- each cell upon which you stepped, in the order in which you stepped.

The Challenge

For a challenge, try to escape the swamp in an optimal way -- travelling as little as possible to get out. This isn't required, but is appropriate for anyone who feels comfortable with last week's maze problem.

The Swamp Class

The Swamp Class is the basis of Swamp object. Swamp objects, are basically an adaption of last week's Maze object. Basically, it is very similar to a markable Maze with discontiguous paths.

It uses a two-dimensional array of booleans to model the array. "true" represents paths (dry spots) and "false" represents quicksand. This array is constructed from a data file.

In addition, it uses a separate, mirror of the Swamp for marking purposes. It calls this array, "scratch". Remember, this marking is being used to make sure that we don't retread over dry spots we've already found -- retreading the same ground won't help.

This data file consists of a header that identifies the number of rows, e.g. "Rows: 6", the number of columns, e.g. "Columns: 6", the start cell's (row, column), e.g. "Start: (2,3)", and the amount by which we can jump, e.g. "Jump: 2".

After the header is a list of cells that are part of paths (dry spots as contrasted from quick sand). By default, all cells in a swamp are quicksand. Only those cells that are individually listed as being part of the paths (dry areas) are path cells. The start cell should also be listed as a path cell.

We have provided one sample swamp for you. You should, of course, create many more swamps for testing. The figure below represents is another representation of the swamp within the sample file.

Please click here to view the Swamp class skeleton.

SwampSolver Class

The really interesting part of this assignment is the SwampSolver class. The solve() method of this class calls upon the solve_recursive() method to recursively find the path. The solve() method, through solve_recursive(), should have two results:

• It should return "true", if it succeeded in finding a path out of the swamp, or "false" if it could not find a path (the case where there was no way to jump far enough to get out).
• It should record the correct path in some data structure so that it can be recovered later via the toString() method.

Please note that this method shold only consider cells to be adjacent if they are in the same column or in the same row -- but not diagnal.

Please click here to view the SwampSolver skeleton. If you'd like to see our solution's output for the sample swamp given earlier, we've made our sample output available, too.