Rectangular Stamps
Time limit2sMemory limit512 MB
Given up to 16 rectangular stamps of size at most 4x4, find the fewest presses that paint a 4x4 target of red, green, and blue cells, where later stamps fully cover earlier color.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Bit manipulation, Brute force, Implementation
- Solved
- No attempts yet
Problem
Getting good results at the ICPC takes practice. The rabbit wants to win at the ICPC, so it decided to practice again today.
Today's practice is to draw pictures and sharpen its creativity. Let's use square stamps to draw patterns well.
Using stamps of various sizes, we want to complete a picture in the specified red, green, and blue on a 4 × 4 grid of paper. Each stamp is a rectangle, and it is used aligned exactly with the grid. You cannot swap the height and width of a stamp.
The paper starts with no color on it. When you press a stamp onto the paper, the pressed part changes to the stamp's color, and any color hidden underneath becomes completely invisible. The stamp's color is determined by the ink applied, so any stamp can be used with any color you like. A stamp may be pressed so that part of it sticks out past the paper, and the part that sticks out is ignored.
A single stamp may be used multiple times. The same stamp may also be used with different colors. Pressing a stamp takes some care, so we want to press stamps as few times as possible.
Input
N
H1 W1
...
HN WN
C1,1C1,2C1,3C1,4
C2,1C2,2C2,3C2,4
C3,1C3,2C3,3C3,4
C4,1C4,2C4,3C4,4
N is the number of stamps, and H**i, W**i (1 ≤ i ≤ N) are integers giving the height and width of the i-th stamp. C**i, j (1 ≤ i ≤ 4, 1 ≤ j ≤ 4) is the character giving the color specified for the cell in row i from the top and column j from the left. Red is written R, green G, and blue B.
The constraints are 1 ≤ N ≤ 16, 1 ≤ H**i ≤ 4, and 1 ≤ W**i ≤ 4. No pair (H**i, W**i) appears more than once.
Output
Print, on one line, the minimum number of times a stamp must be pressed to complete the picture.