Square Ice

Time limit1sMemory limit128 MB

Summary

Given an alternating sign matrix, render the corresponding square ice grid using H, O, dashes, bars, and an asterisk border.

Level: Medium6 of 10
Topics: Implementation, Matrix, Simulation, Array
Solved: No attempts yet

Problem

Square Ice is a two-dimensional arrangement of water molecules H2O: oxygen atoms (O) sit at the vertices of a square lattice, and exactly one hydrogen atom (H) sits between each pair of adjacent oxygen atoms. Hydrogen atoms may stick out of the left and right sides of the lattice, but never out of the top or bottom. A 5×5 example is shown below.

H-O H-O-H O-H O-H O-H
  |       |   |   |
  H   H   H   H   H
      |
H-O-H O H-O H-O-H O-H
      |   |       |
  H   H   H   H   H
  |           |
H-O H-O-H O-H O H-O-H
          |   |
  H   H   H   H   H
  |   |           |
H-O H-O H-O H-O-H O-H
          |
  H   H   H   H   H
  |   |       |   |
H-O H-O H-O-H O-H O-H

Each hydrogen atom bonds to exactly one of its neighboring oxygen atoms, and each oxygen atom bonds to exactly two of its neighboring hydrogen atoms. (Recall that one water molecule is a single O joined to two H's.)

A square ice arrangement can be encoded by an alternating sign matrix (ASM): a horizontal molecule (H-O-H) is written as 1, a vertical molecule as -1, and every other molecule as 0. The arrangement above is encoded as:

0  1  0  0  0
1 -1  0  1  0
0  1  0 -1  1
0  0  0  1  0
0  0  1  0  0

An ASM is a square matrix whose entries are 0, 1, and -1, in which every row and every column sums to 1, and the nonzero entries in each row and in each column alternate in sign. (There is a one-to-one correspondence between ASMs and square ice arrangements.)

Given an ASM, display its square ice arrangement in the same format as the example above. Use dashes (-) for horizontal bonds and vertical bars (|) for vertical bonds. Surround the whole arrangement with a border of asterisks (*), left-justify it, and place exactly one character — a space, a dash, or a vertical bar — between each pair of neighboring hydrogen (H) and oxygen (O) atoms.

Input

The input consists of several cases. Each case begins with a line containing a positive integer $m$ ( $m \le 11$ ), followed by $m$ lines giving the rows of an ASM. Each line lists one row of the ASM, with entries separated by single spaces. The input ends with a line containing $m = 0$ .

Output

For each case, print the case number (starting from 1) in the form Case k:, then a blank line, then the corresponding square ice arrangement in the format described above. Separate the outputs of different cases by a single blank line.

Examples2

Example 1

Input

Expected output

Case 1:

***********
*H-O H-O-H*
*  |      *
*  H   H  *
*      |  *
*H-O-H O-H*
***********

Case 2:

*******************
*H-O H-O-H O-H O-H*
*  |       |   |  *
*  H   H   H   H  *
*      |          *
*H-O-H O H-O H-O-H*
*      |   |      *
*  H   H   H   H  *
*  |           |  *
*H-O H-O H-O-H O-H*
*      |          *
*  H   H   H   H  *
*  |       |   |  *
*H-O H-O-H O-H O-H*
*******************

Example 2

Input

Expected output

Case 1:

***********************
*H-O H-O-H O-H O-H O-H*
*  |       |   |   |  *
*  H   H   H   H   H  *
*      |              *
*H-O-H O H-O H-O-H O-H*
*      |   |       |  *
*  H   H   H   H   H  *
*  |           |      *
*H-O H-O-H O-H O H-O-H*
*          |   |      *
*  H   H   H   H   H  *
*  |   |           |  *
*H-O H-O H-O H-O-H O-H*
*          |          *
*  H   H   H   H   H  *
*  |   |       |   |  *
*H-O H-O H-O-H O-H O-H*
***********************