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 itertools


def count_black(row, col):
    count = 0
    for i, x in enumerate(row):
        for j, y in enumerate(col):
            if x == 0 and y == 0:
                if C[i][j] == "
                    count += 1
    return count


if __name__ == "__main__":
    H, W, K = [int(x) for x in input().split(" ")]
    C = []
    for _ in range(H):
        c = [s for s in input()]
        C.append(c)
    
    ans = 0
    for row in itertools.product([0, 1], repeat=H):
        for col in itertools.product([0, 1], repeat=W):
            if count_black(row, col) == K:
                ans += 1
    print(ans)

Solution (Python):
def main():
    h, w, target = map(int, input().split())
    inlis = []
    for _ in range(h):
        clis = input()
        inlis.append(clis)
    ans = 0
    
    for i in range(2 ** h):
            for k in range(2 ** w):
                tmp = 0
                for l in range(w):
                    for j in range(h):   
                        if ((i >> j) & 1) and ((k >> l) & 1) and inlis[j][l] == "
                            tmp += 1
                if tmp == target:
                    ans += 1
                    
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
h, w, k=map(int, input().split())
l = [[] for _ in range(h)]
for _ in range(h):
  s=str(input())
  for o in s:
    if o=="
      l[_].append(1)
    else:
      l[_].append(0)
import numpy as np
l=np.array(l)
cnt=0

from itertools import product
s = [0,1]
for v1 in sorted(list(product(s, repeat=h)), reverse=1):
  for v2 in sorted(list(product(s, repeat=w)), reverse=1):
    lcal=l
    v1a=[]
    for i in v1:
      v1a.append([i])
    v1a=np.array(v1a)
    v2a=np.array(v2)
    lcal=v2a*lcal
    lcal=v1a*lcal
    if sum(sum(lcal))==k:
      cnt+=1
print(cnt)

Solution (Python):


"""
Created on Sun May  3 16:22:00 2020

@author: neb0123
"""

import itertools

def solution(A,n,m,k):
	cnt = 0
	for i in range(n+1):
		R = list(itertools.combinations(range(n),i))
		for row in R:
			for j in range(m+1):
				C = list(itertools.combinations(range(m),j))
				for column in C:
					B = [A[i][:] for i in range(n)]
					s = 0
					for r in row:
						B[r] = ['.' for _ in range(m)]
					for c in column:
						for ro in range(n):
							B[ro][c] = '.'
					for r in B:
						for p in r:
							if p == '
								s += 1
					if s == k:
						cnt += 1
	return cnt


if __name__ == "__main__":
	n,m,k = map(int, input().split(' '))
	A = []
	for _ in range(n):
		A.append(list(input()))
	print(solution(A,n,m,k))

Solution (Python):
import sys
def input():
    return sys.stdin.readline().rstrip('\n')
    

