Google Code Jam Japan 2011 決勝 D. クローゼットルーム (Small)

クローゼットルーム

Smallならばクローゼットの置き方を全て試せる。

# coding: utf-8
import copy

# 全てのクローゼットに到達可能かチェック
def check(M,C):
    T = copy.deepcopy(M)
    # 入り口から到達可能なマスをDにする
    while True:
        up = False
        for y in range(H):
         for x in range(W):
            if T[y][x]=="D":
                for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                    ty, tx = y+dy, x+dx
                    if 0<=tx<W and 0<=ty<H and T[ty][tx]==".":
                        T[ty][tx] = "D"
                        up = True
        if not up:
            break
    
    # 全てのクロゼットの隣にDがあるか調べる
    f = True
    for y,x,d in C:
        if d==0:
            if ( ( y==0   or T[y-1][x+1]!="D" ) and
                 ( y==H-1 or T[y+1][x  ]!="D" ) ):
                f = False
        else:
            if ( ( x==0   or T[y  ][x-1]!="D" ) and
                 ( x==W-1 or T[y+1][x+1]!="D" ) ):
                f = False
    return f

# バックトラックでクローゼットを置く
def BT(H,W,M,C,p):
    if p>=W*H:
        global maxc
        if len(C)>maxc and check(M,C):
            maxc = len(C)
        return
    
    # 置かない
    BT(H,W,M,C,p+1)
    
    # 0: 横向き　1: 縦向き
    for i in range(2):
        py, px = p/W, p%W
        ty, tx = py+[0,1][i], px+[1,0][i]
        if ty<H and tx<W and M[py][px]!='X' and M[ty][tx]!='X':
            tmp = M[py][px],M[ty][tx]
            M[py][px] = M[ty][tx] = 'X'
            C += [(py,px,i)]
            BT(H,W,M,C,p+1)
            M[py][px],M[ty][tx] = tmp
            del(C[-1])
    
def solve_small(H,W,M):
    global maxc
    maxc = 0
    BT(H,W,M,[],0)
    return maxc
    
for t in xrange(input()):
    H,W = map(int,raw_input().split())
    M = [list(raw_input()) for i in range(H)]
    ans = solve_small(H,W,M)
    print "Case #%s: %s" % (t+1,ans)