1994 ACM Student Programming Contest

Pacific Region

Problem B: Crossword Puzzle Grid

A crossword puzzle grid is a symmetric N by N grid of
squares with the following properties:

1.  N is odd and greater than 1.

2.  Initially, each grid square contains a blank or an X.

3.  The initial grid has 180-degree rotational symmetry,
    i.e., it remains the same with regard to the blanks and X's
    contained in grid squares after a rotation of 180 degrees
    about its center square.

4.  Ascending positive integers starting with 1 are placed
    in any square which is initially blank and which has any one
    or more of the following characteristics:

     o  the square is in the top row;
     o  the square is in the left column;
     o  the square above it contains an X;
     o  the square to the left of it contains an X.

    Otherwise, a blank square remains so.  Squares which
    initially contain  an X always remain so.

5.  The positive integers (1, 2, 3...) assigned as described
    in (4) are assigned in increasing order across the first
    (top) row, then across the second row, etc., and, finally,
    across the last (bottom) row.

An example puzzle grid is shown below.  Squares containing
X's and blanks are displayed with two such characters.

 -- -- -- -- -- -- -- -- --
| 1| 2| 3|XX|XX| 4| 5| 6|XX|
 -- -- -- -- -- -- -- -- --
| 7|  |  | 8|XX| 9|  |  |10|
 -- -- -- -- -- -- -- -- --
|11|  |  |  |12|  |  |  |  |
 -- -- -- -- -- -- -- -- --
|13|  |  |  |XX|14|  |  |  |
 -- -- -- -- -- -- -- -- --
|XX|XX|15|  |16|  |  |XX|XX|
 -- -- -- -- -- -- -- -- --
|17|18|  |  |XX|19|  |20|21|
 -- -- -- -- -- -- -- -- --
|22|  |  |  |23|  |  |  |  |
 -- -- -- -- -- -- -- -- --
|24|  |  |  |XX|25|  |  |  |
 -- -- -- -- -- -- -- -- --
|XX|26|  |  |XX|XX|27|  |  |
 -- -- -- -- -- -- -- -- --

Your task is to write a program which will create a puzzle
grid from input given as follows.  The first line of input
contains the grid size N as a single integer.  Following
this line are (N+1)/2 lines, each describing one row of the
grid.  (Due to the symmetry of the grid, it is only
necessary to specify the top row down through the center
row; this explains why there are only (N+1)/2 lines
describing grid rows).

Each line which describes a row of the grid consists of one
or more specifiers.  The first specifier begins in column 1,
and adjacent specifiers are separated by a single blank.
Each specifier is the lower case letter 'b' or 'x' followed
by an integer indicating the number of consecutive squares
in the row to be filled initially (left to right) with
blanks or X's respectively.  By default, a row is filled out
with blanks if any columns remain unfilled after the last
specifier for this row.

As an example, the preceding grid was created from the
following input:

9
b3 x2 b3 x1
b4 x1 b4
b1
b4 x1
x2 b5 x2

The input describes a 9 by 9 grid whose first 5 rows contain
the following, left to right:

row 1: 3 blanks, 2X's, 3 blanks, and 1X;
row 2: 4 blanks, 1X, and 4 blanks;
row 3: 9 blanks;
row 4: 4 blanks, 1X, and 4 blanks;
row 5: 2X's, 5 blanks, and 2X's.

You may assume without checking that N <= 15 and that the
largest positive integer required in the grid will not
exceed 99.

The required output is a single grid as described by the
input, with positive integers added as described by the
above rules, following the exact output format shown in the
above example grid.  Each square's interior is two columns
wide and one line high.  The sides of squares are the '|' (a
vertical bar), and the tops and bottoms of squares are '--'
(two hyphens).  The corner of each square is blank:  no
hyphen appears over or under a vertical bar, and no vertical
bar appears beside a hyphen.  Numbers are right-justified
within their squares.