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: Runtime Error

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

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):
  N = range(len(piece[0]))
  for i in range(len(piece)):
    tmp = piece[i]
    BoardRow = Board[y+i]
    for j in N:
      if tmp[j]=='#' and BoardRow[x+j]!='.': return 0
  return 1

def get_put(Board, piece, y, x, mode):
  c = '#.'[mode]
  W = range(len(piece[0]))
  for i in range(len(piece)):
    tmp = piece[i]
    Y = y+i
    for j in W:
      if tmp[j]=='#': Board[Y][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
  n = TRIALS[0]
  DOTS = count_board(Board)
  for direction in C[n]:
    P = PIECE[(n, direction)]
    h = len(P)
    w = len(P[0])
    s = B[n]
    POS=[]
    H = range(Height-h+1)
    W = range(Width-w+1)
    for i in H:
      A1 = DOTS[i]
      A2 = DOTS[i+h]
      for j in W:
        tmp = A1[j] - A2[j] - A1[j+w] + A2[j+w]
        if tmp>=s and tmp_put(Board, P, i, j):
          Board = get_put(Board, P, i, j, 0)
          if solve(TRIALS[1:], Board): return 1
          Board = get_put(Board, P, 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 _ in [0]*Height]
  DOTS = count_board(Board)
  PIECE = {}
  n = input()
  B = [0] * n
  C = [[0, 0, 0, 0] 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"
    else: print ["NO", "YES"][solve(TRIALS, copy.deepcopy(Board))]

Submission status: Runtime Error

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

def count_board(Board):
  X = [[0 for _ in [0]*(Width+1)] for _ in [0]*(Height+1)]
  try:
    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
  except:
    return X

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

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

def get_put(Board, piece, y, x, mode):
  c = '#.'[mode]
  W = range(len(piece[0]))
  for i in range(len(piece)):
    tmp = piece[i]
    Y = y+i
    for j in W:
      if tmp[j]=='#': Board[Y][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
  n = TRIALS[0]
  DOTS = count_board(Board)
  for direction in C[n]:
    P = PIECE[(n, direction)]
    h = len(P)
    w = len(P[0])
    s = B[n]
    POS=[]
    H = range(Height-h+1)
    W = range(Width-w+1)
    for i in H:
      A1 = DOTS[i]
      A2 = DOTS[i+h]
      for j in W:
        tmp = A1[j] - A2[j] - A1[j+w] + A2[j+w]
        if tmp>=s and tmp_put(Board, P, i, j):
          Board = get_put(Board, P, i, j, 0)
          if solve(TRIALS[1:], Board): return 1
          Board = get_put(Board, P, 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 _ in [0]*Height]
  DOTS = count_board(Board)
  PIECE = {}
  n = input()
  B = [0] * n
  C = [[0, 0, 0, 0] 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"
    else: print ["NO", "YES"][solve(TRIALS, copy.deepcopy(Board))]

Submission status: Runtime Error

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

def count_board(Board):
  X = [[0 for _ in [0]*(Width+1)] for _ in [0]*(Height+1)]
  try:
    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
  except:
    return X

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

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

def get_put(Board, piece, y, x, mode):
  c = '#.'[mode]
  W = range(len(piece[0]))
  for i in range(len(piece)):
    tmp = piece[i]
    Y = y+i
    for j in W:
      if tmp[j]=='#': Board[Y][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
  n = TRIALS[0]
  DOTS = count_board(Board)
  for direction in C[n]:
    P = PIECE[(n, direction)]
    h = len(P)
    w = len(P[0])
    s = B[n]
    POS=[]
    H = range(Height-h+1)
    W = range(Width-w+1)
    for i in H:
      A1 = DOTS[i]
      A2 = DOTS[i+h]
      for j in W:
        tmp = A1[j] - A2[j] - A1[j+w] + A2[j+w]
        if tmp>=s and tmp_put(Board, P, i, j):
          Board = get_put(Board, P, i, j, 0)
          if solve(TRIALS[1:], Board): return 1
          Board = get_put(Board, P, 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 _ in [0]*Height]
  DOTS = count_board(Board)
  PIECE = {}
  n = input()
  B = [0] * n
  C = [[0, 0, 0, 0] 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"
    else: 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):
  N = range(len(piece[0]))
  for i in range(len(piece)):
    tmp = piece[i]
    BoardRow = Board[y+i]
    for j in N:
      if tmp[j]=='#' and BoardRow[x+j]!='.': return 0
  return 1

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

def solve(TRIALS, Board):
  if TRIALS==[]: return 1
  n = TRIALS[0]
  DOTS = count_board(Board)
  for direction in C[n]:
    P = PIECE[(n, direction)]
    h = len(P)
    w = len(P[0])
    s = B[n]
    POS=[]
    H = range(Height-h+1)
    W = range(Width-w+1)
    for i in H:
      A1 = DOTS[i]
      A2 = DOTS[i+h]
      for j in W:
        tmp = A1[j] - A2[j] - A1[j+w] + A2[j+w]
        if tmp>=s and tmp_put(Board, P, i, j):
          Board = get_put(Board, P, i, j, 0)
          if solve(TRIALS[1:], Board): return 1
          Board = get_put(Board, P, 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 _ in [0]*Height]
  DOTS = count_board(Board)
  PIECE = {}
  n = input()
  B = [0] * n
  C = [[0, 0, 0, 0] 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"
    else: print ["NO", "YES"][solve(TRIALS, copy.deepcopy(Board))]

Submission status: Runtime Error

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

def count_board(Board):
#Board [0,0]から[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 tmp_put(Board, piece, y, x):
  #ピースを枠の[x,y]に置けるかチェック
  #戻り値: OK=1, NG=0
  N = range(len(piece[0]))
  for i in range(len(piece)):
    tmp = piece[i]
    BoardRow = Board[y+i]
    for j in N:
      if tmp[j]=='#' and BoardRow[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]
  W = range(len(piece[0]))
  for i in range(len(piece)):
    tmp = piece[i]
    Y = y+i
    for j in W:
      if tmp[j]=='#': Board[Y][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
  n = TRIALS[0]
  DOTS = count_board(Board)

  for direction in C[n]:
    P = PIECE[(n, direction)]
    h = len(P)
    w = len(P[0])
    s = B[n]
    POS=[]
    H = range(Height-h+1)
    W = range(Width-w+1)
    for i in H:
      A1 = DOTS[i]
      A2 = DOTS[i+h]
      for j in W:
        tmp = A1[j] - A2[j] - A1[j+w] + A2[j+w]
        if tmp>=s and tmp_put(Board, P, i, j):
          Board = get_put(Board, P, i, j, 0)
          if solve(TRIALS[1:], Board): return 1
          Board = get_put(Board, P, 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() 
sys.setrecursionlimit(15)
#パズル枠データの設定
while 1:
  Height, Width = map(int,raw_input().split())
  if Height*Width==0: break
  Board = [list(raw_input()) for _ in [0]*Height]
  DOTS = count_board(Board)

  #ピースデータの設定
  PIECE = {}
  n = input()
  B = [0] * n
  C = [[0, 0, 0, 0] 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"
    else: print ["NO", "YES"][solve(TRIALS, copy.deepcopy(Board))]

Submission status: Runtime Error

Solution code:
import copy,sys
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):
  N = range(len(piece[0]))
  for i in range(len(piece)):
    tmp = piece[i]
    BoardRow = Board[y+i]
    for j in N:
      if tmp[j]=='#' and BoardRow[x+j]!='.': return 0
  return 1

def get_put(Board, piece, y, x, mode):
  c = '#.'[mode]
  W = range(len(piece[0]))
  for i in range(len(piece)):
    tmp = piece[i]
    Y = y+i
    for j in W:
      if tmp[j]=='#': Board[Y][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
  n = TRIALS[0]
  DOTS = count_board(Board)

  for direction in C[n]:
    P = PIECE[(n, direction)]
    h = len(P)
    w = len(P[0])
    s = B[n]
    POS=[]
    H = range(Height-h+1)
    W = range(Width-w+1)
    for i in H:
      A1 = DOTS[i]
      A2 = DOTS[i+h]
      for j in W:
        tmp = A1[j] - A2[j] - A1[j+w] + A2[j+w]
        if tmp>=s and tmp_put(Board, P, i, j):
          Board = get_put(Board, P, i, j, 0)
          if solve(TRIALS[1:], Board): return 1
          Board = get_put(Board, P, 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() 
sys.setrecursionlimit(15)
while 1:
  Height, Width = map(int,raw_input().split())
  if Height*Width==0: break
  Board = [list(raw_input()) for _ in [0]*Height]
  DOTS = count_board(Board)

  PIECE = {}
  n = input()
  B = [0] * n
  C = [[0, 0, 0, 0] 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"
    else: print ["NO", "YES"][solve(TRIALS, copy.deepcopy(Board))]

Submission status: Runtime Error

Solution code:
import copy,sys
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):
  N = range(len(piece[0]))
  for i in range(len(piece)):
    tmp = piece[i]
    BoardRow = Board[y+i]
    for j in N:
      if tmp[j]=='#' and BoardRow[x+j]!='.': return 0
  return 1

def get_put(Board, piece, y, x, mode):
  c = '#.'[mode]
  W = range(len(piece[0]))
  for i in range(len(piece)):
    tmp = piece[i]
    Y = y+i
    for j in W:
      if tmp[j]=='#': Board[Y][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
  n = TRIALS[0]
  DOTS = count_board(Board)

  for direction in C[n]:
    P = PIECE[(n, direction)]
    h = len(P)
    w = len(P[0])
    s = B[n]
    POS=[]
    H = range(Height-h+1)
    W = range(Width-w+1)
    for i in H:
      A1 = DOTS[i]
      A2 = DOTS[i+h]
      for j in W:
        tmp = A1[j] - A2[j] - A1[j+w] + A2[j+w]
        if tmp>=s and tmp_put(Board, P, i, j):
          Board = get_put(Board, P, i, j, 0)
          if solve(TRIALS[1:], Board): return 1
          Board = get_put(Board, P, 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))

sys.setrecursionlimit(15)
while 1:
  Height, Width = map(int,raw_input().split())
  if Height*Width==0: break
  Board = [list(raw_input()) for _ in [0]*Height]
  DOTS = count_board(Board)

  PIECE = {}
  n = input()
  B = [0] * n
  C = [[0, 0, 0, 0] 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"
    else: print ["NO", "YES"][solve(TRIALS, copy.deepcopy(Board))]