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

def paint_h(h, w, t):
    for i in range(w):
        t[h][i] = ' '

def paint_v(h, w, t):
    for i in range(h):
        t[i][w] = ' '

def count_b(h, w, t):
    total = 0
    for i in range(h):
        for j in range(w):
            if t[i][j] == '
                total += 1
    return total


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

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

count = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        t = copy.deepcopy(m)
        
        for a in range(h):
            if i & (2 ** a) == (2 ** a):
                paint_h(a, w, t)
        for a in range(w):
            if j & (2 ** a) == (2 ** a):
                paint_v(h, a, t)
        
        if k == count_b(h, w, t):
            count += 1

print(count)

Solution (Python):
import copy
ans=0
h,w,k=map(int,input().split())
cc=[list(input()) for i in range(h)]
for bit in range(1 << h):
  ccc=copy.deepcopy(cc)
  for i in range(h):
    if bit & (1 << i):
       ccc[i]=["!"]*w 
  for bit in range(1 << w):
    cccc=copy.deepcopy(ccc)
    for i in range(w):
      if bit & (1 << i):
        for j in range(h):
          cccc[j][i]="!"
    count0=0
    for i in range(h):
      count0+=cccc[i].count("
    if count0==k:
      ans+=1
print(ans)

Solution (Python):
from itertools import combinations, chain, product

H, W, K = map(int, input().split())
board = [input() for _ in range(H)]

h_patterns = list(chain.from_iterable([set(combinations(range(H), i)) for i in range(H+1)]))
w_patterns = list(chain.from_iterable([set(combinations(range(W), i)) for i in range(W+1)]))

ans = 0
for h_pattern, w_pattern in product(h_patterns, w_patterns):
    
    count = 0
    for i in range(H):
        for j in range(W):
            if i in h_pattern or j in w_pattern:
                continue
            if board[i][j] == '
                count += 1
    
    if count == K:
        ans += 1
print(ans)

Solution (Python):
import copy


def main():
    H, W, K = input_ints()

    c = []

    count = 0

    for _ in range(H):
        s = input()
        li = []
        for chara in s:
            li.append(chara == '

        c.append(li)

    for i in range(2 ** (H+W)):
        c2 = copy.deepcopy(c)

        for j in range(W):
            if (i >> j) & 1:
                for k in range(H):
                    c2[k][j] = False

        for j in range(H):
            if (i >> (j+W)) & 1:
                for k in range(W):
                    c2[j][k] = False

        black = 0
        for i in range(H):
            for j in range(W):
                if c2[i][j]:
                    black += 1

        if black == K:
            count += 1

    print(count)


def input_ints():
    line_list = input().split()

    if len(line_list) == 1:
        return int(line_list[0])
    else:
        return map(int, line_list)


def input_int_list_in_line():
    return list(map(int, input().split()))


def input_int_tuple_list(n: int):
    return [tuple(map(int, input().split())) for _ in range(n)]


main()

Solution (Python):
H,W,K=map(int,input().split())
C=[input() for i in range(H)]
count=0
for i in range(2**(H+W)):
    tate=[]
    yoko=[]
    for j in range(W):
        if ((i >> j)&1)==True:
            for k in range(H):
                tate.append((k,j))
    for j in range(W,H+W):
        if ((i >> j)&1)==True:
            for k in range(W):
                yoko.append((j-W,k))
    kyo=set(tate) & set(yoko)
    itti=0
    if len(kyo)!=0:
        for items in kyo:
            if C[items[0]][items[1]]=="
                itti+=1
        if itti==K:
            count+=1
print(count)

Solution (Python):
import numpy as np
h, w, k = map(int, input().strip().split())
cs = [list(input().strip()) for _ in range(h)]
grid = np.zeros((h, w), dtype=np.int)
for i, row in enumerate(cs):
    for j, cell in enumerate(row):
        if cell == '
            grid[i, j] = 1


def count_black(grid, bits_row, bits_col):
    mask = np.ones((h, w), dtype=np.int)
    for i in range(h):
        bit = bits_row >> i & 1
        if bit:
            mask[i] = 0
    for j in range(w):
        bit = bits_col >> j & 1
        if bit:
            mask[:, j] = 0

    return np.sum(grid * mask)

count = 0
for b_row in range(2 ** h):
    for b_col in range(2 ** w):
        c = count_black(grid, b_row, b_col)
        if c == k:
            count += 1

print(count)

Solution (Python):
from itertools import product

H, W, K = map(int, input().split(' '))
maze = [input() for i in range(H)]
ans = 0
cnt = 0
for i in range(pow(2,H+W)):
    cnt += 1
    i = format(i,'0{}b'.format(H+W))
    h = list(i[:H])
    w = list(i[H:])
    tmp = 0
    for j in range(H):
        for k in range(W):

            if h[j] == w[k] == '0' and maze[j][k] == '
                tmp += 1
    if tmp == K:
        ans += 1
print(ans)

Solution (Python):
import copy

h, w, k = map(int, input().split())
cs = []
ans = 0

def count_sharps(tmp):
  sharp = 0
  for y in range(h):
    sharp += tmp[y].count("
  if sharp == k:
    return True
  else:
    return False



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

for i in range(2 ** h):
  for j in range(2 ** w):
    tmp = copy.deepcopy(cs)
    for p in range(h):
      if ((i >> p) & 1):
        for x in range(w):
          tmp[p][x] = "r"
    for q in range(w):
      if ((j >> q) & 1):
        for y in range(h):
          tmp[y][q] = "r"

    if count_sharps(tmp):
      ans += 1

print(ans)

Solution (Python):


import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))

from copy import deepcopy
def resolve():
    H,W,K=pin()
    maze=[list(input()) for a in range(H)]


    
    ans=0
    for i in range(2**H):
        for j in range(2**W):
            
            notred=[]
            numh=[0]*W
            
            for ci in range(H):
                check=1<<ci
                if i & check:
                    
                    for k in range(W):
                        if maze[ci][k]=="
                            numh[k]+=1

            cal=0
            for cj in range(W):
                check=1<<cj
                if j & check:
                    cal+=numh[cj]
            if cal==K:ans+=1
    print(ans)


resolve()

Solution (Python):
import sys
readline = sys.stdin.readline

H, W, K = map(int, readline().split())
L = []
s = 0
for i in range(H):
  li = readline().strip()
  Li = []
  for j in range(W):
    if li[j] == "
      s += 1
      Li.append(1)
    else:
      Li.append(0)
  L.append(Li)
if s < K:
  print(0)
  exit()

h0 = ""
w0 = ""
for i in range(H):
  h0 += "0"
for i in range(W):
  w0 += "0"
h = 2**H
w = 2**W
ans = 0
for i in range(h):
  hi = (h0 + bin(i)[2:])[-H:]
  for j in range(w):
    wj  = (w0 + bin(j)[2:])[-W:]
    sij = 0
    for k in range(H):
      for l in range(W):
        if hi[k] != "1" and wj[l] != "1":
          sij += L[k][l]
    if sij == K:
      ans += 1
print(ans)

Solution (Python):
import numpy as np





def main():
    H,W,K = map(int, input().split())
    C = np.zeros((H,W), dtype='int8')
    for h in range(H):
        s = input()
        for i in range(len(s)):
            if s[i] == '.':
                C[h,i] = 0
            else:
                C[h,i] = 1

    t2 = 0
    count = 0
    while t2 < 2**(H+W):
        t = t2
        h = []
        w = []
        for i in range(H+W):
            if t&1 == 1:
                if i < H:
                    h += i,
                else:
                    w += (i-H),
            t = t >> 1
        a = np.delete(np.delete(C, h, 0), w, 1)
        c = np.count_nonzero(np.delete(np.delete(C, h, 0), w, 1))
        if c == K:
            count += 1
        t2+=1

    print(count)


main()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    H, W, K = map(int, input().split())
    field = ['' for _ in range(H)]
    for i in range(H):
        field[i] = input().rstrip()
    num_black = 0
    for i in range(H):
        for j in range(W):
            if field[i][j] == '
                num_black += 1
    ans = 0
    for bit in range(2**(H+W)):
        current = 'h'
        target_h = []
        target_w = []
        for i in range(H+W):
            if i < H:
                current = 'h'
            else:
                current = 'w'
            if bit & 1<<i:
                ord = i
                if current == 'w':
                    ord = i - H
                if current == 'h':
                    target_h.append(ord)
                else:
                    target_w.append(ord)
        cnt = 0
        for j in range(H):
            for k in range(W):
                if j in target_h or k in target_w:
                    if field[j][k] == '
                        cnt += 1
        if num_black - cnt == K:
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
from decimal import *

import numpy as np

import math

import collections
import itertools


def createmaiz(listh,listw,list):
    for i in range(h):
        if listh[i] == "1":
            for j in range(w):
                list[i][j] ="."
    for i in range(w):
        if listw[i] == "1":
            for j in range(h):
                list[j][i] ="."
    return  list


def calc(maiz):
    count = 0
    for i in maiz:
        for j in i:
            if j =="
                count +=1
    return count


if __name__ == '__main__':
    h,w,k = map(int, input().split())
    maiz = []
    for i in range(h):
        s = input()
        maiz.append(list(s))

    listh=[]
    for i  in itertools.product('01', repeat=h):
        listh.append(list(i))
    listw=[]
    for i in itertools.product('01', repeat=w):
        listw.append(list(i))
    ans = 0

    for i in listh:
        for j in listw:
            temp = copy.deepcopy(maiz)
            temp =createmaiz(i,j,temp)
            black = calc(temp)
            if black ==k:
                ans+=1
    print(ans)

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

ans=0

for i in range(2 ** H):
    CM = copy.deepcopy(M)
    for j in range(H):  
        if ((i >> j) & 1):  
            for k in range(W):
                CM[j][k] = '.'
    for l in range(2 ** W):
        CCM = copy.deepcopy(CM)
        for m in range(W):
            if ((l >> m) & 1):
                for n in range(H):
                    CCM[n][m]='.'
        cnt = 0
        for n in range(H):
            for m in range (W):
                if CCM[n][m] == '
                    cnt += 1
        if cnt == K:
            ans+=1

print(ans)

Solution (Python):
h,w,k=map(int,input().split())
a=[[]*w for ii in range(h)]
for ii in range(h):
  a[ii][:]=list(input())
"""
for ii in range(h):
  print(a[ii])
"""
def func(a,bmh,bmw):
  rr=0
  for ii in range(h):
    for jj in range(w):
      if rr>k:
        return(0)
      
      if ((2**ii)&bmh)!=0:
        if ((2**jj)&bmw)!=0:
          
          if a[ii][jj]=="
            rr+=1
  
  if rr==k:
    return(1)
  else:
    return(0)
  
bh=2**h
bw=2**w
r=0

for ii in range(bh):
  for jj in range(bw):
    
    r+=func(a,ii,jj)
print(r)

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

def generate_n_bit(n):
    bins= []
    for i in range(2**n):
        bins.append(list(str(format(i,'b').zfill(n))))
    
    return bins

h_all = generate_n_bit(h)
w_all = generate_n_bit(w)
ans = 0

field = [list(input()) for i in range(h)]

for i_l in h_all:
    for j_l in w_all:
        c  = 0 
        fields = copy.deepcopy(field)
       
        
        for i_i, i in enumerate(i_l):
            for j_i, j in enumerate(j_l):
            
                if i == '1':
                    for a in range(w):
                        fields[i_i][a] = 'r'
                    
                if j == '1':
                    for b in range(h):
                        fields[b][j_i] = 'r'
        
        for q in range(h):
            for e in range(w):
                if fields[q][e] == '
                    c += 1
       
        if c == k:
            ans += 1
        
        
                
print(ans)

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

ans = 0
'それぞれの選び方について'
for i in range(2 ** H):
    for j in range(2 ** W):
        cnt = 0
        for l in range(H):
            for m in range(W):
                if ((i >> l) & 1) and ((j >> m) & 1):
                    if maze[l][m] == '
                        cnt += 1
        if cnt == K:
            ans += 1
print(ans)

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

A = 0
for bit in range(2 ** H):
    D = deepcopy(c)
    for i in range(H):
        if (bit & (1 << i)):
            for k in range(W):
                D[i][k] = '.'
    for bit2 in range(2 ** W):
        E = deepcopy(D)
        for j in range(W):
            if (bit2 & (1 << j)):
                for k in range(H):
                    E[k][j] = '.'
        X = 0
        for k in range(H):
            X += E[k].count('
        if X == K:
            A += 1

print(A)

Solution (Python):


import numpy as np

def funk(matrix, n, k, no_list, h, w):
    if n == 0:
        mask = np.ones((h, w))
        for i in range(h):
            if no_list[i] == 1:
                mask[i,] = 0
        for j in range(w):
            if no_list[h+j] == 1:
                mask[:,j] = 0
        if np.sum(matrix * mask) == k:
            return 1
        else:
            return 0
    ans = 0
    ans += funk(matrix, n - 1, k, no_list + [1], h, w)
    ans += funk(matrix, n - 1, k, no_list + [0], h, w)
    return ans

ans = 0
h, w, k = map(int, input().split())
n = h + w
matrix = np.zeros((h, w))
for i in range(h):
    line = input()
    for j in range(w):
        if line[j] == "
            matrix[i,j] = 1
        else:
            matrix[i,j] = 0
no_list = []
ans += funk(matrix, n, k, no_list, h, w)
print(ans)

Solution (Python):
import math
import bisect
import copy

import itertools



l=[]
h,w,k=map(int,input().split())
for i in range(h):
	l.append(list(input()))

ccc=0
black=0
bl=0
for i in range(h):
	for j in range(w):
		if l[i][j]=='
			bl+=1

a=[i for i in range(64)]
b=[i for i in range(64)]
c=list(itertools.product(a,b))
for i in range(len(c)):
	a1=bin(c[i][0])[2:]
	b1=bin(c[i][1])[2:]
	if len(a1)>h:
		continue
	if len(b1)>w:
		continue
	if len(a1)<h:
		a1='0'*(h-len(a1))+a1
	if len(b1)<w:
		b1='0'*(w-len(b1))+b1
	row=0
	col=0
	for i in range(h):
		if a1[i]=='0':
			continue
		for j in range(w):
			if l[i][j]=='
				row+=1

	for i in range(w):
		if b1[i]=='0':
			continue
		for j in range(h):
			if l[j][i]=='
				col+=1
	if row+col==bl-k:
		ccc+=1

print(ccc)

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

hw_lst = [0 for i in range(h+w)]
lst_map = []
for i in range(h):
  lst_map.append(list(input()))
ans = [0]

def dfs(i, lst, aa):
  if i == h+w:
    count = 0
    for ij in range(h):
      for j in range(w):
        if lst[ij] == 0 and lst[h+j] == 0 and lst_map[ij][j] == '
          count += 1
    if count == k:
      aa[0] += 1
    return

  a = lst.copy()
  dfs(i+1, a, aa)
  b = lst.copy()
  b[i] = 1
  dfs(i+1, b, aa)

dfs(0, hw_lst, ans)
print(ans[0])

Solution (Python):
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
import copy

h, w, K = map(int, sys.stdin.readline().split())



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

ans = 0
for i in range(2**(h+w)):
    b = format(i, "0"+str(h+w)+"b")
    m = copy.deepcopy(l)
    for j in range(h):
        if b[j] == "1":
            for k in range(w):
                m[j][k] = "R"

    for j in range(w):
        if b[h+j] == "1":
            for k in range(h):
                m[k][j] = "R"

    cnt = 0
    for j in range(h):
        for k in range(w):
            if m[j][k] == "
                cnt += 1



    if cnt == K:
        ans += 1


print(ans)

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

import itertools
h = list(itertools.product([0,1], repeat=H))
w = list(itertools.product([0,1], repeat=W))

ans = 0
for i in h:
    for j in w:
        tmp = 0
        for ii in range(H):
            for jj in range(W):
                if C[ii][jj] == '
                    tmp += 1
        if tmp == K:
            ans += 1
            
print(ans)

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

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

C = np.array(C)
C = np.where(C == '.', 0, C)
C = np.where(C == '
C = C.astype(np.int)

ans = 0

for h_bits in product(*[range(2) for _ in range(H)]):
    ch = C.copy()
    for i,h in enumerate(h_bits):
        if h == 1:
            ch[i] = 0
    for w_bits in product(*[range(2) for _ in range(W)]):
        cw = ch.copy()
        for j,w in enumerate(w_bits):
            if w == 1:
                cw[:,j] = 0
        if cw.sum() == K:
            ans += 1

print(ans)

Solution (Python):
from itertools import combinations

def main(H, W, K, HW):
    ans = 0

    
    n_all = sum(HW, []).count('

    
    comb_h = []
    comb_w = []
    for h in range(H):
        comb_h.extend(combinations([i for i in range(H)], h))
    for w in range(W):
        comb_w.extend(combinations([i for i in range(W)], w))

    
    for c_h in comb_h:
        n_h = 0
        for h in c_h:
            n_h += HW[h].count('

        
        for c_w in comb_w:
            n_w = 0
            n_hw = 0
            for w in c_w:
                for h in range(H):
                    if HW[h][w] == '
                        n_w += 1
                        if h in c_h:
                            n_hw += 1
            
            n_black = n_all - n_h - n_w + n_hw
            if n_black == K:
                ans += 1
    print(ans)

if __name__ == '__main__':
    H, W, K = list(map(int, input().split()))
    HW = []
    for h in range(H):
        HW.append(list(input()))
    main(H, W, K, HW)

Solution (Python):
def func ( L00 , x0 , H  , W  , K , c0 ) :

	if sum(L00) == K :
		c0[0] += 1 ; 

	for r in range ( x0 , H + W ) : 

		if r >= H :
			y = r - H 
			L =L00[:];
			for c in range ( H ) :
				if L[ c * W + y ] == 1 :
					L[c * W + y ] = 0 ;
			func ( L , r+1 , H , W , K , c0 ) ;

		else :
			L =L00[:];
			for c in range ( W ) :
				if L[r * W + c] == 1 :
					L[r  * W + c ] = 0 ;
			func ( L , r+1 , H , W , K , c0 ) ;




	


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

L00 = [] ;
for x in range ( H ) :
	for c in input().strip() :
		if c =='
			L00.append ( 1 ) ;
		else :
			L00.append ( 0 ) ;

c0 = [0] ;
func ( L00 , 0 , H , W , K , c0 ) ;
print ( c0[0] ) ;

Solution (Python):
H,W,K=map(int,input().split())
import numpy as np
import copy
c=[]
for i in range(H):
  c.append(list(input().replace('.','0').replace('

def count(xdel,ydel,l):
  cnt=0
  for i in range(H):
      for j in range(W):
        if 2**i&ydel!=0 or 2**j&xdel!=0:
          l[i][j]=2
        if l[i][j]=='1':
          cnt+=1
          l[i][j]=1
        
  return cnt

result=0
for i in range(2**H):
  for j in range(2**W):
    l=copy.deepcopy(c)
    if count(j,i,l)==K:
      result+=1
print(result)

Solution (Python):
import math
import collections
import bisect
from copy import copy, deepcopy


def main():
    H, W, K = map(int, input().split())
    c = [None] * H
    for i in range(H):
        c[i] = list(input())

    ans = 0
    for i in range(2**(H)):
        c_ = deepcopy(c)
        for j in range(H):
            if((i >> j) & 1):
                for k in range(W):
                    c_[j][k] = "."
        for j in range(2**(W)):
            c__ = deepcopy(c_)
            for k in range(W):
                if((j >> k) & 1):
                    for l in range(H):
                        c__[l][k] = "."
            if K == sum(list(map(lambda x: x.count("
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
h, w, k = map(int, input().split())
c = []
for i in range(h):
  c.append(input())

ans = 0
for ht in range(1 << h):
  for wt in range(1 << w):
    b = 0
    for i in range(h):
      
      if ht & 1 << i:
        continue
      for j in range(w):
        
        if wt & 1 << j:
          continue
        if c[i][j] == '
          b += 1
    if (b == k):
      ans += 1
print(ans)

Solution (Python):
def tw(n,x):
  r=[0]*x
  i=0
  while (n>=2 and i<x-1):
    r[i]=n%2
    n=int(n/2)
    i+=1
  r[i]=n%2
  return r

H,W,K=input().split()
H,W,K=int(H),int(W),int(K)
c2=["."*W]*H

for i in range(H): 
  tmp=input()
  
  c2[i]=str(tmp)


a=2**(H+W)
cnt=0
for i in range(a):
  lis=tw(i,a)
  c=c2[:]
  for j in range(H):
    if lis[j]==1: c[j]="a"*W
  for j in range(W):
    if lis[H+j]==1: 
      for k in range(H): c[k]=c[k][:j]+"a"+c[k][j+1:]
  cnt2=0
  for s in range(H):
    for t in range(W):
      if c[s][t]=="
  
  if cnt2==K: cnt+=1
print(cnt)

Solution (Python):
h, w, k = map(int, input().split())
c = [''] * h
for i in range(h):
    c[i] = list(input())

ans = 0

for i in range(2 ** (h + w)):
    white = 0
    wi = []
    he = []

    for j in range(h + w):
        if ((i >> j) & 1):
            if j < w:
                wi.append(j)
            else:
                he.append(j - w)

    for hei in range(h):
        for wid in range(w):
            if (not hei in he) and (not wid in wi) and c[hei][wid] == '
                white += 1

    if white == k:
        ans += 1

print(ans)

Solution (Python):
from copy import deepcopy
import numpy as np

def paint_red(array, rows, cols):
    ret = deepcopy(array)
    for i in rows:
        ret[i, :] = "r"
    for j in cols:
        ret[:, j] = "r"

    return ret

def get_idx(bins):
    indices = []
    for i, c in enumerate(reversed(bins)):
        if c == "1":
            indices.append(i)
    
    return indices

def is_terminated(array, n_blacks):
    actual_number = 0
    for i in range(array.shape[0]):
        for j in range(array.shape[1]):
            if array[i, j] == "
                actual_number += 1
    return n_blacks == actual_number

H, W, K = [int(x) for x in input().split()]
c = []
for i in range(H):
    row = [x for x in input()]
    c.append(row)
c = np.array(c)

n_solutions = 0
for counter in range(2 ** (H + W)):
    bins = bin(counter)[2:].zfill(H + W)
    rows = get_idx(bins[:H])
    cols = get_idx(bins[H:])

    painted = paint_red(c, rows, cols)
    if is_terminated(painted, K):
        n_solutions += 1

print(n_solutions)

Solution (Python):
import itertools
import copy
H, W, K = map(int, input().split())

c = []
for i in range(H):
    c.append(input())
a = []
for i in c:
    b = []
    for j in i:
        if j == '
            b.append(1)
        else:
            b.append(0)
    a.append(b)

col = []
r = list(range(H))
for i in range(H+1):
    col += itertools.combinations(r, i)

row = []
r = list(range(W))
for i in range(W+1):
    row += itertools.combinations(r, i)

ans = 0
for i in col:
    for j in row:
        tar = copy.deepcopy(a)
        for k in i:
            tar[k] = [0] * W
        for k in j:
            for t in tar:
                t[k] = 0
        n = 0
        for t in tar:
            for k in t:
                n += k
        if n == K:
            ans += 1

print(ans)

Solution (Python):


import sys
readline=sys.stdin.readline

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

C = [None] * H
for i in range(H):
  C[i] = readline().rstrip()
  
def count_black(C,y,x):
  cnt = 0
  for i in range(H):
    for j in range(W):
      if C[i][j] == ".":
        continue
      
      if y[i] != "1" and x[j] != "1":
        cnt += 1
  return cnt


ans = 0
yketa = len(bin(H)[2:])
xketa = len(bin(W)[2:])

for y in range(2 ** H):
  yst = bin(y)[2:].zfill(H)
  for x in range(2 ** W):
    xst = bin(x)[2:].zfill(W)
    if count_black(C,yst,xst) == K:
      ans += 1
    
print(ans)

Solution (Python):
import sys
import copy
sys.setrecursionlimit(2147483647)

def main():
  H, W, K = map(int, input().split(' '))
  C = []
  for i in range(H):
    C.append(input())
  count = 0
  mani_row = []
  mani_col = []
  for i in range(2**H):
    for j in range(2**W):
      num = 0
      bini = format(i, f'0{H}b')
      binj = format(j, f'0{W}b')
      for h in range(H):
        for w in range(W):
          if(bini[h] == '0' and binj[w] == '0' and C[h][w] == '
            num += 1
      if(num == K):
        count += 1
  print(count)






if __name__=='__main__':
  main()

Solution (Python):
import copy

H, W, K = list(map(int,input().split()))
c = []
for i in range(H):
    c.append(input())
    
red = 0
cc = [[-1 for _ in range(W)] for j in range(H)]
for i in range(W):
    for j in range(H):
        if c[j][i] == ".":  cc[j][i] = 0
        else:  
            cc[j][i] = 1
            red += 1
            
def bit_all(red):
    ans = 0
    for x in range(2 ** W):
        for y in range(2 ** H):
            ccc = copy.deepcopy(cc)
            temp = 0
            b = str(format(x, '010b'))
            c = str(format(y, '010b'))
            
            for i in range(W):
                if b[-(i + 1)] == "1":
                    for ii in range(H):
                        if ccc[ii][i] == 1:
                            ccc[ii][i] = 0
                            temp += 1
                            
            for j in range(H):
                if c[-(j + 1)] == "1":
                    for ii in range(W):
                        if ccc[j][ii] == 1:
                            ccc[j][ii] = 0
                            temp += 1 
                            
            if red - temp == K:
                ans += 1
                
    return ans

ans = bit_all(red)
print(ans)

Solution (Python):
def combinationUtil(arr, n, r, index, data, i):
    global a
    if(index == r):
        tmp = []
        for j in range(r):
            tmp.append(data[j])
            
        a.append(tmp)
        
        return
    if(i >= n): 
        return
    data[index] = arr[i] 
    combinationUtil(arr, n, r, index + 1, data, i + 1) 
    combinationUtil(arr, n, r, index, data, i + 1) 

def printcombination(arr, n, r):
    data = list(range(r)) 
    combinationUtil(arr, n, r, 0, data, 0)

h, w, k = map(int, input().split())
l = []
for i in range(h):
    s = list(input())
    l.append(s)
ans = 0
ro, col = [], []
for i in range(h): ro.append(i)
for i in range(w): col.append(i)


t1 = []
t2 = []
for i in range(h + 1):
    a = []
    printcombination(ro, h, i)
    for j in a: t1.append(j)

for i in range(w + 1):
    a = []
    printcombination(col, w, i)
    for j in a: t2.append(j)





for i in t1:
    for j in t2:
        cnt = 0
        for a in range(h):
            for b in range(w):
                if a in i or b in j: continue
                if l[a][b] == '
        if cnt == k: ans -= -1
print(ans)

Solution (Python):
from collections import Counter
from itertools import product
import numpy as np
from copy import copy
H, W, K, *data = map(str, open(0).read().split())

H = int(H)
W = int (W)
K = int(K)



encoder = dict()
encoder["."] = 0
encoder["

mat = np.zeros([H,W], dtype=int)
for i, row_raw in enumerate(data):
    row = [encoder[char] for char in row_raw]
    mat[i,:] = row

counter = 0
for H_red in product([True, False], repeat=H):
    for W_red in product([True, False], repeat=W):
        mat_c = copy(mat)
        mat_c[H_red, :] = 0
        mat_c[:, W_red] = 0
        black_count = np.sum(mat_c)
        if black_count == K:
            counter += 1

print(counter)

Solution (Python):
import itertools as itr

def get_val(c, x_list, y_list):
    cnt = 0
    for y in range(len(c)):
        if y_list[y] == 0: 
            for x in range(len(c[y])):
                if (x_list[x] == 0) and (c[y][x] == '
                    cnt += 1
    return (cnt)

h,w,k = list(map(int,input().split(' ')))

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

ans = 0
for y in list(itr.product([0,1], repeat=h)):
    for x in list(itr.product([0,1], repeat=w)):
        if get_val(c_tmp, x, y) == k:
            ans += 1
print(ans)

Solution (Python):
h, w, k = map(int, input().split())
c = [[] for _ in range(h)]
count = 0

for i in range(h):
  c_now = input()
  c[i] = [0 if cc=="." else 1 for cc in c_now]
  
  

for i in range(2**h):
  ii = bin(i)[2:].zfill(h)
  for j in range(2**w):
    jj = bin(j)[2:].zfill(w)
    
    count_now = 0
    for hh in range(h):
      if(ii[hh] == '1'):
        continue
      
      for ww in range(w):
        if(jj[ww] == '1'):
          continue
        if(c[hh][ww] == 1):
          count_now += 1
    if(count_now == k):
      count += 1
        
print(count)

Solution (Python):
import copy
h,w,k = list(map(int,input().split()))
hw_origin = [[0]*w for i in range(h)]
for i in range(h) :
    c = input()
    for j in range(w) :
        hw_origin[i][j] = c[j]

ans = 0
for i in range(2**h) :
    for j in range(2**w) :
        hw = copy.deepcopy(hw_origin)
        for l in range(h) :
            if (i>>l)&1 :
                for m in range(w) :
                    hw[l][m] = 1
        for m in range(w) :
            if (j>>m)&1 :
                for l in range(h) :
                    hw[l][m] = 1
        countb = 0
        for l in range(h) :
            for m in range(w) :
                if hw[l][m] == '
                    countb += 1
        if countb == k :
            ans += 1

print(ans)