Problem:


ジグソーパズル

子供から大人まで脳トレ系パズルゲームが流行しています。我々も遅れを取らぬよう、パズルゲームを作ってみんなで遊ぶことにしました。

  我々が考えたのはジグソーパズルのゲームで、未完成の部分を埋めるのに必要なピースを選ぶというものです。図 1 (a) はパズルの枠の例です。黒が埋まっている部分、白が未完成の部分です。このパズルを完成するのに使えるピースが図 1 (b) のように与えられます。この中から、枠の白い部分を埋めることができる黒いピースを 1 つ以上選択します。例えば、図 2 の選択例 1 のような組み合わせなら正解となります。一方、選択例 2 のような組み合わせではパズルは完成しないので不正解となります。また、選択したピースが余ってしまう場合も不正解です。このように、プレイヤーは適切なピースを選択することでゲームをクリアします。

  そこでこのパズルゲームで用いる判定プログラムを開発することになりました。未完成のパズル、ピースの候補、そしてプレイヤーが選んだピースの組み合わせを入力とし、プレイヤーが適切なピースを選ぶことができていれば YES を、そうでなければ NO と出力するプログラムを作成してください。

  この問題では、パズルの枠は H &times; W の配列で表し、未完成の部分を . (半角ピリオド)、完成している部分を # (半角シャープ)によって与えます。パズルの枠の大きさは最大 20 &times; 20 とします。また、各ピースは h &times; w の配列で表し、ピースを構成する部分を # 、そうでない部分を . によって与えます。与えられる各ピースは、元の状態から 90 度、180 度、270 度だけ回転することができます。また、各ピースの大きさは最大 20 &times; 20 とし、与えられるピースの数 n は最大 10 とします。

Input

複数のデータセットが与えられます。各データセットは以下の形式で与えられます。

H W
g1,1g1,2...g1,W
g2,1g2,2...g2,W
:
gH,1gH,2...gH,W
n
h1 w1
c11,1c11,2...c11,w1
c12,1c12,2...c12,w1
:
c1h1,1c1h1,2...c1h1,w1
:
:
hn wn
cn1,1cn1,2...cn1,wn
cn2,1cn2,2...cn2,wn
:
cnhn,1cnhn,2...cnhn,wn
p
k1 t1 t2 ... tk1
k2 t1 t2 ... tk2
:
kp t1 t2 ... tkp

