Milk Bottle Data
Time Limit: 2 Seconds
Memory Limit: 65536 KB
There is a box of the shape of an N*N lattice. Each grid of the lattice may contain
a milk bottle or none. Mr. Smith wrote down the data of the box by making a record
for each row from left to right and each column from top to bottom. In each record,
'1' indicates that there is a bottle in the corresponding grid and '0' does not.
Unfortunately, the order of these records is thrown into confusion, and some of
these records have corrupted.
Now it's up to you to provide a program to recover these data: i.e. to give
the original arrangement of the box and give real values for those corrupted
First number is N, size of lattice. Records folows, where '2' denotes that the
corresponding character has been corrupted. Each line in the file represents
a record. You should output the original arrangement of the box, and show the
record number for each column on the top of the lattice, and show the record
number for each row to the left of the lattice. After the last lattice is '0'.
You are required to give only one possible result if there are many, and you
should give an indication if there is no possibility of original arrangement.
Do not worry about allignment of output. Our special judge would take care of
9 8 6 2 7
4 1 0 1 1 0
10 1 0 0 1 0
1 0 1 1 1 0
3 0 1 0 0 1
5 1 1 1 0 1
Source: Asia 1996, Shanghai (Mainland China)