Programming Assignment 1b
Flood Planning, Part 2

Due Date

See the assignment turn-in page (last modified on 16 October 2007) for instructions on turning in your assignment.

Background

A rectangular region of land is divided into 10-meter by 10-meter squares. Each square has a uniform elevation with respect to sea level; adjacent squares may have different elevations. Rain falling on the region flows from higher squares to lower squares unimpeded by intervening terrine (imagine a series of culverts if you like). All rain that lands on the region stays in the region; there is no outflow from the region.

Problem

Given a region description and a volume of rain falling on the region, write a program to determine the water level in the region after the rainfall and how much of the region is flooded. Your program should compute these values efficiently, where “efficiently” means within 10% of the time it takes my solution to compute these values.

Input

Output

If the input is correct, the program should output the water level in meters above or below sea level and the percentage of the region’s area under water, each on a separate line, water level first. Each value should be output with two significant digits.

For example, given the input

3 3
25 37 45
51 12 34
94 83 27
10000

your program should produce the output

46.67
66.67

indicating the water level after rainfall was 46.67 meters above sea level and 66.67% of the squares were underwater. If no rain falls, the water level should be set to the lowest square elevation.

If the input is incorrect, your program should produce output as described in the first assignment. After outputting the error message, your program should stop immediately with no further processing.

Testing

You can use the script gen-input in the assignment directory /export/home/class/cs-305-503/a1b to create testing input for your program. This version of gen-input is different from the version for the first assignment: it doesn’t produce bad output, and it produces larger region descirptions. Your program should still handle bad input, but that’s not the focus of this assignment.

My solution hwm is also available in the assignment directory. Remember the purpose of this assignment is to implement a correct solution, not to copy the behavior of my solution. If my solution’s wrong and you copy the incorrect behavior, you’re going to lose points.

You can use the script time-it in the assignment directory to compare your code’s timings against my solution. The script format is

/export/home/class/cs-305-503/a1b/time-it your-prog

where your-prog is the name of your program for this assignment. time-it writes to std-out a single value which is the ratio of your program’s execution time over my program’s execution time. The value should not be greater than 1.1 (10% slower). time-it runs the version of my program in the assignment directory.