Problem:
 Score : 300 points    Problem Statement We have a grid of H rows and W columns of squares. The color of the square at the i -th row from the top and the j -th column from the left (1 \leq i \leq H, 1 \leq j \leq W) is given to you as a character c_{i,j} : the square is white if c_{i,j} is . , and black if c_{i,j} is # .  Consider doing the following operation:   Choose some number of rows (possibly zero), and some number of columns (possibly zero). Then, paint red all squares in the chosen rows and all squares in the chosen columns.   You are given a positive integer K . How many choices of rows and columns result in exactly K black squares remaining after the operation? Here, we consider two choices different when there is a row or column chosen in only one of those choices.      Constraints  1 \leq H, W \leq 6  1 \leq K \leq HW  c_{i,j} is . or # .         Input Input is given from Standard Input in the following format:  H  W  K  c_{1,1}c_{1,2}...c_{1,W}  c_{2,1}c_{2,2}...c_{2,W}  :  c_{H,1}c_{H,2}...c_{H,W}       Output Print an integer representing the number of choices of rows and columns satisfying the condition.        Sample Input 1 2 3 2
..#
###      Sample Output 1 5  Five choices below satisfy the condition.   The 1 -st row and 1 -st column  The 1 -st row and 2 -nd column  The 1 -st row and 3 -rd column  The 1 -st and 2 -nd column  The 3 -rd column        Sample Input 2 2 3 4
..#
###      Sample Output 2 1  One choice, which is choosing nothing, satisfies the condition.       Sample Input 3 2 2 3
##
##      Sample Output 3 0       Sample Input 4 6 6 8
..##..
.#..#.
#....#
######
#....#
#....#      Sample Output 4 208

Solution (Python):
import copy
import itertools
import numpy as np

H, W, K = map(int, input().split())
c = []
for _ in range(H):
    c.append(list(input()))
ans = 0

list_H = []
for i in range(1, H+1):
    list_H.append(i)
list_W = []
for i in range(1, W+1):
    list_W.append(i)

