Example 6.4

The Unsinkable Ship?

Problem:

The USS Unsinkable, which you were lucky (maybe) enough to get a ticket on, has tragically hit an iceberg. Suddenly the ship is going down, and you must find a way off of the ship, before your escape route is blocked. To make matters worse, there aren't enough lifeboats for all of the passengers.

As you make your way through the corridors (moving north, south, east and west), the boat will continue to flood, blocking sections which were previously usable. To safely make it out of the boat, you must locate a path which does not enter any flooded sections. You also must make it to the lifeboats before they are all filled with other passengers and dispatched into the sea (without you!).

Write a program to determine a route out of the ship, reading in the layout and the current flood situation.

General Info:

  • The lifeboats will fill at the rate of one lifeboat per 2 moves. The first lifeboat boat will fill after the second move.
  • All lifeboats are located in the north west corner of the boat.
  • If a section is bordered (either north, west, south or east) by a flooded section, that section will flood after A turns. The first automatically flooded section will occur after move A and before move A+1.
  • Unflooded spaces adjacent to the newly flooded spaces will flood after A more spaces.
  • You may not move into a section that will flood before the next turn unless it is the section with the lifeboat.
  • You may not enter any section more than once.
  • The map of the boat will have at most 20 columns and 20 rows.
  • People move using Manhattan geometry only -- no diagonal moves.

    Input:

    The first line will indicate how many sinking ships will be entered.
    For each sinking ship:
  • the first line of the input will indicate how many lifeboats exist on the sinking ship
  • the second line will indicate how quickly the sinking ship will flood (A)
  • the third line of input will indicate how many rows make up the sinking ship map (M)
  • the next M lines will indicate the layout of the ship and the flooding situation

    The following letters will appear in the layout:

  • O = Open
  • F = Flooded
  • Y = your starting location

    Output:

    This program will first print Sinking Ship #N where N is the input set (start at 1). Starting on the next line, a map showing the path to the lifeboats (located in the north west corner), starting at your initial location (position 0), and ending at the lifeboats. A final diagram, indicating only the moves should be displayed. All sections which are not entered should be marked with an X. Each section should take up 3 spaces in the final diagram. All numbers and letters should be right justified. If no path exists, this should simply output "No Path Exists.". After printing a path or the message, a blank line should appear. After the last set is run a message, "All Sets Run." should appear.

    Example:

    Input: 
    2
5
3
3
OOOOOF
OOOOFF
OFFYFF
1
1
3
OOF
OFO
FOY

    Output: 

    Sinking Ship #1
     5      4      3      2      X      X
     X      X      X      1      X      X
     X      X      X      0      X      X

Sinking Ship #2
No Path Exists.

All Sets Run.