1 行目に、パズルの枠の大きさ H(縦) と W(横) が与えられます。
2 行目に、文字 gi,j (.  または #) からなりパズルの盤面を表す 1 行 W 文字の文字列が H 行与えられます。

続いてピースの数 n、n 個のピースの情報が与えられます。各ピースの情報として、l 番目のピースの配列のサイズ hl (縦) と wl (横)、l 番目のピースの配列が与えられます。l 番目のピースの配列として文字 cli,j (. または #) からなる 1 行 wl 文字の文字列が hl 行与えられます。

続いてプレイヤーの人数 p、i 番目のプレイヤーの選択したピースの数 ki と選択したピースの番号 tj が与えられます。

入力は２つの 0 を含む行で終了します。データセットの数は 10 を超えません。

Output

各データセットごとに、i 番目のプレイヤーが選択したピースの正否 YES または NO を i 行目に出力してください。

Sample Input

14 20
####################
###.............####
####..........######
#######.....########
########.....#######
###..###......######
###..####......#####
#########......#####
###########.....####
############.....###
###.########......##
###.#######...###.##
##...###....#####.##
####################
10
12 15
#############..
.##########....
....#####......
.....#####.....
.....######....
......######...
......######...
........#####..
.........#####.
.........######
........###...#
.....####.....#
3 3
#..
###
#..
2 2
##
##
4 10
....#####.
....######
...###...#
####.....#
6 5
....#
..###
#####
##.##
#..##
#..#.
6 4
...#
.###
####
##.#
##.#
#...
2 6
######
.#####
2 7
..#####
#######
2 13
#############
.##########..
6 9
#####....
.######..
.######..
..######.
...#####.
....#####
8
3 1 2 3
4 1 2 3 4
7 2 3 4 5 6 7 8
5 2 3 10 7 8
6 2 3 9 5 6 4
8 2 3 4 6 9 5 4 10
4 4 5 6 9
5 10 2 3 4 9
0 0

Output for the Sample Input

YES
NO
YES
NO
YES
NO
NO
YES



Sample input:
14 20
####################
###.............####
####..........######
#######.....########
########.....#######
###..###......######
###..####......#####
#########......#####
###########.....####
############.....###
###.########......##
###.#######...###.##
##...###....#####.##
####################
10
12 15
#############..
.##########....
....#####......
.....#####.....
.....######....
......######...
......######...
........#####..
.........#####.
.........######
........###...#
.....####.....#
3 3
#..
###
#..
2 2
##
##
4 10
....#####.
....######
...###...#
####.....#
6 5
....#
..###
#####
##.##
#..##
#..#.
6 4
...#
.###
####
##.#
##.#
#...
2 6
######
.#####
2 7
..#####
#######
2 13
#############
.##########..
6 9
#####....
.######..
.######..
..######.
...#####.
....#####
8
3 1 2 3
4 1 2 3 4
7 2 3 4 5 6 7 8
5 2 3 10 7 8
6 2 3 9 5 6 4
8 2 3 4 6 9 5 4 10
4 4 5 6 9
5 10 2 3 4 9
0 0


Sample output:
YES
NO
YES
NO
YES
NO
NO
YES

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
cost_table = [[] for _ in xrange(20*20*10)]
ANS_SET = {}
table = {}

def BFS(visited):#mark island num
    W,H = len(visited[0]),len(visited)
    D = zip([0,1,0,-1], [-1,0,1,0])
    for x in xrange(W):
        for y in (y for y in xrange(H) if not visited[y][x]):
            q,top  = [(x,y)], 0
            while len(q) > top:
                cx,cy = q[top]
                top += 1
                f = lambda d:(cx+d[0],cy+d[1])
                for nx,ny in map(f,D):
                    if (0<=nx<W and 0<=ny<H) and not visited[ny][nx]:
                        q.append((nx,ny))
                        visited[ny][nx] = True
            yield q

def divided(field):
    W,H = len(field[0]),len(field)
    visited = [[field[y][x]=="#" for x in xrange(W)]
               for y in xrange(H)]    
    return sorted([put(pos) for pos in BFS(visited)],
                  key = lambda a:sum(aa.count(".") for aa in a))#sort by sum of "."

def put(pos):
    x,y = zip(*pos)
    min_x, max_x = min(x), max(x)
    min_y, max_y = min(y), max(y)
    W = max_x - min_x + 1
    H = max_y - min_y + 1
    ret = [["#"]*W for _ in xrange(H)]
    for x in xrange(W):
        for y in xrange(H):
            if (x+min_x, y+min_y) in pos:
                ret[y][x] = "."
    return ["".join(r) for r in ret]

def can_add(field,piece,pos):
    sx,sy = pos
    W,H = len(field[0]),len(field)
    pw,ph = len(piece[0]),len(piece)
    for x in xrange(pw):
        for y in (y for y in xrange(ph) if piece[y][x]=="#"):
            if not(0<=sx+x<W and 0<=sy+y<H) or field[sy+y][sx+x] == "#":
                return False
    return True

def added(field,piece,pos):
    ret = [list(f) for f in field]
    sx,sy = pos
    W,H = len(field[0]),len(field)
    pw,ph = len(piece[0]),len(piece)
    for x in xrange(pw):
        for y in (y for y in xrange(ph) if piece[y][x]=="#"):
            ret[sy+y][sx+x] = "#"
    return ["".join(r) for r in ret]

def rotated(p):
    _90 = ["".join(pp)[::-1] for pp in zip(*p)]
    _180 = [pp[::-1] for pp in p[::-1]]
    _270 = ["".join(pp) for pp in zip(*p)[::-1]]
    return [p,_90,_180,_270]

def get_empty(field):
    return sum(f.count(".") for f in field)

def memoize(f):
    global table
    def func(*args):
        key = tuple(map(tuple,args))
        if not key in table:
            table[key]=f(*args)
        return table[key]
    return func

@memoize
def DFS(field,pieces,open_list):
    W,H = len(field[0]),len(field)
    #print "OPEN_LIST:",open_list
    #print_field(field)
    if len(open_list) == 1:        
        for p in rotated(pieces[open_list[0]]):
            for x in xrange(W):
                for y in (y for y in xrange(H) if can_add(field,p,(x,y))):
                    return True
        return False

    p = pieces[open_list[0]]
    for p in rotated(pieces[open_list[0]]):
        for x in xrange(W):
            for y in (y for y in xrange(H) if can_add(field,p,(x,y))):
                divided_fields = divided(added(field,p,(x,y)))
                for ols in find(divided_fields,open_list[1:]):
                    if all(DFS(f,pieces,ol) for f,ol in zip(divided_fields,ols)):
                            return True
    return False

def print_field(field):
    print "\n".join(field)

def init_DFS(field,pieces,open_list):
    global ANS_SET
    divided_fields = divided(field)
    #print "\n\n".join("\n".join(df) for df in divided_fields)
    for ols in find(divided_fields,open_list):
        tmp = tuple(sorted(reduce(lambda a,b:a+b,ols)))
        if tmp not in ANS_SET or ANS_SET[tmp] == False:
            ANS_SET[tmp] = all(DFS(f,pieces,sorted(ol,key=lambda a:len(pieces[a])*len(pieces[a][0]),
                                                   reverse = True)) for f,ol in zip(divided_fields,ols))
def fill_cost_table(pieces):
    global cost_table
    N = len(pieces)
    costs = [sum(pp.count("#") for pp in p) for p in pieces]
    for r in xrange(1,N+1):
        for p in combinations(range(N),r):
            cost_table[sum(costs[i] for i in p)].append(p)

def find(fields,open_list):
    if len(fields)==0 and len(open_list)==0:
        yield []
    elif len(fields)==0 or len(open_list)==0:
        pass
    else:
        empty = get_empty(fields[0])
        for indices in cost_table[empty]:
            if any(i not in open_list for i in indices):
                continue
            for f in find(fields[1:],list(set(open_list)-set(indices))):
                yield [indices] + f

while True:
    H, W = map(int,raw_input().split())
    if (H,W) == (0,0):
        break
    cost_table = [[] for _ in xrange(20*20*10)]
    ANS_SET = {}
    field = [raw_input() for _ in xrange(H)]
    pieces =tuple([tuple([raw_input() for _ in xrange(map(int,raw_input().split())[0])])
              for _ in xrange(input())])
    #print "\n\n".join("\n".join(p) for p in pieces)
    fill_cost_table(pieces)
    #print ANS_SET
    for _ in xrange(input()):
        num = tuple(sorted(map(lambda a:int(a)-1,raw_input().split())[1:]))
        init_DFS(field,pieces,num)
        if num in ANS_SET:
            print "YES" if ANS_SET[num] else "NO"
        else:
            print "NO"

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
cost_table = [[] for _ in xrange(20*20*10)]
ANS_SET = {}
table = {}

def BFS(visited):#mark island num
    W,H = len(visited[0]),len(visited)
    D = zip([0,1,0,-1], [-1,0,1,0])
    for x in xrange(W):
        for y in (y for y in xrange(H) if not visited[y][x]):
            q,top  = [(x,y)], 0
            while len(q) > top:
                cx,cy = q[top]
                top += 1
                f = lambda d:(cx+d[0],cy+d[1])
                for nx,ny in map(f,D):
                    if (0<=nx<W and 0<=ny<H) and not visited[ny][nx]:
                        q.append((nx,ny))
                        visited[ny][nx] = True
            yield q

def divided(field):
    W,H = len(field[0]),len(field)
    visited = [[field[y][x]=="#" for x in xrange(W)]
               for y in xrange(H)]    
    return sorted([put(pos) for pos in BFS(visited)],
                  key = lambda a:sum(aa.count(".") for aa in a))#sort by sum of "."

def put(pos):
    x,y = zip(*pos)
    min_x, max_x = min(x), max(x)
    min_y, max_y = min(y), max(y)
    W = max_x - min_x + 1
    H = max_y - min_y + 1
    ret = [["#"]*W for _ in xrange(H)]
    for x in xrange(W):
        for y in xrange(H):
            if (x+min_x, y+min_y) in pos:
                ret[y][x] = "."
    return ["".join(r) for r in ret]

def can_add(field,piece,pos):
    sx,sy = pos
    W,H = len(field[0]),len(field)
    pw,ph = len(piece[0]),len(piece)
    for x in xrange(pw):
        for y in (y for y in xrange(ph) if piece[y][x]=="#"):
            if not(0<=sx+x<W and 0<=sy+y<H) or field[sy+y][sx+x] == "#":
                return False
    return True

def added(field,piece,pos):
    ret = [list(f) for f in field]
    sx,sy = pos
    W,H = len(field[0]),len(field)
    pw,ph = len(piece[0]),len(piece)
    for x in xrange(pw):
        for y in (y for y in xrange(ph) if piece[y][x]=="#"):
            ret[sy+y][sx+x] = "#"
    return ["".join(r) for r in ret]

def rotated(p):
    _90 = ["".join(pp)[::-1] for pp in zip(*p)]
    _180 = [pp[::-1] for pp in p[::-1]]
    _270 = ["".join(pp) for pp in zip(*p)[::-1]]
    return [p,_90,_180,_270]

def get_empty(field):
    return sum(f.count(".") for f in field)

def memoize(f):
    global table
    def func(*args):
        key = tuple(map(tuple,args))#tmp
        if not key in table:
            table[key]=f(*args)
        return table[key]
    return func

@memoize
def DFS(field,pieces,open_list):
    W,H = len(field[0]),len(field)
    #print "OPEN_LIST:",open_list
    #print_field(field)
    if len(open_list) == 1:        
        for p in rotated(pieces[open_list[0]]):
            for x in xrange(W):
                for y in (y for y in xrange(H) if can_add(field,p,(x,y))):     
                    return True
        return False

    p = pieces[open_list[0]]
    for p in rotated(pieces[open_list[0]]):
        for x in xrange(W):
            for y in (y for y in xrange(H) if can_add(field,p,(x,y))):
                divided_fields = divided(added(field,p,(x,y)))
                for ols in find(divided_fields,open_list[1:]):
                    if all(DFS(f,pieces,ol) for f,ol in zip(divided_fields,ols)):
                            return True
    return False

def print_field(field):
    print "\n".join(field)

@memoize
def init_DFS(field,pieces,open_list):
    global ANS_SET
    divided_fields = divided(field)
    #print "\n\n".join("\n".join(df) for df in divided_fields)
    for ols in find(divided_fields,open_list):
        if all(DFS(f,pieces,sorted(ol,key=lambda a:len(pieces[a])*len(pieces[a][0]),
                                   reverse = True)) for f,ol in zip(divided_fields,ols)) == True:
            return True
    return False
def fill_cost_table(pieces):
    global cost_table
    N = len(pieces)
    costs = [sum(pp.count("#") for pp in p) for p in pieces]
    for r in xrange(1,N+1):
        for p in combinations(range(N),r):
            cost_table[sum(costs[i] for i in p)].append(p)

def find(fields,open_list):
    if len(fields)==0 and len(open_list)==0:
        yield []
    elif len(fields)==0 or len(open_list)==0:
        pass
    else:
        empty = get_empty(fields[0])
        for indices in cost_table[empty]:
            if any(i not in open_list for i in indices):
                continue
            for f in find(fields[1:],list(set(open_list)-set(indices))):
                yield [indices] + f

while True:
    H, W = map(int,raw_input().split())
    if (H,W) == (0,0):
        break
    cost_table = [[] for _ in xrange(20*20*10)]
    ANS_SET = {}
    field = [raw_input() for _ in xrange(H)]
    pieces =tuple([tuple([raw_input() for _ in xrange(map(int,raw_input().split())[0])])
              for _ in xrange(input())])
    #print "\n\n".join("\n".join(p) for p in pieces)
    fill_cost_table(pieces)
    #print ANS_SET
    for _ in xrange(input()):
        num = tuple(sorted(map(lambda a:int(a)-1,raw_input().split())[1:]))                
        print "YES" if init_DFS(field,pieces,num) else "NO"

Submission status: Runtime Error

Solution code:
import copy
def rot90(A):
#Aを時計方向に90度回転させる
  return zip(*A[::-1])

def count_board(Board):
#X[x][y]: [x,y]から[Width-1,Height-1]にあるドット数のテーブルを作る
  X = [[0 for _ in [0]*(Width+1)] for _ in [0]*(Height+1)]
  for i in range(Height)[::-1]:
    for j in range(Width)[::-1]:
      X[i][j] = X[i+1][j] + X[i][j+1] - X[i+1][j+1] + (Board[i][j]=='.')
  return X

def check_sum(TRIALS):
  return sum([B[e] for e in TRIALS]) != DOTS[0][0]

def get_POS(n, mode, DOTS):
#n番ピースを置ける場所の洗い出し
#ピースの向き
#mode=0: 通常, mode=1: 90度回転
  P0 = PIECE[(n, mode)]
  P2 = PIECE[(n, mode+2)]
  h = len(P0)
  w = len(P0[0])
  s = B[n]
  POS=[]
  for i in range(Height-h+1):
    for j in range(Width-w+1):
      tmp = DOTS[i][j] - DOTS[i+h][j] \
            - DOTS[i][j+w] + DOTS[i+h][j+w]
      if tmp>=s:
        if tmp_put(P0, i, j): POS.append([i, j, mode])
        elif tmp_put(P2, i, j): POS.append([i, j, mode+2])
  return POS

def tmp_put(piece,y,x):
  #ピースを枠の[x,y]に置けるかチェック
  #戻り値: OK=1, NG=0
  for i in range(len(piece)):
    for j in range(len(piece[0])):
      if piece[i][j]=='#' and Board[y+i][x+j]!='.': return 0
  return 1

def get_put(Board, piece, y, x, mode):
  #mode=0: ピースを枠の[x,y]に置く
  #mode=1: ピースを枠の[x,y]から取る
  #戻り値: OK=1, NG=0
  c = '#.'[mode]
  for i in range(len(piece)):
    for j in range(len(piece[0])):
      if piece[i][j]=='#': Board[y+i][x+j]=c
  return Board

def solve(TRIALS, Board):
  if TRIALS==[]: return 1
  e = TRIALS[0]
  POS = get_POS(e, 0, DOTS) + get_POS(e, 1, DOTS)
  for pos in POS:
    y, x, direction = pos
    Board = get_put(Board, PIECE[(e, direction)], y, x, 0)
    tmp = TRIALS[:]
    del tmp[0]
    if solve(tmp, Board): return 1
    Board = get_put(Board, PIECE[(e, direction)], y, x, 1)
  return 0

#パズル枠データの設定
Height, Width = map(int,raw_input().split())
Board = [list(raw_input()) for i in range(Height)]
DOTS = count_board(Board)

#ピースデータの設定
PIECE = {}
n = input()
B = [0]*n
for i in range(n):
  height, width = map(int,raw_input().split())
  piece = [list(raw_input()) for _ in [0]*height]
  B[i] = sum([e.count("#") for e in piece])
  for direction in [0,1,2,3]:
    PIECE[(i, direction)] = piece
    piece = rot90(piece)
          
for _ in [0]*input():
  #試すピースデータを設定し，ピースの面積と枠の面積の一致を確認
  #ピースを面積の広い順にソート
  a = map(int, raw_input().split())[1:]
  a = sorted([[B[e-1], e-1] for e in a], key=lambda x:[-x[0]])
  TRIALS = list(zip(*a)[1])
  if check_sum(TRIALS): print "NO"; continue 
  #面積が同じならパズルを解く
  print ["NO", "YES"][solve(TRIALS, copy.deepcopy(Board))]

Submission status: Runtime Error

Solution code:
def rot90(A):
  return zip(*A[::-1])

def count_board(Board):
  X = [[0 for _ in [0]*(Width+1)] for _ in [0]*(Height+1)]
  for i in range(Height)[::-1]:
    for j in range(Width)[::-1]:
      X[i][j] = X[i+1][j] + X[i][j+1] - X[i+1][j+1] + (Board[i][j]=='.')
  return X

def check_sum(TRIALS):
  return sum([B[e] for e in TRIALS]) != DOTS[0][0]

def get_POS(Board, n, mode, DOTS):
  P0 = PIECE[(n, mode)]
  P2 = PIECE[(n, mode+2)]
  h = len(P0)
  w = len(P0[0])
  s = B[n]
  POS=[]
  for i in range(Height-h+1):
    for j in range(Width-w+1):
      tmp = DOTS[i][j] - DOTS[i+h][j] \
            - DOTS[i][j+w] + DOTS[i+h][j+w]
      if tmp>=s:
        if tmp_put(Board, P0, i, j): POS.append([i, j, mode])
        elif tmp_put(Board, P2, i, j): POS.append([i, j, mode+2])
  return POS

def tmp_put(Board, piece, y, x):
  for i in range(len(piece)):
    for j in range(len(piece[0])):
      if piece[i][j]=='#' and Board[y+i][x+j]!='.': return 0
  return 1

def get_put(Board, piece, y, x, mode):
  c = '#.'[mode]
  for i in range(len(piece)):
    for j in range(len(piece[0])):
      if piece[i][j]=='#': Board[y+i][x+j]=c
  return Board

def PrintBoard(Board):
  for e in Board:
    print "".join(e)
  print
  return

def PrintDots(DOTS):
  for e in DOTS:
    print e
  print
  return

def solve(TRIALS, Board):
  if TRIALS==[]: return 1
  e = TRIALS[0]
  DOTS = count_board(Board)
  POS = get_POS(Board, e, 0, DOTS) + get_POS(Board, e, 1, DOTS)
  i=0
  for pos in POS:
    i=i+1    
    y, x, direction = pos
    Board = get_put(copy.deepcopy(Board), PIECE[(e, direction)], y, x, 0)
    tmp = TRIALS[:]
    del tmp[0]
    if solve(tmp, copy.deepcopy(Board)): return 1
    Board = get_put(copy.deepcopy(Board), PIECE[(e, direction)], y, x, 1)
  return 0

Height, Width = map(int,raw_input().split())
Board = [list(raw_input()) for i in range(Height)]
DOTS = count_board(Board)

PIECE = {}
n = input()
B = [0]*n
for i in range(n):
  height, width = map(int,raw_input().split())
  piece = [list(raw_input()) for _ in [0]*height]
  B[i] = sum([e.count("#") for e in piece])
  for direction in [0,1,2,3]:
    PIECE[(i, direction)] = piece
    piece = rot90(piece)
          
for _ in [0]*input():
  a = map(int, raw_input().split())[1:]
  a = sorted([[B[e-1], e-1] for e in a], key=lambda x:[-x[0]])
  TRIALS = list(zip(*a)[1])
  if check_sum(TRIALS): print "NO"; continue 
  print ["NO", "YES"][solve(TRIALS, Board[:])]

Submission status: Runtime Error

Solution code:
import copy
def rot90(A):
  return zip(*A[::-1])

def count_board(Board):
  X = [[0 for _ in [0]*(Width+1)] for _ in [0]*(Height+1)]
  for i in range(Height)[::-1]:
    for j in range(Width)[::-1]:
      X[i][j] = X[i+1][j] + X[i][j+1] - X[i+1][j+1] + (Board[i][j]=='.')
  return X

def check_sum(TRIALS):
  return sum([B[e] for e in TRIALS]) != DOTS[0][0]

def get_POS(Board, n, mode, DOTS):
  P0 = PIECE[(n, mode)]
  P2 = PIECE[(n, mode+2)]
  h = len(P0)
  w = len(P0[0])
  s = B[n]
  POS=[]
  for i in range(Height-h+1):
    for j in range(Width-w+1):
      tmp = DOTS[i][j] - DOTS[i+h][j] \
            - DOTS[i][j+w] + DOTS[i+h][j+w]
      if tmp>=s:
        if tmp_put(Board, P0, i, j): POS.append([i, j, mode])
        elif tmp_put(Board, P2, i, j): POS.append([i, j, mode+2])
  return POS

def tmp_put(Board, piece, y, x):
  for i in range(len(piece)):
    for j in range(len(piece[0])):
      if piece[i][j]=='#' and Board[y+i][x+j]!='.': return 0
  return 1

def get_put(Board, piece, y, x, mode):
  c = '#.'[mode]
  for i in range(len(piece)):
    for j in range(len(piece[0])):
      if piece[i][j]=='#': Board[y+i][x+j]=c
  return Board

def PrintBoard(Board):
  for e in Board:
    print "".join(e)
  print
  return

def PrintDots(DOTS):
  for e in DOTS:
    print e
  print
  return

def solve(TRIALS, Board):
  if TRIALS==[]: return 1
  e = TRIALS[0]
  DOTS = count_board(Board)
  POS = get_POS(Board, e, 0, DOTS) + get_POS(Board, e, 1, DOTS)
  i=0
  for pos in POS:
    i=i+1   
    y, x, direction = pos
    Board = get_put(Board, PIECE[(e, direction)], y, x, 0)
    tmp = TRIALS[:]
    del tmp[0]
    if solve(tmp, Board): return 1
    Board = get_put(Board, PIECE[(e, direction)], y, x, 1)
  return 0

while 1:
  Height, Width = map(int,raw_input().split())
  if Height==Width==0: break
  Board = [list(raw_input()) for i in range(Height)]
  DOTS = count_board(Board)

  PIECE = {}
  n = input()
  B = [0]*n
  for i in range(n):
    height, width = map(int,raw_input().split())
    piece = [list(raw_input()) for _ in [0]*height]
    B[i] = sum([e.count("#") for e in piece])
    for direction in [0,1,2,3]:
      PIECE[(i, direction)] = piece
      piece = rot90(piece)

  for _ in [0]*input():
    a = map(int, raw_input().split())[1:]
    a = sorted([[B[e-1], e-1] for e in a], key=lambda x:[-x[0]])
    TRIALS = list(zip(*a)[1])
    if check_sum(TRIALS): print "NO"; continue
    print ["NO", "YES"][solve(TRIALS, copy.deepcopy(Board))]

Submission status: Runtime Error

Solution code:
import copy
def rot90(A):
  return zip(*A[::-1])

def count_board(Board):
  X = [[0 for _ in [0]*(Width+1)] for _ in [0]*(Height+1)]
  for i in range(Height)[::-1]:
    for j in range(Width)[::-1]:
      X[i][j] = X[i+1][j] + X[i][j+1] - X[i+1][j+1] + (Board[i][j]=='.')
  return X

def check_sum(TRIALS):
  return sum([B[e] for e in TRIALS]) != DOTS[0][0]

def get_POS(Board, n, mode, DOTS):
  P0 = PIECE[(n, mode)]
  P2 = PIECE[(n, mode+2)]
  h = len(P0)
  w = len(P0[0])
  s = B[n]
  POS=[]
  for i in range(Height-h+1):
    for j in range(Width-w+1):
      tmp = DOTS[i][j] - DOTS[i+h][j] \
            - DOTS[i][j+w] + DOTS[i+h][j+w]
      if tmp>=s:
        if tmp_put(Board, P0, i, j): POS.append([i, j, mode])
        elif tmp_put(Board, P2, i, j): POS.append([i, j, mode+2])
  return POS

def tmp_put(Board, piece, y, x):
  for i in range(len(piece)):
    for j in range(len(piece[0])):
      if piece[i][j]=='#' and Board[y+i][x+j]!='.': return 0
  return 1

def get_put(Board, piece, y, x, mode):
  c = '#.'[mode]
  for i in range(len(piece)):
    for j in range(len(piece[0])):
      if piece[i][j]=='#': Board[y+i][x+j]=c
  return Board

def PrintBoard(Board):
  for e in Board:
    print "".join(e)
  print
  return

def PrintDots(DOTS):
  for e in DOTS:
    print e
  print
  return

def solve(TRIALS, Board):
  if TRIALS==[]: return 1
  e = TRIALS[0]
  DOTS = count_board(Board)
  POS = get_POS(Board, e, 0, DOTS) + get_POS(Board, e, 1, DOTS)
  i=0
  for pos in POS:
    i=i+1   
    y, x, direction = pos
    Board1 = get_put(copy.deepcopy(Board), PIECE[(e, direction)], y, x, 0)
    tmp = TRIALS[:]
    del tmp[0]
    if solve(tmp, Board1): return 1
  return 0

while 1:
  Height, Width = map(int,raw_input().split())
  if Height==Width==0: break
  Board = [list(raw_input()) for i in range(Height)]
  DOTS = count_board(Board)

  PIECE = {}
  n = input()
  B = [0]*n
  for i in range(n):
    height, width = map(int,raw_input().split())
    piece = [list(raw_input()) for _ in [0]*height]
    B[i] = sum([e.count("#") for e in piece])
    for direction in [0,1,2,3]:
      PIECE[(i, direction)] = piece
      piece = rot90(piece)

  for _ in [0]*input():
    a = map(int, raw_input().split())[1:]
    a = sorted([[B[e-1], e-1] for e in a], key=lambda x:[-x[0]])
    TRIALS = list(zip(*a)[1])
    if check_sum(TRIALS): print "NO"; continue
    print ["NO", "YES"][solve(TRIALS, copy.deepcopy(Board))]

Submission status: Runtime Error

Solution code:
import copy
def rot90(A):
  return zip(*A[::-1])

def count_board(Board):
  X = [[0 for _ in [0]*(Width+1)] for _ in [0]*(Height+1)]
  for i in range(Height)[::-1]:
    for j in range(Width)[::-1]:
      X[i][j] = X[i+1][j] + X[i][j+1] - X[i+1][j+1] + (Board[i][j]=='.')
  return X

def check_sum(TRIALS):
  return sum([B[e] for e in TRIALS]) != DOTS[0][0]

def tmp_put(Board, piece, y, x):
  for i in range(len(piece)):
    tmp = piece[i]
    BoardRow = Board[y+i]
    for j in range(len(piece[0])):
      if tmp[j]=='#' and BoardRow[x+j]!='.': return 0
  return 1

def get_put(Board, piece, y, x, mode):
  c = '#.'[mode]
  for i in range(len(piece)):
    tmp = piece[i]
    for j in range(len(piece[0])):
      if tmp[j]=='#': Board[y+i][x+j]=c
  return Board

def PrintBoard(Board):
  for e in Board:
    print "".join(e)
  print
  return

def PrintDots(DOTS):
  for e in DOTS:
    print e
  print
  return

def solve1(TRIALS, Board):
  if TRIALS==[]: return 1
  n = TRIALS[0]
  DOTS = count_board(Board)

  for direction in C[n]:
    P0 = PIECE[(n, direction)]
    h = len(P0)
    w = len(P0[0])
    s = B[n]
    POS=[]
    for i in range(Height-h+1):
      A1 = DOTS[i]
      A2 = DOTS[i+h]
      for j in range(Width-w+1):
        tmp = A1[j] - A2[j] - A1[j+w] + A2[j+w]
        if tmp>=s and tmp_put(Board, P0, i, j):
          Board = get_put(Board, P0, i, j, 0)
          tmp = TRIALS[:]
          del tmp[0]
          if solve1(tmp, Board): return 1
          Board = get_put(Board, P0, i, j, 1)
  return 0

def CheckPieceType(i):
  def f(x1, x2):
    for j in range(len(PIECE[i,x1])):
      if "".join(PIECE[i, x1][j])!="".join(PIECE[i, x2][j]): return 0
    return 1
  flg = [0,1,2,3]
  for a, b in [[0,1],[1,3],[0,2]]:
    if f(a, b): flg[b] = flg[a]
  return list(set(flg))
      
while 1:
  Height, Width = map(int,raw_input().split())
  if Height==Width==0: break
  Board = [list(raw_input()) for i in range(Height)]
  DOTS = count_board(Board)

  PIECE = {}
  n = input()
  B = [0]*n
  C = [[0 for _ in [0]*4] for _ in [0]*n]
  for i in range(n):
    height, width = map(int,raw_input().split())
    piece = [list(raw_input()) for _ in [0]*height]
    B[i] = sum([e.count('#') for e in piece])
    for direction in [0,1,2,3]:
      PIECE[(i, direction)] = piece
      piece = rot90(piece)

    C[i] = CheckPieceType(i)

  for _ in [0]*input():
    a = map(int, raw_input().split())[1:]
    a = sorted([[B[e-1], e-1] for e in a], key=lambda x:[-x[0]])
    TRIALS = list(zip(*a)[1])
    if check_sum(TRIALS): print "NO"; continue 
    print ["NO", "YES"][solve1(TRIALS, copy.deepcopy(Board))]

Submission status: Runtime Error

Solution code:
import copy
def rot90(A):
  return zip(*A[::-1])

def count_board(Board):
  X = [[0 for _ in [0]*(Width+1)] for _ in [0]*(Height+1)]
  for i in range(Height)[::-1]:
    for j in range(Width)[::-1]:
      X[i][j] = X[i+1][j] + X[i][j+1] - X[i+1][j+1] + (Board[i][j]=='.')
  return X

def check_sum(TRIALS):
  return sum([B[e] for e in TRIALS]) != DOTS[0][0]

def tmp_put(Board, piece, y, x):
  for i in range(len(piece)):
    tmp = piece[i]
    BoardRow = Board[y+i]
    for j in range(len(piece[0])):
      if tmp[j]=='#' and BoardRow[x+j]!='.': return 0
  return 1

def get_put(Board, piece, y, x, mode):
  c = '#.'[mode]
  for i in range(len(piece)):
    tmp = piece[i]
    for j in range(len(piece[0])):
      if tmp[j]=='#': Board[y+i][x+j]=c
  return Board

def PrintBoard(Board):
  for e in Board:
    print "".join(e)
  print
  return

def PrintDots(DOTS):
  for e in DOTS:
    print e
  print
  return

def solve1(TRIALS, Board):
  if TRIALS==[]: return 1
  n = TRIALS[0]
  DOTS = count_board(Board)

  for direction in C[n]:
    P0 = PIECE[(n, direction)]
    h = len(P0)
    w = len(P0[0])
    s = B[n]
    POS=[]
    for i in range(Height-h+1):
      A1 = DOTS[i]
      A2 = DOTS[i+h]
      for j in range(Width-w+1):
        tmp = A1[j] - A2[j] - A1[j+w] + A2[j+w]
        if tmp>=s and tmp_put(Board, P0, i, j):
          Board = get_put(Board, P0, i, j, 0)
          tmp = TRIALS[:]
          del tmp[0]
          if solve1(tmp, Board): return 1
          Board = get_put(Board, P0, i, j, 1)
  return 0

def CheckPieceType(i):
  def f(x1, x2):
    for j in range(len(PIECE[i, x1])):
      if "".join(PIECE[i, x1][j])!="".join(PIECE[i, x2][j]): return 0
    return 1
  flg = [0,1,2,3]
  for a, b in [[0,1], [1,3], [0,2]]:
    if f(a, b): flg[b] = flg[a]
  return list(set(flg))
      
start_time = time.clock() 

while 1:
  try:
    Height, Width = map(int,raw_input().split())
  except:
    break
  if Height==Width==0: break
  Board = [list(raw_input()) for i in range(Height)]
  DOTS = count_board(Board)

  PIECE = {}
  n = input()
  B = [0] * n
  C = [[0 for _ in [0]*4] for _ in [0] * n]
  for i in range(n):
    height, width = map(int, raw_input().split())
    tmp = [list(raw_input()) for _ in [0] * height]
    B[i] = sum([e.count('#') for e in tmp])
    for direction in [0, 1, 2, 3]:
      PIECE[(i, direction)] = tmp
      tmp = rot90(tmp)
    C[i] = CheckPieceType(i)

  for _ in [0]*input():
    a = map(int, raw_input().split())[1:]
    a = sorted([[B[e-1], e-1] for e in a], key = lambda x:[-x[0]])
    TRIALS = list(zip(*a)[1])
    if check_sum(TRIALS): print "NO"; continue 
    print ["NO", "YES"][solve1(TRIALS, copy.deepcopy(Board))]

Submission status: Runtime Error

Solution code:
import copy
def rot90(A):
  return zip(*A[::-1])

def count_board(Board):
  X = [[0 for _ in [0]*(Width+1)] for _ in [0]*(Height+1)]
  for i in range(Height)[::-1]:
    for j in range(Width)[::-1]:
      X[i][j] = X[i+1][j] + X[i][j+1] - X[i+1][j+1] + (Board[i][j]=='.')
  return X

def check_sum(TRIALS):
  return sum([B[e] for e in TRIALS]) != DOTS[0][0]

def tmp_put(Board, piece, y, x):
  for i in range(len(piece)):
    tmp = piece[i]
    BoardRow = Board[y+i]
    for j in range(len(piece[0])):
      if tmp[j]=='#' and BoardRow[x+j]!='.': return 0
  return 1

def get_put(Board, piece, y, x, mode):
  c = '#.'[mode]
  for i in range(len(piece)):
    tmp = piece[i]
    for j in range(len(piece[0])):
      if tmp[j]=='#': Board[y+i][x+j]=c
  return Board

def PrintBoard(Board):
  for e in Board:
    print "".join(e)
  print
  return

def PrintDots(DOTS):
  for e in DOTS:
    print e
  print
  return

def solve1(TRIALS, Board):
  if TRIALS==[]: return 1
  n = TRIALS[0]
  DOTS = count_board(Board)

  for direction in C[n]:
    P0 = PIECE[(n, direction)]
    h = len(P0)
    w = len(P0[0])
    s = B[n]
    POS=[]
    for i in range(Height-h+1):
      A1 = DOTS[i]
      A2 = DOTS[i+h]
      for j in range(Width-w+1):
        tmp = A1[j] - A2[j] - A1[j+w] + A2[j+w]
        if tmp>=s and tmp_put(Board, P0, i, j):
          Board = get_put(Board, P0, i, j, 0)
          tmp = TRIALS[:]
          del tmp[0]
          if solve1(tmp, Board): return 1
          Board = get_put(Board, P0, i, j, 1)
  return 0

def CheckPieceType(i):
  def f(x1, x2):
    for j in range(len(PIECE[i, x1])):
      if "".join(PIECE[i, x1][j])!="".join(PIECE[i, x2][j]): return 0
    return 1
  flg = [0,1,2,3]
  for a, b in [[0,1], [1,3], [0,2]]:
    if f(a, b): flg[b] = flg[a]
  return list(set(flg))
      
while 1:
  try:
    Height, Width = map(int,raw_input().split())
  except:
    break
  if Height==Width==0: break
  Board = [list(raw_input()) for i in range(Height)]
  DOTS = count_board(Board)

  PIECE = {}
  n = input()
  B = [0] * n
  C = [[0 for _ in [0]*4] for _ in [0] * n]
  for i in range(n):
    height, width = map(int, raw_input().split())
    tmp = [list(raw_input()) for _ in [0] * height]
    B[i] = sum([e.count('#') for e in tmp])
    for direction in [0, 1, 2, 3]:
      PIECE[(i, direction)] = tmp
      tmp = rot90(tmp)
    C[i] = CheckPieceType(i)

  for _ in [0]*input():
    a = map(int, raw_input().split())[1:]
    a = sorted([[B[e-1], e-1] for e in a], key = lambda x:[-x[0]])
    TRIALS = list(zip(*a)[1])
    if check_sum(TRIALS): print "NO"; continue 
    print ["NO", "YES"][solve1(TRIALS, copy.deepcopy(Board))]