Programming Assignment 3 - Ditch Digging

Advanced Programming II, Fall 2003

Due Date

This assignment is due by 2:00 p.m. on Sunday, 2 November.

See the assignment turn-in page (last modified on 3 November 2003) for instructions on turning in your assignment.

Background

A community garden is laid out as an n x m grid, n and m greater than 1. Individual plots appear at the intersection of interior grid lines; for reasons explained below, there are no plots on the boundary of the garden.

Each winter community members submit requests for individual plots. The community-garden committee assembles the individual requests in to a layout which assigns plots to community members.

To be useful, a layout must be feasible. A layout is feasible if every individual plot can be irrigated according to the following rules:

  1. The four boundaries of the community garden are irrigation ditches.

  2. Each individual plot can have at most one feeder ditch from any one of the boundary irrigation ditches.

  3. Feeder ditches must follow grid lines.

  4. Feeder ditches must not cross each other, and must not pass through other plots.

The Problem

Write a program that determines whether or not a community-garden layout is feasible or not. Your program should read from std-in and write to std-out; errors should go to std-err.

Input

Input consists of a sequence one or more of non-negative integer pairs. Adjacent numbers are separated by at least one space character; a space character is any character for which isspace() is true. The first number may be preceded by, and the last number may be followed by, a sequence of space characters.

The first pair input gives m and n, the size of the community garden. The remaining pairs x and y give individual-plot locations, 0 < x < m and 0 < y < n.

Any input not conforming to this description should be considered invalid input.

Here's an example of valid input: 

5 5
1 2 2 1 2
2 2 3 3
2

Output

If the input is a feasible layout, the output consists of a description of potential feeder ditches for the individual plots. Each description is a single line of text with the following format:

x y d1 d2 ... dn

where x and y are the coordinates of the individual plot and di is one of n, e, s, or w. At least one non-newline space character should separate adjacent output-line elements; a sequence of non-newline space characters may appear before the first or after the last output-line element.

n stands for "north" and represents one step in the positive y direction; s stands for "south" and represents one step in the negative y direction; e stands for "east" and represents one step in the positive x direction; w stands for "west" and represents one step in the negative x direction.

If the input is not a feasible layout, the word infeasible should be written to std-out.

If an error is discovered in input, an informative error message should be written to std-err and the program should end with no further processing.

Testing

I won't be providing any test data for this assignment; you're on your own.

This page last modified on 21 October 2003.