def calc(H, W, K, C):
    ans = 0
    for ph in range(2 ** H):
        sh = format(ph, '0{0}b'.format(H))
        for pw in range(2 ** W):
            sw = format(pw, '0{0}b'.format(W))
            n = 0
            for i in range(H):
                if sh[i] == '1':
                    for j in range(W):
                        if sw[j] == '1':
                            n += (1 if C[i][j] == '
            if n == K:
                ans += 1
    return ans


(H, W, K) = tuple([int(s) for s in input().split()])
C = [list(input()) for _ in range(H)]
print(calc(H, W, K, C))

Solution (Python):
import itertools
import copy
def main():
    H, W, K = map(int, input().split())
    board = [list(input()) for i in range(H)]
    ans = 0

    for i in range(H + 1):
        for j in range(W + 1):
            for row in itertools.combinations(range(H), i):
                for col in itertools.combinations(range(W), j):

                    paint = copy.deepcopy(board)
                    
                    if len(row) == 0:
                        pass
                    else:
                        for r in row:
                            for k in range(W):
                                paint[r][k] = "-"

                    if len(col) == 0:
                        pass
                    else:
                        for c in col:
                            for l in range(H):
                                paint[l][c] = "-"

                    count = 0
                    for k in range(H):
                        for l in range(W):
                            if paint[k][l] == "
                                count += 1

                    if count == K:
                        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import copy

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

hw = []
for _ in range(H):
    tmp = list(input())
    hw.append(tmp)

ans = 0
for hi in range(2**H):
    tmp_hw = copy.deepcopy(hw)
    for hj in range(H):
        if ((hi >> hj) & 1):
            
            for i in range(W):
                tmp_hw[hj][i] = 'x'

    tmp_cnt = 0
    for i in range(H):
        tmp_cnt += tmp_hw[i].count('
    if tmp_cnt < K:
        continue

    for wi in range(2**W):
        tmp_hw2 = copy.deepcopy(tmp_hw)
        for wj in range(W):
            if ((wi >> wj) & 1):
                
                for i in range(H):
                    tmp_hw2[i][wj] = 'x'
        cnt = 0
        for i in range(H):
            cnt += tmp_hw2[i].count('
        if cnt == K:
            ans += 1
print(ans)

Solution (Python):
import itertools
import copy
h, w, k = list(map(int, input().split()))
maze = []
for i in range(h):
  li = []
  tmp = input()
  for j in range(w):
    li.append(tmp[j])
  maze.append(li)

h_total_li = list(itertools.product([1, 0], repeat=h))
w_total_li = list(itertools.product([1, 0], repeat=w))
ans = 0
for h_val in h_total_li:
  for w_val in w_total_li:
    now = 0
    tmp_maze = copy.deepcopy(maze)
    for h_ind, each_h in enumerate(h_val):
      if each_h == 1:
        for i in range(w):
          tmp_maze[h_ind][i] = 1
    for w_ind, each_w in enumerate(w_val):
      if each_w == 1:
        for i in range(h):
          tmp_maze[i][w_ind] = 1

    for i in range(h):
      for j in range(w):
        if (tmp_maze[i][j] == '
          now += 1

    if now == k:
      ans += 1

print(ans)

Solution (Python):
def solve(C,H,W,tate,yoko,sum):
    for h in range(H):
        if 2**h & tate != 0:
            for w in range(W):
                if C[h][w] == "
                    sum -= 1

    for w in range(W):
        if 2**w & yoko != 0:
            for h in range(H):
                if C[h][w] == "
                    sum -= 1

    for h in range(H):
        for w in range(W):
            if 2**h & tate != 0 and 2**w & yoko != 0 and C[h][w] == "
                sum += 1

    return sum

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

    sum,ans = 0,0
    for h in range(H):
        for w in range(W):
            if C[h][w] == "
                sum += 1

    for i in range(2**H):
        for j in range(2**W):
            if solve(C,H,W,i,j,sum) == K:
                ans += 1

    print(ans)

if __name__ == "__main__":
    main()

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

sl=[]
for i in range(H):
    s=input()
    sl.append(s)

sh=list(range(H))
sw=list(range(W))

cnt=0

for i in range(H+1):
    for sqh in itertools.combinations(sh,i):
        for j in range(W+1):
            for sqw in itertools.combinations(sw,j):
                bcnt=0
                
                for k in range(H):
                    for l in range(W):
                        if k not in sqh and l not in sqw:
                            if sl[k][l]=="
                                bcnt+=1
                
                if bcnt==K:
                    cnt+=1

print(cnt)

Solution (Python):
import copy
h,w,v=map(int,input().split())
c=[list(input()) for _ in range(h)]
ans=0
for i in range(2**w):
  a=copy.deepcopy(c)
  tr1=bin(i)[2:].zfill(w)
  for k in range(w):
    if tr1[k]=='1':
      for l in range(h):
        a[l][k]='.'   
  for j in range(2**h):
    tr2=bin(j)[2:].zfill(h)
    cnt=0
    for k in range(h):
      if tr2[k]=='1':
          cnt+=a[k].count('
    if cnt==v:ans+=1
print(ans)

Solution (Python):
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  
    to_index = lambda x: int(x) - 1  
    print_list_in_2D = lambda x: print(*x, sep="\n")  

    
    def input_int():
        return int(input())

    def map_int_input():
        return map(int, input())

    MII = map_int_input

    def MII_split():
        return map(int, input().split())

    def MII_to_index():
        return map(to_index, input())

    def MII_split_to_index():
        return map(to_index, input().split())

    
    def list_int_inputs():
        return list(map(int, input()))

    LII = list_int_inputs

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

    
    def LII_2D(rows_number):
        return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number):
        return [LII_split() for _ in range(rows_number)]

    import itertools
    import copy

    H, W, K = MII_split()
    field = [input() for _ in range(H)]

    

    ans = 0
    rows = [i for i in range(H)]
    cols = [i for i in range(W)]
    for row_num in range(H + 1):
        for col_num in range(W + 1):
            
            for paint_rows in itertools.combinations(rows, row_num):
                for paint_cols in itertools.combinations(cols, col_num):
                    tmp_field = copy.deepcopy(field)
                    blacks = 0
                    for i, row in enumerate(tmp_field):
                        if i in paint_rows:
                            continue
                        for j, col in enumerate(row):
                            if j in paint_cols:
                                continue
                            if col == '
                                blacks += 1
                    if blacks == K:
                        ans += 1
    print(ans)
resolve()

Solution (Python):
H,W,K = map(int,input().split())
listc = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == ".":
            listc[i][j] = 0
        else:
            listc[i][j] = 1

ans = 0

for i in range(2**H):
    l = i
    tmp = []
    for j in range(H-1,-1,-1):
        if l >= (2**j):
            tmp.append(listc[j])
            l -= 2**j
    
    for j in range(2**W):
        h = j
        t = 0
        for k in range(W-1,-1,-1):
            if h >= (2**k):
                for x in range(len(tmp)):
                    t += tmp[x][k]
                h -= 2**k
        
        if t == K:
            ans += 1

print(ans)

Solution (Python):




import sys
input = sys.stdin.readline



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

    res = 0

    for i in range(2**H):
        for j in range(2**W):
            cnt = 0
            for k in range(H):
                for l in range(W):
                    if ((i >> k) & 1) | ((j >> l) & 1):
                        continue
                    if c[k][l] == '
                        cnt += 1
            if cnt == K:
                res += 1

    print(res)



main()

Solution (Python):
h, w, k = map(int, input().split())
c = [list(map(int, list(input().replace('.', '0').replace('
cs = [[0] for _ in range(h)]
y = 0
for i, ci in enumerate(c):
    for j, cij in enumerate(ci):
        cs[i].append(cs[i][-1])
        cs[i][-1] += c[i][j]
    y += cs[i][-1]
ans = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        x = 0
        for ii in range(h):
            if (i >> ii) & 1:
                x += cs[ii][-1]
            else:
                for jj in range(j):
                    if (j >> jj) & 1:
                        x += c[ii][jj]
        ans += (y - x == k)
print(ans)

Solution (Python):
from copy import deepcopy
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = [x.strip() for x in open(0).readlines()]
h, w, k = map(int, X[0].split())
grid_origin = Grid(X[1:])
ans = 0
for i in range(2 ** h):
    grid_tmp = deepcopy(grid_origin.grid)
    Y = [k for k in range(h) if (i >> k) & 1]
    for y in Y:
        grid_tmp[y, :] = 'x'
    
    for j in range(2 ** w):
        grid = deepcopy(grid_tmp)
        X = [k for k in range(w) if (j >> k) & 1]
        for x in X:
            grid[:, x] = 'x'
        ans += np.sum(grid == '
print(ans)

Solution (Python):
def main():
    h, w, k = map(int, input().split())
    c = [list(input()) for _ in range(h)]
    hp, wp = [], []
    def dfs_h(hl):
        if len(hl) == h:
            hp.append(hl)
            return
        dfs_h(hl + [0])
        dfs_h(hl + [1])
    
    def dfs_w(wl):
        if len(wl) == w:
            wp.append(wl)
            return
        dfs_w(wl + [0])
        dfs_w(wl + [1])
    
    dfs_h([])
    dfs_w([])
    
    ans = 0
    for fh in hp:
        for fw in wp:
            num = 0
            for hi, i in enumerate(fh):
                if i == 1:
                    continue
                for wi, j in enumerate(fw):
                    if j == 1:
                        continue
                    if c[hi][wi] == "
                        num += 1
            if num == k:
                ans += 1
    print(ans)
                    
            
            
            

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import deque
from itertools import combinations_with_replacement
from itertools import product
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, W, K = NMI()
    grid = [SI() for _ in range(H)]

    n = H + W
    ans = 0
    for case in range(2**n):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if (case >> i) & 1:
                    if (case >> j + H) & 1:
                        if grid[i][j] == "
                            cnt += 1
        if cnt == K:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

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


ans=0
for i in range(1<<w):
    for j in range(1<<h):
        cnt=0
        for x in range(w):
            for y in range(h):
                if c[y][x]=="
                    if (i>>x)&1==0 and (j>>y)&1==0:
                        cnt+=1

        if cnt==k:
            ans+=1

print(ans)

Solution (Python):
from itertools import product
import copy

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

c_ = [input() for i in range(H)]
c = [[0] * W for i in range(H)]


for i in range(H):
    for j in range(W):
        if c_[i][j] == "
            c[i][j] = 1

ans = 0
for idxs in product(range(2), repeat=H+W):
    tmp_c = copy.deepcopy(c)

    for idx, j in enumerate(idxs):
        if j == 1:
            if idx < H:
                for x in range(W):
                    tmp_c[idx][x] = 0
            else:
                for x in range(H):
                    tmp_c[x][idx-H] = 0

    cnt = 0
    for i in range(H):
        for j in range(W):
            if tmp_c[i][j] == 1:
                cnt += 1
                
    if cnt == K:
        ans += 1

print(ans)

Solution (Python):
import sys

def calc_hash_bool(Len, hash):
    bools = [False] * Len
    for i in range(Len-1, -1, -1):
        remainder = hash %2
        if(remainder==1):
            bools[i] = True
        hash //= 2
    return bools

def calc_combinations(height, width, boards, demand_black):
    """
    縦: 2^6 = 64
    横: 2^6 = 64
    64^2 = 4096通り
    """
    combinations = 0
    
    for hash_h in range(2**height):
        bool_h = calc_hash_bool(height, hash_h)
        for hash_v in range(2**width):
            bool_v = calc_hash_bool(width, hash_v)
            N_black = 0
            for i in range(height):
                for j in range(width):
                    if(bool_h[i]==False and bool_v[j]==False and boards[i][j]=="
                        N_black += 1
            if(N_black==demand_black):
                combinations += 1
    return combinations



if(__name__ == "__main__"):

    height, width, demand_black = map( int, input().strip().split() )

    boards = [ [] for i in range(height) ]
    N_black_total = 0
    for i in range(height):
        Str = input().strip()
        for j in Str:
            boards[i].append(j)
            if(j=="
                N_black_total += 1
    if(N_black_total < demand_black):
        print("0")
    else:
        combinations = calc_combinations(height, width, boards, demand_black)
        print(combinations)

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 0
for p in product([0,1],repeat=H+W):
  cnt = 0
  for i in range(H):
    for j in range(W):
      if S[i][j]=='
        cnt += 1
  if cnt == K:
    ans += 1
print(ans)

Solution (Python):
import itertools
import copy

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

c = list()
for _ in range(H):
    c.append(list(input()))

ns = [i for i in range(H + W)]

res = 0
for n in range(H + W + 1):
    for tup in itertools.combinations(ns, n):
        _c = copy.deepcopy(c)
        for r in tup:
            if r < H:
                for w in range(W):
                    _c[r][w] = '-'
            else:
                for h in range(H):
                    _c[h][r - H] = '-'
        count = 0
        for h in range(H):
            for w in range(W):
                if _c[h][w] == '
                    count += 1

        if count == K:
            res += 1

print(res)

Solution (Python):
H,W,K = map(int,input().split())
cnt = 0
d = [[0]*(W) for _ in range(H)]
h = [0]*H
w = [0]*W
for i in range(H):
    A = input()
    for j in range(len(A)):
        if A[j]=='
            cnt += 1
            d[i][j] = 1
            h[i] += 1
            w[j] += 1
ans = 0
for i in range(2**H):
    I = bin(i)[2:]
    I = I.zfill(H)
    for j in range(2**W):
        J = bin(j)[2:]
        J = J.zfill(W)
        tmp = cnt
        for k in range(len(I)):
            if I[k]=='1':
                tmp-=h[k]
        for l in range(len(J)):
            if J[l] =='1':
                tmp-=w[l]
        for k in range(len(I)):
            for l in range(len(J)):
                if I[k]=='1' and J[l]=='1':
                    tmp += d[k][l]
        if tmp ==K:
            ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000)

def Hdfs(pat,hw):
    if len(pat)==hw:
        p=pat[:]
        Hlist.append(p)
        return
    else:
        pat.append(0)
        Hdfs(pat,hw)
        pat.pop()
        pat.append(1)
        Hdfs(pat,hw)
        pat.pop()

def Wdfs(pat,hw):
    if len(pat)==hw:
        p=pat[:]
        Wlist.append(p)
        return
    else:
        pat.append(0)
        Wdfs(pat,hw)
        pat.pop()
        pat.append(1)
        Wdfs(pat,hw)
        pat.pop()

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

cnt=0
Hlist=[]
Wlist=[]
Hdfs([],H)
Wdfs([],W)
for i in Hlist:
    for j in Wlist:
        cnt=0
        for h in range(H):
            for w in range(W):
                if i[h]==0 and j[w]==0 and c[h][w]=="
                    cnt+=1
        if cnt==K:
            ans+=1
print(ans)

Solution (Python):
import numpy as np
import itertools

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

Hs = []
for i in range(H + 1):
    Hs.extend(list(itertools.combinations(range(H), i)))
Ws = []
for i in range(W + 1):
    Ws.extend(list(itertools.combinations(range(W), i)))

ans = 0
for h_list in Hs:
    for w_list in Ws:
        C_tmp = C.copy()
        for h in h_list:
            for i in range(W):
                C_tmp[h][i] = 'r'

        for w in w_list:
            for i in range(H):
                C_tmp[i][w] = 'r'

        c = 0
        for i in range(H):
            for j in range(W):
                if C_tmp[i][j] == '
                    c += 1
        if c == K:
            ans += 1

print(ans)

Solution (Python):
import itertools

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

hlist = []
for i in range(H+1):
    hlist += list(itertools.combinations(range(H), i))
wlist = []
for i in range(W+1):
    wlist += list(itertools.combinations(range(W), i))

answer = 0
for hchoice in hlist:
    for wchoice in wlist:
        count = 0
        for row in hchoice:
            for col in wchoice:
                if C[row][col]=='
                    count += 1
        if count == K:
            answer += 1
print(answer)

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


def count(h_mask, w_mask):
    sum_ = 0
    
    for i in range(h):
        if h_mask & 2 ** i != 0:
            continue
        for j in range(w):
            if w_mask & 2 ** j != 0:
                continue
            else:
                if c[i][j] == "
                    sum_ += 1

    if sum_ == k:
        return 1
    else:
        return 0


for i in range(h):
    c.append(input())

res = 0

for i in range(2 ** h):
    for j in range(2 ** w):
        res += count(i, j)

print(res)

Solution (Python):
import itertools 

H, W, K = map(int, input().split())
C = []
HS = []
WS = []
T = 0

def f(x):
  if x == "
    return 1
  else:
    return 0

for i in range(H):
  X = list(input())
  c = [f(x) for x in X]
  C.append(c)
  HS.append(sum(c))
  T += sum(c)

for j in range(W):
  cnt = 0
  for i in range(H):
    cnt += C[i][j]
  WS.append(cnt)
  
ans = 0

for h in itertools.product([0, 1], repeat = H):
  for w in itertools.product([0, 1], repeat = W):
    cnt = 0
    for i in range(H):
      if h[i] == 1:
        cnt += HS[i]
    for j in range(W):
      if w[j] == 1:
        cnt += WS[j]
    for i in range(H):
      for j in range(W):
        if h[i] == 1 and w[j] == 1:
          cnt -= C[i][j]
    if T - cnt == K:
      ans += 1

print(ans)

Solution (Python):
import math  
from collections import deque  
from itertools import combinations
from typing import Deque, Dict, List, Optional, Tuple, Union  

import numpy as np


def count_sharp(C: List[List[str]]) -> int:
    n = 0
    for row in C:
        for e in row:
            if e == "
                n += 1
    return n


def main(H: int, W: int, K: int, C: List[List[str]]):
    ans = 0

    h_list = [x for x in range(0, H)]
    w_list = [x for x in range(0, W)]

    for num_row in range(H):
        for num_col in range(W):
            row_combs = list(combinations(h_list, num_row))
            col_combs = list(combinations(w_list, num_col))

            for row_comb in row_combs:
                for col_comb in col_combs:
                    C_np = np.array(C)
                    for row in row_comb:
                        C_np[row, :] = "*"
                    for col in col_comb:
                        C_np[:, col] = "*"

                    if count_sharp(C_np) == K:
                        ans += 1

    print(ans)


if __name__ == "__main__":
    H, W, K = map(int, input().split())
    C: List[List[str]] = []

    for _ in range(H):
        c: List[str] = list(input())
        C.append(c)

    main(H, W, K, C)

Solution (Python):
def bit_fullsearch(target):
    n = len(target)
    ret = []
    for i in range(2**n):
        tmp = []
        for j in range(n):
            if (i>>j)&1:
                tmp.append(target[j])
        ret.append(tmp)
    return ret

h,w,k = map(int,input().split())
C = [list(input()) for _ in range(h)]

col = [i for i in range(h)]
row = [j for j in range(w)]

col = bit_fullsearch(col)
row = bit_fullsearch(row)

now = 0
ans = 0
for i in range(h):
    for j in range(w):
        if C[i][j]=='
            now += 1
for y in col:
    for x in row:
        tmp = 0
        for i in range(h):
            for j in range(w):
                flg = False
                if i in y:
                    flg = True
                if j in x:
                    flg = True
                if flg and C[i][j]=='
                    tmp += 1
        if now - tmp == k:
            ans += 1
print(ans)

Solution (Python):
from sys import stdin
import numpy as np
import copy


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W, K = list(map(int, _in[0].split(' ')))  
    c_arr = []
    for i in range(H):
        _ = list(_in[i + 1])  
        c_arr.append(_)
    c_arr = np.array(c_arr)
    
    c_arr[c_arr == '
    c_arr[c_arr == '.'] = 0
    c_arr = c_arr.astype(np.int8)

    ans = 0

    
    for bitw in range(1 << W):
        for bith in range(1 << H):
            board = copy.deepcopy(c_arr)
            
            for i in range(W):
                if bitw & (1 << i):
                    board[:, i] *= 0
            for i in range(H):
                if bith & (1 << i):
                    board[i, :] *= 0
            black = board.sum()
            if black == K:
                ans += 1
    
    print(ans)


if __name__ == "__main__":
    main()

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

from copy import deepcopy
ans = 0
for i in range(pow(2, H + W)):
    c_copy = deepcopy(c_list)
    for w in range(W):
        if (i & pow(2, H + w)) > 0:
            for h in range(H):
                c_copy[h] = c_copy[h][:w] + 'x' + c_copy[h][w+1:]
    cnt = 0
    for h in range(H):
        if (i & pow(2, h)) > 0:
            c_copy[h] = 'x' * W
        cnt += c_copy[h].count('
    if cnt == K:
        ans += 1
print(ans)

Solution (Python):
import copy
from itertools import product


h, w, k = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = 0
for x in product((0, 1), repeat=h):
    for y in product((0, 1), repeat=w):
        b = copy.deepcopy(c)
        for i in range(h):
            if x[i] == 1:
                for tate in range(w):
                    
                    b[i][tate] = "S"

        for j in range(w):
            if y[j] == 1:
                for yoko in range(h):
                   
                    b[yoko][j] = "S"
        count = 0
        for i in range(h):
            count += b[i].count("

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

Solution (Python):
from copy import deepcopy as cp
h,w,k=map(int,input().split())
l=[list(input()) for _ in range(h)]

cnt=0
for i in range(2**h):
  for j in range(2**w):
    tmp=cp(l)
    for b in range(h):
      if (i>>b)&1:
        tmp[b]=['.']*w
    for b in range(w):
      if (j>>b)&1:
        for c in range(h):
          tmp[c][b]='.'
    black=0
    for r in tmp:
      black+=r.count('
    if black==k:
      cnt+=1
print(cnt)

Solution (Python):
from itertools import combinations
import numpy as np
h, w, k = map(int, input().split())
cnt = 0
mass = []
for _ in range(h):
    s = list(str(input()))
    mass.append(s)
    
mass = np.array(mass)
for i in range(h+1):
    row_list = list(combinations(range(h), i))
    for j in range(w+1):
        col_list = list(combinations(range(w), j))
        for r_choice in row_list:
            for c_choice in col_list:
                tmp_mass = mass.copy()
                tmp_mass[list(r_choice), :] = "r"
                tmp_mass[:, list(c_choice)] = "r"
                if (tmp_mass == "
                    cnt += 1
      
print(cnt)

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

ans = 0
for i in range(2 ** (h + w)):
    d = copy.deepcopy(c)
    for j in range(h + w):
        if i >> j & 1:
            if 0 <= j < h:
                for k in range(w):
                    d[j][k] = "."
            else:
                for k in range(h):
                    d[k][j - h] = "."
    
    cnt = 0
    for l in range(h):
        cnt += d[l].count("
    if cnt == x:
        ans += 1

print(ans)

Solution (Python):

from itertools import product
import copy

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


sheet = []
for i in range(H):
    s = input()
    ret = []
    for j in range(W):
        if(s[j] == '
            ret.append(1)
        else:
            ret.append(0)
    sheet.append(ret)



pattern = list(product('YN', repeat = H+W))



ans = 0
for _ in range(len(pattern)):
    
    
        
    town = copy.deepcopy(sheet)
    
    now = pattern[_]
    
    for i in range(H):
        
        if(now[i] == 'Y'):
            town[i] = [0] * W
    
    for i in range(H, H+W):
        
        if(now[i] == 'Y'):
            for j in range(H):
                town[j][i-H] = 0
    
    
    su = 0
    for i in range(H):
        su += sum(town[i])
    if(su == K):
        ans += 1

    
print(ans)

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




ans = 0
for hbit in range(1<<h): 
    for wbit in range(1<<w): 
        c = 0
        for i in range(h):
            for j in range(w):
                if hbit>>i & 1 and wbit>>j & 1:
                    if C[i][j] =='
        if c == k: ans += 1

print(ans)