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 standard-issue 5-by-5 boxes are available. Only 2D space will be considered for this problem. Items of various shapes, each no larger than a single 5×5 box, will be given as a set of graphical inputs: number sign (#) for solid object and period (.) for 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 in it.
Note that some items could be “hollow”, and smaller items could fit inside the free space. Also note that even if an item appears disconnected, the rotated pieces must still remain in the same relative positions to each other. Rotations are done by multiples of 90 degrees only, so each item will have at most 4 unique shapes.
The input file DATA5.txt will contain 5 sets of data – the first line of input will be an integer, 1 ≤ n < 30, which is the number of items to follow. Items will be followed by a blank line. Items will be represented by # and . symbols. Sets repeat in such a pattern. Refer to the sample input for the layout.
The output file OUT5.txt will contain 5 lines – the minimum positive integer number of boxes required to fit all of the items.
4
#####
#...#
#...#
#...#
#####
##
##
###.
..#.
..#.
#####
#####
#####
#####
#####
2
.####
#####
##...
##...
##...
###..
###..
###..
.....
....#
2
1