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: Wrong Answer

Solution code:
d={}
H,W=map(int,raw_input().split())
A=list([raw_input() for i in range(H)])
area0=sum([e.count(".") for e in A])

n=input()
B=[[0,0,0] for i in [0]*n]
for i in range(n):
  h,w=map(int,raw_input().split())
  P=[list(raw_input()) for _ in range(h)]
  d[i]=P
  B[i]=[sum([e.count("#") for e in d[i]]),max(h,w),i]
p=input()
for _ in range(p):
  A=map(int,raw_input().split())
  area1=sum([B[i-1][0] for i in A[1:]])
  if area1==area0: print "YES"
  else: print "NO"

Submission status: Wrong Answer

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

def count_board(A):
  X = [[0 for _ in range(Width+1)] for _ in range(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(A):
  area = sum([B[i-1][0] for i in A[1:]])
  return area!=Board_area[0][0]

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

def tmp_put(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 solve(TRIALS, Board):
  if TRIALS==[]: return 1
  e = TRIALS[0]
  POS = get_POS(e-1,0)+get_POS(e-1,1)
  for pos in POS:
    Board = get_put(Board, PIECE[(e-1,pos[2])], pos[0], pos[1], 0)
    tmp = TRIALS[:]
    del tmp[0]
    if solve(tmp, Board): return 1
    Board = get_put(Board, PIECE[(e-1,pos[2])], pos[0], pos[1], 1)
  return 0
  
Height,Width = map(int,raw_input().split())
Board = [list(raw_input()) for i in range(Height)]
Board_area = count_board(Board)

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

Submission status: Wrong Answer

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(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(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):
  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 solve(TRIALS, Board):
  if TRIALS==[]: return 1
  e = TRIALS[0]
  DOTS = count_board(Board)
  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 
  tmpBoard = copy.deepcopy(Board)
  print ["NO", "YES"][solve(TRIALS, tmpBoard)]

Submission status: Wrong Answer

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(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(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):
  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 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: Wrong Answer

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(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, Board[:])]

Submission status: Wrong Answer

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
 
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: Time Limit Exceeded

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

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 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):
                    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):
    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,range(len(pieces))):
        tmp = tuple(sorted(reduce(lambda a,b:a+b,ols)))
        if tmp not in ANS_SET:
            ANS_SET[tmp] = all(DFS(f,pieces,ol) 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:
        yield []
    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 = [[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)
    init_DFS(field,pieces)
    #print ANS_SET
    for _ in xrange(input()):
        num = tuple(sorted(map(lambda a:int(a)-1,raw_input().split())[1:]))
        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 = {}

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 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):
                    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):
    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,range(len(pieces))):
        tmp = tuple(sorted(reduce(lambda a,b:a+b,ols)))
        if tmp not in ANS_SET:
            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:
        yield []
    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 = [[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)
    init_DFS(field,pieces)
    #print ANS_SET
    for _ in xrange(input()):
        num = tuple(sorted(map(lambda a:int(a)-1,raw_input().split())[1:]))
        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 = {}

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 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 = [[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"