for i in range(H+1):
    for v in itertools.combinations(list_H, i):
        tmp_masu = []
        for j in list(v):
            tmp_masu.append(c[j-1])
        tmp_masu = np.array(tmp_masu)
        for j in range(W+1):
            for x in itertools.combinations(list_W, j):
                try:
                    tmp_masu_ = copy.deepcopy(tmp_masu)
                    count = 0
                    for k in list(x):
                        tmp_masu_ = np.delete(tmp_masu_, k-1-count, 1)
                        count += 1
                    tmp = tmp_masu_.tolist()
                    count_ = 0
                    for k in range(len(tmp)):
                        count_ += tmp[k].count('
                    if count_ == K:
                        ans += 1
                except IndexError:
                    pass
print(ans)

Solution (Python):
import itertools
import numpy as np

h, w, k = (int(each) for each in input().split())
c = []
for _ in range(h):
    c.append(list(input()))

result = 0

n_c = np.array(c)

for y in itertools.product([0,1], repeat = h):
    for x in itertools.product([0,1], repeat = w):
        
        n_c2 = np.array(c)
        for i, y2 in enumerate(y):
            if y2 == 1:
                n_c2[i] = 'R'
        for i, x2 in enumerate(x):
            if x2 == 1:
                n_c2[:,i] = 'R'
        
        m = np.count_nonzero(n_c2 == '
        if k == m:
            result += 1

print(result)

Solution (Python):
import itertools
import copy
h, w, k = map(int, input().split())

cs = []
for i in range(h):
    cs.append(list(input()))



hpatterns = []
for i in range(h + 1):
    hpatterns += list(itertools.combinations(range(h), i))
wpatterns = []
for i in range(w + 1):
    wpatterns += list(itertools.combinations(range(w), i))




c = 0
for hpattern in hpatterns:
    for wpattern in wpatterns:
        black = 0
        cs2 = copy.deepcopy(cs)
        for pi in hpattern:
            cs2[pi] = ['' for k in range(w)]

        for pj in wpattern:
            for s in range(len(cs2)):
                
                cs2[s][pj] = ''
        
        for s in cs2:
            black += s.count('

        if black == k:
            c += 1

print(c)

Solution (Python):

import sys
import itertools
input = sys.stdin.readline

H,W,K = list(map(int,input().split()))
lis_H = []
lis_W = []

for i in range(H):
    Hi = list(itertools.combinations(range(0,H),i+1))
    lis_H.append(Hi)
lis_H.append([(99,)])
for i in range(W):
    Wi = list(itertools.combinations(range(0,W),i+1))
    lis_W.append(Wi)
lis_W.append([(99,)])
C = []
for i in range(H):
    ci = input().rstrip()
    C.append(ci)
ans = 0
for hi in range(len(lis_H)):
    for hj in range(len(lis_H[hi])):
        for wi in range(len(lis_W)):
            for wj in range(len(lis_W[wi])):
                counter = 0
                for hk in range(H):
                    for wk in range(W):
                        if C[hk][wk] == '
                            counter +=1
                if counter == K:
                    ans += 1


print(ans)

Solution (Python):
import itertools
H, W, K = map(int, input().split())
C = []
for _ in range(H):
    C.append(input())
r = 0
for i in range(1, H+1):
    for ii in itertools.combinations(range(H), i):
        for j in range(1, W+1):
            for jj in itertools.combinations(range(W), j):
                l = 0
                for x in [C[iii] for iii in ii]:
                    xx = [x[jjj] for jjj in jj]
                    l += len([xxx for xxx in xx if xxx == '
                if l == K:
                    r += 1
print(r)

Solution (Python):
h,w,k=map(int,input().split())
l=[]
v=['']*w
h_n=[0]*h
v_n=[0]*w
n=0
ans=0
for i in range(h):
    s=input()
    scnt=s.count('
    n+=scnt
    h_n[i]+=scnt
    l.append(s)
    for j in range(w):
        v[j]+=s[j]
for i in range(w):
    v_n[i]+=v[i].count('


for i in range(2**h):
    for j in range(2**w):
        i_bin=bin(i)[2:]
        i_bin='0'*(h-len(i_bin))+i_bin
        j_bin=bin(j)[2:]
        j_bin='0'*(w-len(j_bin))+j_bin
        h_ind=[]
        w_ind=[]
        for ii in range(len(i_bin)):
            if i_bin[ii]=='1':
                h_ind.append(ii)
        for jj in range(len(j_bin)):
            if j_bin[jj]=='1':
                w_ind.append(jj)
        nn=0
        for kk in h_ind:
            nn+=h_n[kk]
            for ll in w_ind:
                if l[kk][ll]=='
                    nn-=1
        for ll in w_ind:
            nn+=v_n[ll]
        if n-nn==k:
            ans+=1
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
C = [input() for _ in range(H)]

c = [[] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if C[i][j] == ".":
            c[i].append(0)
        elif C[i][j] == "
            c[i].append(1)


sw = []
for i in range(H):
    sw.append(sum(c[i]))

sh = []
for i in range(W):
    s = 0
    for j in range(H):
        s += c[j][i]
    sh.append(s)

S = sum(sw)
ans = 0

for i in range(2 ** H):
    Y = []
    ds = 0
    for h in range(H):
        if (i >> h) & 1:
            ds += sw[h]
            Y.append(h)

    for j in range(2 ** W):
        s = S - ds
        X = []
        for w in range(W):
            if (j >> w) & 1:
                s -= sh[w]
                X.append(w)
        
        for y in Y:
            for x in X:
                s += c[y][x]
        
        if s == K:
            ans += 1

print(ans)

Solution (Python):








def solve(H, W, K, Cxx):
    ans = 0
    for i in range(2 ** H):
        for j in range(2 ** W):
            cnt = 0
            for h in range(H):
                if i >> h & 1 == 1:
                    continue
                for w in range(W):
                    if j >> w & 1 == 1:
                        continue
                    if Cxx[h][w] == '
                        cnt += 1
            if cnt == K:
                ans += 1
    print(ans)



if __name__ == '__main__':
    
    
    H, W, K = map(int, input().split())
    Cxx = [input() for _ in range(H)]
    
    
    solve(H, W, K, Cxx)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W, K = map(int, readline().split())
C = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W]

C = 1 * (C == b'

def f(C, x, y):
    rows = [i for i in range(H) if x & (1<<i)]
    cols = [i for i in range(W) if y & (1<<i)]
    D = C[rows][:,cols]
    return D.sum() == K

ans = 0
for x in range(1 << H):
    for y in range(1 << W):
        ans += f(C, x, y)
print(ans)

Solution (Python):



import sys
import itertools
from copy import deepcopy

def input():
    return sys.stdin.readline()

def count_black(combi, field, h, w):

    height_list = []
    width_list = []
    for num in combi:
        if num <= h:
            height_list.append(num)
        else:
            width_list.append(num-(h))

    
    

    for line in height_list:
        for i in range(w):
            field[line-1][i] = "x"

    for row in width_list:
        for i in range(h):
            field[i][row-1] = "x"

    black_cnt = 0
    for line in field:
        black_cnt += line.count("

    return black_cnt





def resolve():
    h, w, k = map(int, input().split())
    field = [list(input().rstrip()) for i in range(h)]
    

    lst = []

    for i in range(1, h+1):
        lst.append(i)

    lst_length = len(lst)
    for j in range(1, w+1):
        lst.append(lst_length+j)


    
    p = []
    for i in range(len(lst)):
        p.append(itertools.combinations(lst, i+1))

    ans_num = 0

    for v in p:
        for vv in v:
            temp_field = deepcopy(field)
            black_num = count_black(vv, temp_field, h, w)
            if black_num == k:
                ans_num += 1

    
    black_cnt = 0
    for line in field:
        black_cnt += line.count("

    if black_cnt == k:
        ans_num += 1

    print(ans_num)

if __name__ == "__main__":
    resolve()

Solution (Python):
from itertools import product
from copy import copy


def count(f):
    ret = 0
    for h in f:
        for w in h:
            if w == '
                ret += 1

    return ret


(h, w, k) = [int(s) for s in input().split()]

f = []

for _ in range(h):
    f.append(list(input()))

tmp = [range(2)] * h
bit_h = list(product(*tmp))

tmp = [range(2)] * w
bit_w = list(product(*tmp))

ans = 0

for bh in bit_h:
    for bw in bit_w:
        d = []

        for i, hh in enumerate(bh):
            if hh == 1:
                d.append(['-'] * w)
            else:
                d.append(copy(f[i]))

        for i, ww in enumerate(bw):
            if ww == 1:
                for dd in d:
                    dd[i] = '-'

        if count(d) == k:
            ans += 1


print(ans)

Solution (Python):
import numpy as np

H,W,K = map(int, input().split())

def s2n(s):
    if s=='
        return 1
    else:
        return 0

c = []

for i in range(H):
    c.append(list(map(s2n,list(input()))))
    


ans = 0

def fill(mp,num,iscolumn):
    if iscolumn==0:
        mp[num]=0
    else:
        mp[:,num-H]=0
    return mp

for i in range(2**(H+W)):
    mp = np.array(c)
    for j in range(H+W):
        if((i>>j)&1):
            mp = fill(mp,j,j>=H)
    if np.sum(mp)==K:
        ans+=1

print(ans)

Solution (Python):
import numpy as np
 
h, w, k = list(map(int, input().split(' ')))
c = []
for i in range(h):
    c.append(np.array(list(list(input()))))
 
c = np.array(c)
ans = 0
 
h_comb = [[]]
for i in range(h):
    h_comb.append([i])
    for j in range(i+1, h):
        h_comb.append([i, j])
        for l in range(j+1, h):
            h_comb.append([i, j, l])
            for m in range(l+1, h):
                h_comb.append([i, j, l, m])
                for n in range(m+1, h):
                    h_comb.append([i, j, l, m, n])
                    for o in range(n+1, h):
                        h_comb.append([i, j, l, m, n, o])
 
w_comb = [[]]
for i in range(w):
    w_comb.append([i])
    for j in range(i+1, w):
        w_comb.append([i, j])
        for l in range(j+1, w):
            w_comb.append([i, j, l])
            for m in range(l+1, w):
                w_comb.append([i, j, l, m])
                for n in range(m+1, w):
                    w_comb.append([i, j, l, m, n])
                    for o in range(n+1, w):
                        w_comb.append([i, j, l, m, n, o])
 
 
for h_indice in h_comb:
    for w_indice in w_comb:
        a = c.copy()
        if len(h_indice) != 0:
            for i in h_indice:
                a[i, :] = 'x'
        if len(w_indice) != 0:
            for i in w_indice:
                a[:, i] = 'x'
        cnt = np.count_nonzero(a=='
        if cnt == k:
            ans += 1
 
print(ans)

Solution (Python):
h,w,k=map(int,input().split())
l=[]

for i in range(h):
    l.append([x for x in input()])

ans=0
for i in range(2**h):
    row=bin(i)[2:]
    while len(row)<h:row='0'+row
    for j in range(2**w):
        col=bin(j)[2:]
        while len(col) < w: col = '0' + col

        s=0
        for x in range(h):
            for y in range(w):
                if l[x][y]=='
                    s+=1

        if s==k:
            ans+=1
print(ans)

Solution (Python):
from sys import stdin
from sys import setrecursionlimit
from itertools import permutations
import numpy as np

h,w,k = map(int,input().split())
li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]

point = 0
c = np.array(li)

for i in range(2**h):
    for j in range(2**w):
        d = c.copy()
        count = 0
        for ii in range(h):
            if (i >> ii)&1:
                for iii in range(w):
                    d[ii][iii] = 0
        for jj in range(w):
            if (j >> jj)&1:
                for jjj in range(h):
                    d[jjj][jj] = 0
        d = d.flatten()
        if np.count_nonzero(d=="
            point += 1

print(point)

Solution (Python):
import itertools
import copy
h, w, k = map(int, input().split())
ans = 0
yoko = []
for _ in range(h):
    c = input()
    yoko.append(c)
y = [int(i) for i in range(h)]
y_kouho = []
t = [int(i) for i in range(w)]
t_kouho = []
for i in range(h+1):
    yy = itertools.combinations(y, i)
    y_kouho.append(list(yy))
for i in range(w+1):
    tt = itertools.combinations(t, i)
    t_kouho.append(list(tt))
    
for y_k in y_kouho:
    if len(y_k) > 0:
        for yy_k in y_k:
            y_test = copy.copy(yoko)
            yy_k = list(yy_k)
            if len(yy_k) > 0:
                for yyy_k in yy_k:
                    y_test[yyy_k] = list('-'*w)

            tate = []
            for i in range(w):
                c = [s[i] for s in y_test]
                tate.append(c)


            for t_k in t_kouho:
                if len(t_k) > 0:
                    for tt_k in t_k:
                        t_test = copy.copy(tate)
                        sm = 0
                        tt_k = list(tt_k)
                        if len(tt_k) > 0:
                            for ttt_k in tt_k:
                                t_test[ttt_k] = list('-' * h)


                        for i in range(w):
                            sm += t_test[i].count('
                        if sm == k:
                            ans += 1
print(ans)

Solution (Python):
import numpy as np
import itertools


def conv(l, n):
    a = [True]*n
    for i in l:
        a[i] = False
    return a

H, W, K = list(map(int, input().split()))
c = [input().split() for _  in range(H)]
c = np.array([list(c[i][0]) for i in range(H)])

path = 0
H_array = range(H)
W_array = range(W)
for n_i in range(H+1):
    for n_j in range(W):
        for comb_i in itertools.combinations(H_array, n_i):
            for comb_j in itertools.combinations(W_array, n_j):
                black = np.count_nonzero(c[conv(comb_i, H)][:, conv(comb_j, W)] == '
                if black == K:
                    path += 1

print(path)

Solution (Python):
from copy import deepcopy
h,w,k=map(int, input().split())
maze=[list(input()) for _ in range(h)]
ans=0
for bit in range(1<<h):
    

    
    if bit == 2**h:
        continue
    
    t1=deepcopy(maze)
    
    for i in range(h):
        if bit & (1<<i):
            for j in range(w):
                t1[i][j] = "."
    
    
    for Bit in range(1<<w):
        
        if Bit == 2**w:
            continue

        t2=deepcopy(t1)
        
        
        for n in range(w):
            if Bit & (1<<n):
                for l in range(h):
                    t2[l][n] = "."
        
        
        cnt = 0
        for m in range(h):
            cnt += t2[m].count("
        if cnt == k:
            ans += 1
print(ans)

Solution (Python):
import copy
H, W, K = map(int,input().split())
c = [list(input()) for __ in range(H)]



ans = 0
for bit in range(1<<(H+W)):
  
  row = 0
  c_new = copy.deepcopy(c)
  
  while bit:
    a = bit%2
    
    
    if(a):
      if row < H:
        for i in range(W):
            c_new[row][i] = '.'
      else:
        for j in range(H):
            c_new[j][row-H] = '.'
    row += 1
    bit = bit>>1
  
  
  count = 0
  for i in range(H):
    for j in range(W):
      if c_new[i][j] == '
        count+=1
  
  if count == K:
    ans+=1

    

print(ans)

Solution (Python):
from itertools import combinations
import numpy as np





h, w, k = map(int, input().split())
c_m = [list(input()) for _ in range(h)]
c_m = np.array(c_m)
result = 0
for i in range(1, h+1):
    chs = list(combinations(range(h), i))
    for ch in chs:
        c_1 = c_m.copy()
        for ch_i in ch:
            c_1[ch_i] = 'r'
        for j in range(1, w+1):
            whs = (combinations(range(w), j))
            for wh in whs:
                c_2 = c_1.copy()
                for wh_i in wh:
                    c_2[:,wh_i] = 'r'
                if np.sum(c_2=='


for i in range(1, h+1):
    chs = list(combinations(range(h), i))
    for ch in chs:
        c_1 = c_m.copy()
        for ch_i in ch:
            c_1[ch_i] = 'r'
        if np.sum(c_1=='

for i in range(1, w+1):
    chs = list(combinations(range(w), i))
    for ch in chs:
        c_1 = c_m.copy()
        for ch_i in ch:
            c_1[:,ch_i] = 'r'
        if np.sum(c_1=='

if np.sum(c_m=='
print(result)

Solution (Python):
H,W,K=map(int,input().split())
import copy
sq=[list(input()) for i in range(H)]
temp=copy.deepcopy(sq)
ans=0
lh=[j for j in range(H)]
lw=[k for k in range(W)]

import itertools
conH=[]
for m in range(1,H+1):
    for conb in itertools.combinations(lh,m):
        conH.append(list(conb))
conW=[]
for n in range(1,W+1):
    for conb2 in itertools.combinations(lw,n):
        conW.append(list(conb2))
conH.append([])
conW.append([])

for o in range(len(conH)):
    for p in range(len(conW)):
        c=0
        sq=copy.deepcopy(temp)
        for q in conH[o]:
            for r in range(W):
                sq[q][r]="!"
        for s in range(H):
            for t in conW[p]:
                sq[s][t]="!"
        for u in range(len(sq)):
            c+=sq[u].count("
        if c==K:
            ans+=1

print(ans)

Solution (Python):
import copy
h,w,aa=map(int,input().split())
s=[input() for _ in range(h)]
t=copy.copy(s)
cnt=0
hs=['.' for _ in range(h)]
hw=['.' for _ in range(w)]
for i in range(2**h):
    b=bin(i)[2:]
    if len(b)<h:
        b=str("0"*(h-len(b)))+b
    
    for j in range(2**w):
        c=bin(j)[2:]
        if len(c)<w:
            c=str("0"*(w-len(c)))+c
        
        t=copy.copy(s)
        
        for k in range(len(b)):


            if b[k]=="1":
                t[k]=hw
        

        o=[]
        t= [list(x) for x in zip(*t)]
        
        for l in range(len(c)):
            
            if c[l]=="1":
                t[l]=hs
        for m in range(len(t)):
            o.extend(t[m])
        

        on=o.count("
        if on==aa:
            cnt+=1
            










print(cnt)

Solution (Python):
import sys
import itertools

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    
    H, W, K = MI()
    c = [0 for i in range(H)]
    for i in range(H):
        q = str(input())
        c[i] = list(q)
    ans = 0

    numh = list(range(H))
    numw = list(range(W))
    for i in range(H):
        for h_kumi in itertools.combinations(numh,i):
            h_kumi = list(h_kumi)
            
            for j in range(W):
                for w_kumi in itertools.combinations(numw,j):
                    w_kumi = list(w_kumi)
                    
                    c_blk = 0


                    if (not h_kumi) and (not w_kumi):
                        for x in numh:
                            for y in numw:
                                if c[x][y] == "
                                    c_blk += 1
                    elif not h_kumi:
                        for x in numh:
                            for y in w_kumi:
                                if c[x][y] == "
                                    c_blk += 1


                    elif not w_kumi:
                        for x in h_kumi:
                            for y in numw:
                                if c[x][y] == "
                                    c_blk += 1

                    else:
                        for x in h_kumi:
                            for y in w_kumi:
                                if c[x][y] == "
                                    c_blk += 1


                    if c_blk == K:
                        ans += 1
                        



    print(ans)
    
    
    

if __name__ == "__main__":
	main()

Solution (Python):
import copy
from itertools import combinations
h, w, k = map(int, input().split())
c =[input() for i in range(h)]
ans = 0
y = []
for i in range(h):
    y.append(i)
x = []
for i in range(w):
    x.append(i)
for i in range(h+1):
    ty = list(combinations(y, i))
    for j in range(w+1):
        tx = list(combinations(x, j))
        for l in ty:
            for m in tx:
                cnt = 0
                for p in l:
                    for q in m:
                        if c[p][q] == '
                            cnt += 1
                if cnt == k:
                    ans += 1
print(ans)

Solution (Python):
H, W, K= map(int, input().split())
lst = []
for _ in range(H):
    lst.append(list(str(input())))

ans = 0
for i in range(2**H):
    for j in range(2**W):
        temp =[]
        c = 0
        for h in range(H):
            if (i >> h) & 1:
                temp.append(lst[_])
                for w in range(W):
                    if (j >> w) & 1:
                        if lst[h][w] == '
                            c +=1
        if c == K:
            ans += 1
print(ans)

Solution (Python):
from itertools import product
H,W,K=map(int,input().split())
c = [list(input()) for _ in range(H)]

ans=0
fh = list(product([True,False],repeat=H))
fw = list(product([True,False],repeat=W))


for s in fh:
    for t in fw:
        
        tmp=0
        for i in range(H):
            for j in range(W):
                if c[i][j]=="
                    tmp +=1
                    
        if tmp==K:
            ans +=1
            
                    
print(ans)