画家问题

注意： 总时间限制: 1000ms 内存限制: 65536kB

描述

有一个正方形的墙，由N*N个正方形的砖组成，其中一些砖是白色的，另外一些砖是黄色的。Bob是个画家，想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时， 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖，才能使所有砖的颜色都变成黄色。

输入

第一行是一个整数n (1≤n ≤15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖，“y”表示黄砖。

输出

一行，如果Bob能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出“inf”。

样例输入

5
wwwww
wwwww
wwwww
wwwww
wwwww

样例输出

15 

代码

思路同之前的C++代码

#! /usr/bin/python

def guess(n,init2,draw):
    for r in range(1,n):
        for c in range(1,n+1):
            draw[r+1][c]=(init2[r][c]+draw[r][c]+draw[r-1][c]+draw[r][c-1]+draw[r][c+1])%2
    for c in range(1,n+1):
        if (draw[n][c-1]+draw[n][c]+draw[n][c+1]+draw[n-1][c])%2!=init2[n][c]:
            return False
    return True

def enumerate(n,init2,draw):
    mindraw=226;
    sum=0;
    for c in range(1,n+1):
        draw[1][c]=0
    for i in range(0,pow(2,n)):
        if guess(n,init2,draw)==True:
            for r in range(1,n+1):
                for c in range(1,n+1):
                    sum = sum+draw[r][c]
            if sum<mindraw :
                mindraw=sum
        draw[1][1]+=1
        c=1
        while draw[1][c]>1:
            draw[1][c]=0
            c+=1
            draw[1][c]+=1
    return mindraw
    
def main():
    n=int(input())
    init=[]
    init2=[[0 for col in range(n+2)] for row in range(n+1)]
    draw=[[0 for col in range(n+2)] for row in range(n+1)]
    for r in range(0,n):
        init.append(input())
        for c in range(0,n):
            if init[r][c]=='w':
                init2[r+1][c+1]=1
    result=enumerate(n,init2,draw)
    if result==226:
        print('inf')
    else:
        print(result)
        
main()