ZOJ Problem Set-1100 Mondriaan's Dream Python実現

動的計画問題.構想は暴力検索であり,各層単位で検索し,状態数が少なく,各行の格子をバイナリ符号化に圧縮する.
Pythonコード:

# -*- coding: utf-8 -*-

import sys

 
H = W = 0

#          

tran = []

 
def dfs(n, _from, to):

    '''      W   ，          

    _from       ，to       

    _from 1    ，0     

    to 1    （             ）

    0     （                ，             ）

    '''

    global W, tran

    if n > W:

        return

    if n == W:

        tran.append((_from, to))

        return

    
    #       

    dfs(n   2, (_from << 2)   3, (to << 2)   3)

    #       

    dfs(n   1, (_from << 1)   1, to << 1)

    #      

    dfs(n   1, _from << 1, (to << 1)   1)

 
def dp():

    global W, H, tran

    #          

    # b[i][j]  0 i - 1      i    j       

    #     b[H][(1 << W) - 1]    

    b = [[0 for j in xrange(2048)] for i in xrange(12)]

    #      0 ，     1，      

    b[0][(1 << W) - 1] = 1

    for i in xrange(H):

        for j in tran:

            b[i   1][j[1]]  = b[i][j[0]]

    print b[H][(1 << W) - 1]

            
def main():

    global W, H, tran

    for line in sys.stdin:

        H, W = [int(a) for a in line.split()]

        if H == W == 0:

            break

        tran = []

        if H < W:

            H, W = W, H

        dfs(0, 0, 0)

        dp()

     
if __name__ == '__main__':

    main()