Programming Assignment 1a
Flood Planning, Part 1

CS 305 & 503 - Data Structures & Algorithms,
Fall 2008


Due Date

This assignment is due by 6:00 p.m. on Tuesday, 4 November.

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. 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 how much of the region is flooded. In part 2 of this assignment, your program will calculate the percentage of squares under water. However, for this part of the assignment your program only has to read the input and check it for validity.

Input

The input consists of a sequence of integers read from std-in. The first two numbers read are a pair of non-negative integers x and y giving the region size in 10-meter units. Next follows x*y integers giving the elevation in meters of the squares in row-major order. A negative number indicates the associated square is below sea level. Following the x*y elevations is a non-negative integer indicating the number of cubic meters of rain falling on the region. Anything following the rain-fall volume should be ignored.

For example, the input

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

describes a 3×3 region; the upper-left square in the region (in the north-west corner) is 25 meters above sea level; the lower-right square in the region (the south-east corner) is 27 meters above sea level. 10,000 cubic meters of rain fell on the region.

Output

If the input is correct, the program should produce no output. If the input is incorrect, your program should print an informative error message to std-err and stop. The error message should start with three exclamation points (!!!).

For example, if your program read the input given above, it would produce no output. If your program read the input


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

your program should write an informative error message to std-err, such as

!!! Rainfall should be a non-negative integer, not -10000.

Testing

You can use the program gen-input in the assignment directory /export/home/class/cs-305-503/a1a to create testing input for your program. When run, gen-input writes the output to std-out. By default, the output is randomly chosen to be either good or bad. The command-line argument g or G always generations good input; the b or B argument always generates bad input.

Because gen-input generates different input each time it's run, you'll probably want to capture the output so you can reliably repeat input for your program when debugging. For example, if your program is called hwm, you might do:

$ /export/home/class/cs-305-503/a1a/gen-input > inp

$ ./hwm < inp

$

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.


This page last modified on 2 November 2008.

Creative
    Commons License