Problem:


H: Rectangular Stamps

ICPC で良い成績を収めるには修行が欠かせない．うさぎは ICPC で勝ちたいので，今日も修行をすることにした．

今日の修行は，絵を描くことによって，創造力を高めようというものである．四角いスタンプを用いて，上手く模様を描こう．

大小さまざまなスタンプを使い，4 &times; 4 のマス目の紙に指定された赤・緑・青の通りの絵を完成させたい．スタンプは長方形であり，マス目にぴったり合わせて使う．スタンプの縦と横を入れ替えることはできない．

紙は最初色が塗られていない状態にある．紙にスタンプを押すと，押された部分がスタンプの色に変わり，下に隠れた色は全く見えなくなる．スタンプの色は付けるインクにより決定されるので，どのスタンプでも，好きな色を選ぶことが可能である．スタンプは紙から一部がはみ出た状態で押すことも可能であり，はみ出た部分は無視される．

1 つのスタンプを複数回使うことは可能である．同じスタンプを別の色に対して使ってもよい．スタンプを押すのはやや神経を使う作業なので，出来るだけスタンプを押す回数を少なくしたい．

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 はスタンプの個数，Hi, Wi (1 ≤ i ≤ N) はそれぞれ，i 番目のスタンプの縦の長さ，横の長さを表す整数である．Ci, j (1 ≤ i ≤ 4，1 ≤ j ≤ 4) は，上から i 行目，左から j 列目のマスについて指定された絵の色を表す文字である．赤は R ，緑は G ，青は B で表される．

1 ≤ N ≤ 16，1 ≤ Hi ≤ 4，1 ≤ Wi ≤ 4 を満たす．(Hi, Wi) として同一の組は複数回現れない．

Output

絵を完成させるためにスタンプを押さなければならない最小の回数を 1 行に出力せよ．

Sample Input 1

2
4 4
1 1
RRRR
RRGR
RBRR
RRRR

Sample Output 1

3

Sample Input 2

1
2 3
RRGG
BRGG
BRRR
BRRR

Sample Output 2

5



Sample input:
2
4 4
1 1
RRRR
RRGR
RBRR
RRRR


Sample output:
3

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
H = W = 4
S = 1 << 16
P = [list(map(int, input().split())) for i in range(N)]
C = [input() for i in range(H)]
I = "RGB".index
ps = set()
for i in range(N):
    h, w = P[i]
    for y in range(1-h, H):
        py = max(0, y); sh = min(H, y+h) - py
        for x in range(1-w, W):
            px = max(0, x); sw = min(W, x+w) - px
            ps.add((px, py, sw, sh))
L = len(ps)
M = [0]*L; V = [None]*L
for l, (x, y, w, h) in enumerate(ps):
    s = S-1; b = 0
    v = [0]*3
    for i in range(h):
        for j in range(w):
            k = 1 << ((y+i)*W + x+j)
            s ^= k
            c = I(C[y+i][x+j])
            v[c] |= k
    M[l] = s
    V[l] = v

U = [-1]*S
que = deque([0])
U[0] = 0
while que:
    state = que.popleft()
    d = U[state]
    for i in range(L):
        n_state = state & M[i]
        for v in V[i]:
            if not v:
                continue
            if U[n_state | v] != -1:
                continue
            U[n_state | v] = d+1
            que.append(n_state | v)
print(U[S-1])

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    from itertools import combinations
    file_input = stdin
    
    N = int(file_input.readline())
    hw = [tuple(map(int, file_input.readline().split())) for i in range(N)]
    goal = (line.rstrip() for line in file_input)
    goal = ''.join(goal)
    
    R = 0
    G = 0
    B = 0
    b = 1
    for c in goal[:]:
        if c == 'R':
            R += b
        elif c == 'G':
            G += b
        else:
            B += b
        b <<= 1
    c_m = (R, G, B) # color mask
    g_m = (1 << 16) - 1 # goal mask
    
    stamps = []
    for r1, r2 in combinations(range(5), 2):
        rw = r2 - r1
        for c1, c2 in combinations(range(5), 2):
            cw = c2 - c1
            for h, w in hw:
                if (rw == h and cw == w) or \
                ((r1 == 0 or r2 == 4) and rw < h and cw == w) or \
                ((c1 == 0 or c2 == 4) and cw < w and rw == h) or \
                ((r1 == 0 or r2 == 4) and (c1 == 0 or c2 == 4) and \
                 rw < h and cw < w):
                    m = 1
                    for i in range(cw - 1):
                        m <<= 1
                        m += 1
                    m <<= c1
                    r_m = m
                    for i in range(rw - 1):
                        m <<= 4
                        m += r_m
                    m <<= (r1 * 4)
                    for c in c_m:
                        s = c & m
                        if s:
                            stamps.append((m ^ g_m, s))
                    break
    
    picture = [0]
    generated_picture = [False] * (2 ** 16)
    generated_picture[0] = True
    step = 0
    while True:
        t_picture = picture[:]
        picture = []
        step += 1
        for p in t_picture:
            for m, s in stamps:
                n_p = p & m | s
                if generated_picture[n_p]:
                    continue
                if n_p == g_m:
                    return step
                generated_picture[n_p] = True
                picture.append(n_p)

print(solve())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n):
        a = [LI() for _ in range(n)]
        b = []
        for _ in range(4):
            b += [c for c in S()]
        s = set()
        ms = 2**16 - 1
        ii = [2**i for i in range(16)]
        for h, w in a:
            for i in range(-h+1, 4):
                for j in range(-w+1, 4):
                    mask = ms
                    for k in range(max(0, i), min(4, i+h)):
                        for l in range(max(0, j), min(4, j+w)):
                            mask -= ii[k*4+l]
                    s.add(mask)
        ta = []
        for mask in s:
            for c in 'RGB':
                t = 0
                for i in range(16):
                    if ii[i] & mask:
                        continue
                    if b[i] == c:
                        t += ii[i]
                if t > 0:
                    ta.append((mask, t))

        v = collections.defaultdict(bool)
        q = set([0])
        r = 0
        while q:
            r += 1
            nq = set()
            for c in q:
                v[c] = True
            for c in q:
                for mask, t in ta:
                    n = (c & mask) + t
                    if v[n]:
                        continue
                    if n == ms:
                        return r
                    nq.add(n)
            q = nq

        return -1

    while 1:
        n = I()
        if n == 0:
            break
        rr.append(f(n))
        break

    return '\n'.join(map(str, rr))


print(main())