DWITE Online Computer Programming Contest, October 2008, Problem 5

Moving between University (Waterloo) and work (Toronto) every term, has gotten Tony to perfect his Tetris-like skill of packing his stuff into boxes, in the most optimal manner possible. The question now becomes – how many boxes will be required to hold a particular set of things.

Up to 10 of standard-issue ~5 \times 5~ boxes are available. Only 2D space will be considered for this problem. Items of various shapes, each no larger than a single ~5 \times 5~ box, will be given as a set of graphical input – # for solid object, . as free space. Items can be rotated. Free space can overlap and go outside of box boundaries. Each item will have at least 1 solid unit to it.

Note that some items could be "hollow", and smaller items could fit inside free space. Also note that even if the item appears disjointed, the rotated pieces must still remain in the same relative position to each other. Rotations are done by 90 degrees only, so each item will have at most 4 unique shapes.

The input will contain 5 sets of data – first line of input will be an integer, ~1 \le n \le 30~, number of items to follow. Items will be separated by a blank line. Items will be represented by # and .. Sets repeat in such a pattern. Refer to sample input for organization.

The output will contain 5 lines – a minimum positive integer number of boxes required to fit all of the items.

Sample Input

4
#####
#...#
#...#
#...#
#####

##
##

###.
..#.
..#.

#####
#####
#####
#####
#####

2
.####
#####
##...
##...
##...

###..
###..
###..
.....
....#

Sample Output

2
1

Problem Resource: DWITE