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
from itertools import combinations
h, w, k = map(int, input().split())
c =[input() for i in range(h)]
su = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == "
            su += 1
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())
c = [list(input()) for _ in range(h)]

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

ans = 0

for i in range(1 << h):
    for j in range(1 << w):
        count = black
        visited = [[False for _ in range(w)] for __ in range(h)]
        for p in range(h):
            if i >> p & 1:
                for k in range(w):
                    if not visited[p][k] and c[p][k] == '
                        count -= 1
                        visited[p][k] = True
        for p in range(w):
            if j >> p & 1:
                for k in range(h):
                    if not visited[k][p] and c[k][p] == '
                        count -= 1
                        visited[k][p] = True
        if count == K:
            ans += 1

print(ans)

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

gyo = []
retu = []

def gyoretu(l,n,gr):
    if len(l) == n:
        if gr == 0:
            global gyo
            gyo.append(l)
        else:
            global retu
            retu.append(l)
    else:
        gyoretu(l+[0],n,gr)
        gyoretu(l+[1],n,gr)

gyoretu([],h,0)
gyoretu([],w,1)

ans = 0

for Gyo in range(len(gyo)):
    for Retu in range(len(retu)):
        count = 0
        for i in range(h):
            for j in range(w):
                if gyo[Gyo][i] == 1 and retu[Retu][j] == 1:
                    if c[i][j:j+1] == "
                        count += 1
        if count == k:
 
            ans += 1
print(ans)

Solution (Python):
from itertools import combinations as comb
from bisect import bisect_left

import numpy as np
def main():
    H, W, K = map(int, input().split())
    cells = []
    count = 0
    for _ in range(H):
        row = [w for w in input()]
        cells.append(row)

    original = np.copy(np.array(cells))
    black = np.count_nonzero(cells == '
    
    for i in range(H+1):
        for iconb in comb(range(H), i):
            for j in range(W+1):
                for jconb in comb(range(W), j):
                    cells = np.copy(original)
                    cells[iconb, :] = '-'
                    cells[:, jconb] = '-'
                    black = np.count_nonzero(cells == '
                    
                    if black == K:
                        count += 1
    print(count)

if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import copy

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

def count_black(c):
  cnt = 0
  for i in c:
    cnt += i.count('
  return cnt


a = []
b = []

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

for i in range(h+1):
  a += list(itertools.combinations(range(h), i))
  
for j in range(w+1):
  b += list(itertools.combinations(range(w), j))

def change_color(d, i, j):
  for y in j:
    for x in range(len(d)):
      d[x] = d[x][:y] + 'r' + d[x][y+1:]
  
  for x in i:
    d[x] = 'r'
    
  return d
    
  
for i in a:
  for j in b:
    d = copy.deepcopy(c)
    d = change_color(d, i, j)
    if count_black(d) == k:
      ans += 1
    
print(ans)

Solution (Python):
import itertools
import numpy as np
H, W, K = map(int, input().split())
C = [[w=='

def count(h_slice, w_slice):
    cnt = 0
    for i in range(H):
        if h_slice[i] == 0:
            continue
        for j in range(W):
            if w_slice[j] == 0:
                continue
            cnt += C[i][j]
    return cnt

ans = 0
for h_slice in itertools.product([0, 1], repeat=H):
    h_slice = np.array(h_slice).astype(bool)
    for w_slice in itertools.product([0, 1], repeat=W):
        w_slice = np.array(w_slice).astype(bool)
        ans += count(h_slice, w_slice) == K
print(ans)

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

row_count = [c_row.count("
column_count = [[c_low[i] for c_low in c_list].count("
all_count = sum(row_count)

def bit_tansaku(num):
    list_num = list(range(num))
    list_num_all = []
    for i in range(2**len(list_num)):
        list_temp = []
        for j in range(len(list_num)):
            if (i >> j) &1 == 1:
                list_temp.append(list_num[j])
        list_num_all.append(list_temp)
    return list_num_all

def reducible_num(row_list,column_list,row_count,column_count,c_list):
    count = sum([row_count[i] for i in row_list])+sum([column_count[i] for i in column_list])
    for i in row_list:
        for j in column_list:
            if c_list[i][j] == "
                count -= 1
    return count
list_h_all = bit_tansaku(h)
list_w_all = bit_tansaku(w)

count = 0
for list_h_i in list_h_all:
    for list_w_j in list_w_all:
        if all_count - reducible_num(list_h_i,list_w_j,row_count,column_count,c_list)==k:
            count+=1
print(count)

Solution (Python):
from itertools import combinations
import copy
H,W,K = map(int,input().split())
cs = [list(input()) for i in range(H)]
HC = [i for i in range(H)]
WC = [i for i in range(W)]
fBlackCount=0
for i in range(H):
  fBlackCount += cs[i].count('
cBlackCount=fBlackCount
c=0
for i in range(H+1):
  for j in range(W+1):
    for selectRows in combinations(HC,i):
      for selectCols in combinations(WC,j):
        
        
        cBlackCount=fBlackCount
        for m in range(H):
          for n in range(W):
            if cs[m][n] == '
              if m in selectRows or n in selectCols:
                cBlackCount-=1
        if cBlackCount == K:
          
          
          
          c+=1
print(c)

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


def black_cnt(List):
  cnt = 0
  for c in List:
    cnt += c.count("
  return cnt

ans = 0

for i in range(2 ** (H+W)):
  cc = copy.deepcopy(cs)
  cnt = 0
  
  for j in range(H+W):
    if ((i >> j) & 1):
      if j < H:
        cc[j] = ["@"]*W
      else:
        for h in range(H):
          cc[h][j-H] = "@"
  
  if black_cnt(cc) == K:
    
    ans += 1

print(ans)

Solution (Python):
import sys
from io import StringIO
import unittest
import os
import copy


sys.setrecursionlimit(999999999)


def count(target_list: list, target_str: str):
    cnt = 0
    for target in target_list:
        cnt += target.count(target_str)
    return cnt



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

    ans = 0
    for i in range(1 << (h + w)):
        table = copy.deepcopy(data)
        for j in range(h):
            if i & 1 << j:
                table[j] = ["." for aaaa in range(w)]

        for jj in range(w):
            target = j + jj + 1
            if i & 1 << target:
                for aaaa in table:
                    aaaa[jj] = "."

        if count(table, "
            ans += 1

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """2 3 2
..

        output = """5"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """2 3 4
..

        output = """1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """2 2 3


        output = """0"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """6 6 8
..
.




        output = """208"""
        self.assertIO(test_input, output)

    
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

    h_bin = 1 << h
    w_bin = 1 << w

    ans = 0
    for i_h in range(h_bin):
        for i_w in range(w_bin):
            now_count = 0

            for i_line in range(h):
                now_line = 1 << i_line
                if i_h & now_line == 0:
                    continue

                for j_raw in range(w):
                    now_raw = 1 << j_raw
                    if i_w & now_raw == 0:
                        continue

                    if c[i_line][j_raw] == '
                        now_count += 1
                    
                    if now_count > k:
                        break

            if now_count == k:
                ans += 1

    print(ans)
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Solution (Python):
import numpy as np



h, w, K = map(int, input().split())
data = []
for i in range(h):
    data.append(list(input()))
data = np.array(data)


ans = 0
for i in range(2**h):
    h_indexs = []
    for k in range(h):
        if (i >> k) & 1:
            h_indexs.append(k)
    
    for j in range(2**w):
        w_indexs = []
        for k in range(w):
            if (j >> k) & 1:
                w_indexs.append(k)
        d = np.copy(data)
        
        for h_index in h_indexs:
            d[h_index, :] = 'r'
        for w_index in w_indexs:
            d[:, w_index] = 'r'
        num = (d == '
        if num == K:
            ans += 1
        
print(ans)

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

cells = []
rowBlack = []
columnBlack = [0] * w
for _ in range(h):
    ipt = input()
    rowBlack.append(ipt.count("
    cells.append(ipt)

for cell in cells:
    for i in range(w):
        if cell[i] == "
            columnBlack[i] += 1

total = sum(columnBlack)
cnt = 0
for hbit in range(2**h):
    for wbit in range(2**w):
        decBlack = 0

        hlis = []
        for he in range(h):
            if not hbit >> he & 1: continue
            decBlack += rowBlack[he]
            hlis.append(he)

        for we in range(w):
            if not wbit >> we & 1: continue
            decBlack += columnBlack[we]
            for he in hlis:
                if cells[he][we] == "
                    decBlack -= 1

        if total - decBlack == k:
            cnt += 1
print(cnt)

Solution (Python):
h,w,k=map(int,input().split())
moto=0
l=[]
for i in range(h):
  ll=input()
  l.append(ll)
  moto+=ll.count('
sa=moto-k

ans=0
import itertools
for p in itertools.product([0,1],repeat=h):
  for q in itertools.product([0,1],repeat=w):
    cnt=0
    for hh in range(h):
      if p[hh]==1:
        cnt+=l[hh].count('
    for ww in range(w):
      if q[ww]==1:
        for ll in l:
          if ll[ww]=='
            cnt+=1
    for hh in range(h):
      for ww in range(w):
        if p[hh]==q[ww]==1 and l[hh][ww]=='
          cnt-=1
    if cnt==sa:
      ans+=1
print(ans)

Solution (Python):

def count(il,jl):
    cnt = 0
    for k in range(h):
        for l in range(w):
            if il[k] == 0 and jl[l] == 0:
                if c[k][l] == "
                    cnt += 1
    return cnt


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

ans = 0

for i in range(2**h):
    il = [0] * h
    for ii in range(h):
        if i>>ii & 1:
            il[ii] = 1
    for j in range(2**w):
        jl = [0] * w
        for jj in range(w):
            if j>>jj & 1:
                jl[jj] = 1
        
        
        
        if k == count(il, jl):
            ans += 1

print(ans)

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

table = []

for _ in range(H):
    s = input()
    inst_s = []
    for x in s:
        inst_s.append(x)
    table.append(inst_s)




del_H = []
l = [i for i in range(H)]
for x in range(1,H+1):
	for v in itertools.combinations(l,x):
		del_H.append(v)


del_W = []
l = [i for i in range(W)]
for x in range(1,W+1):
	for v in itertools.combinations(l,x):
		del_W.append(v)

"""
print(del_H)
print(del_W)
"""
ans = 0


for tuple_h in del_H:
    for tuple_w in del_W:
        count = 0
        for h in tuple_h:
            for w in tuple_w:
                count += table[h][w].count("
        
        if count == K:
            ans += 1

print(ans)

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

H = 2 ** H - 1
W = 2 ** W - 1

for I in range(H+1):
    for J in range(W+1):
        count = 0
        for i, row in enumerate(C):
            for j, elem in enumerate(row):
                if 2 ** i & I and 2 ** j & J and elem == '
                    count += 1
        if count == K:
            Count += 1

print(Count)

Solution (Python):
import itertools
import copy


def nuri(a, b, _):
    
    if len(a)!=0:
        for aa in a:
            for i in range(w):
                _[aa][i] = 0
    
    if len(b)!=0:
        for bb in b:
            for i in range(h):
                _[i][bb] = 0
    return sum(map(sum, _))


h, w, k = map(int, input().split())
c = []  
for i in range(h):
    s = input()
    _ = []
    for j in range(w):
        if s[j] == ".":
            _.append(0)
        else:
            _.append(1)
    c.append(_)

iterh = [i for i in range(h)]
iterw = [i for i in range(w)]

count = 0
for i in range(h):
    lih = itertools.combinations(iterh, i)
    for lih_ in lih:
        for j in range(w):
            liw = itertools.combinations(iterw, j)
            for liw_ in liw:
                _ = copy.deepcopy(c)
                if nuri(lih_, liw_, _) == k:
                    count += 1
print(count)

Solution (Python):
H, W, K = map(int, input().split())
l = []
ans = 0
for i in range(H):
    l.append(input())
Hblack = []
Wblack = []
for i in range(W):
    Hblack.append(0)
    for j in range(H):
        if l[j][i] == '
            Hblack[-1] += 1
for i in range(H):
    Wblack.append(0)
    for j in range(W):
        if l[i][j] == '
            Wblack[-1] += 1
ALL = sum(Hblack)

for i in range(2 ** H):
    t1 = i
    Hl = [False] * H
    for j in range(H):
        if t1 & 1:
            Hl[j] = True
        t1 = t1 >> 1
    
    T = ALL
    for j in range(H):
        if Hl[j]:
            T -= Wblack[j]
    
    for j in range(2 ** W):
        T2 = T
        t2 = j
        for k in range(W):
            if t2 & 1:
                T2 -= Hblack[k]
                for m in range(H):
                    if Hl[m] and l[m][k] == '
                        T2 += 1
            t2 = t2 >> 1
        
        if T2 == K:
            ans += 1
print(ans)

Solution (Python):
from copy import deepcopy
h, w, k = map(int, input().split())
C = [['']*w for _ in range(h)]
for i in range(h):
    C[i] = list(input())

ans = 0
for i in range(2**h-1):
    for j in range(2**w-1):
        _C = deepcopy(C)
        H = bin(i)[2:].zfill(h)
        W = bin(j)[2:].zfill(w)
        for _k,_h in enumerate(H):
            if _h == '1':
                for _w in range(w):
                    _C[_k][_w] = 'x'
        for _k,_w in enumerate(W):
            if _w == '1':
                for _h in range(h):
                    _C[_h][_k] = 'x'
        tmp = []
        _ = [tmp.extend(c) for c in _C]
        if tmp.count('
            ans += 1

print(ans)

Solution (Python):
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    h, w, K = i_map()
    str_list = s_row_list(h)

    count = 0

    for h_bit in list(product([0,1], repeat=h)):
        for w_bit in list(product([0,1], repeat=w)):
            copy_list = deepcopy(str_list)

            for i in range(h):
                if h_bit[i] == 0:
                    continue
                copy_list[i][0] = '.' * w

            for i in range(w):
                if w_bit[i] == 0:
                    continue
                for k in range(h):
                    tmp = ''
                    for l in range(w):
                        if l == i:
                            tmp += '.'
                        else:
                            tmp += copy_list[k][0][l]
                    copy_list[k][0] = tmp
            tmp_count = 0
            for aaa in range(h):
                for bbb in range(w):
                    if copy_list[aaa][0][bbb] == '.':
                        continue
                    tmp_count += 1
            if tmp_count == K:
                count += 1

    print(count)
 
if __name__ == '__main__':
    main()

Solution (Python):



import copy

def dfs(hi, wi, wc, wh, ww, wk, d):
    if d == 0 and wi >= ww:
        d = 1
    elif d == 1 and hi >= wh:
        d = 2

    if d == 0:
        newc = copy.deepcopy(wc)
        for i in range(wh):
            newc[i][wi] = '.'
        rval = dfs(hi, wi+1, wc, wh, ww, wk, d)
        rval += dfs(hi, wi+1, newc, wh, ww, wk, d)
        return rval
    elif d == 1:
        newc = copy.deepcopy(wc)
        for i in range(ww):
            newc[hi][i] = '.'
        rval = dfs(hi+1, wi, wc, wh, ww, wk, d)
        rval += dfs(hi+1, wi, newc, wh, ww, wk, d)
        return rval
    else:
        cnt = 0
        for i in range(wh):
            for j in range(ww):
                if wc[i][j] == '
                    cnt = cnt + 1
        if cnt == wk:
            return 1
        else:
            return 0


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

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

ans = dfs(0, 0, c, h, w, k, 0)


print(ans)

Solution (Python):
H, W, K = map(int, input().split())
c = [input() for i in range(H)]
ans = 0
for hn in range(2**H):
    hp = list("{:0>{}b}".format(hn,H))
    for wn in range(2**W):
        wp = list("{:0>{}b}".format(wn,W))
        kuronum = 0
        for hc in range(H):
            if hp[hc] == "1":
                continue
            for wc in range(W):
                if wp[wc] == "0" and c[hc][wc] == "
                    kuronum += 1
        if kuronum == K:
            ans += 1
print(ans)

Solution (Python):
import copy
H,W,K = map(int,input().split())
C = []
for i in range(H):
    C.append(input())
D = copy.deepcopy(C)
count = 0
for j in range(2**(H+W)):
    a = str(bin(j))[2:]
    a = '0'*(H+W-len(a))+a
    for k in range(H):
        if a[k] == '0':
            C[k] = 'r'*W
    for l in range(W):
        if a[H+l] == '0':
            for q in range(H):
                C[q] = C[q][:l] + 'r' + C[q][l+1:]
    b = 0
    for t in range(H):
        b += C[t].count('
    if b == K:
        count += 1
    C = copy.deepcopy(D)
print(count)

Solution (Python):
import copy

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

ans = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        cnt = 0
        x = copy.deepcopy(ls)
        for g in range(h):
            for l in range(w):
                if (i >> g) & 1:
                    x[g] = ['.' for _ in range(w)]
                if (j >> l) & 1:
                    for y in range(h):
                        x[y][l] = '.'
        for z in x:
            for m in z:
                if m == '
                    cnt += 1
        if k == cnt:
            ans += 1
            
print(ans)

Solution (Python):
from copy import deepcopy

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

for h in range(0, 2**H):
  for w in range(0, 2**W):
    h_str = format(h, 'b').zfill(H)
    w_str = format(w, 'b').zfill(W)
    test = deepcopy(board)
    for i in range(H):
      if h_str[i] == '1':
        test[i] = 'r'*W
      for j in range(W):
      	if w_str[j] == '1':
          test[i] = test[i][:j] + 'r' + test[i][j+1:]
    counter = 0
    for row in test:
      counter += row.count('
    if counter == K:
      ans += 1
print(ans)

Solution (Python):

from itertools import combinations
H,W,K=map(int,input().split())
C=[input() for i in range(H)]
cnt=0
for i in range(H):
    for j in range(W):
        if C[i][j]=="
            cnt+=1
combH=[]
combW=[]
for h in range(H+1):
    combH+=combinations(list(range(H)),h)
for w in range(W+1):
    combW+=combinations(list(range(W)),w)
    
ans=0
for h in combH:
    for w in combW:
        cou=0
        flag=[[True for i in range(W)] for j in range(H)]
        for i in h:
            for j in range(W):
                if flag[i][j]:
                    if C[i][j]=="
                        cou+=1
                        flag[i][j]=False
        for i in range(H):
            for j in w:
                if flag[i][j]:
                    if C[i][j]=="
                        cou+=1
                        flag[i][j]=False
        if cnt-cou==K:
            ans+=1
print(ans)

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

c = [input() for i in range(h)]

ans = 0

for i in range(2 ** h):
    for k in range(2 ** w):
        cnt = 0
        for j in range(h):  
                for l in range(w):
                    if ((i >> j) & 1) and ((k >> l) & 1):
                        if c[j][l] == '
                            cnt = cnt + 1
        if cnt == kk:
            ans = ans + 1


print(ans)

Solution (Python):















import sys
def _p(*_a):
  
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")

def _pa(_aa):
  
  for _a in _aa: _p(_a)



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

M = list( list(input()) for _ in range(H) )

def fCntM(A):
  cnt = 0
  for h in range(H):
    for w in range(W):
      if A[h][w] == "
  return cnt


ans = 0



for h in range(1 << H):
  for w in range(1 << W):

    A = [ ["_"]*W for _ in range(H) ]
    for i in range(H):
      for j in range(W):
        if ( (h >> i) & 1 ) or ( (w >> j) & 1 ):
          A[i][j] = "R"
        else:
          A[i][j] = M[i][j]

    if fCntM(A) == K: ans += 1
    
    


print(ans)

Solution (Python):
import copy

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


def count(c):
    cnt = 0
    for i in range(len(c)):
        for j in range(len(c[i])):
            if "
                cnt += 1
    return cnt


def pattenrs(i, n, str, lst):
    if i == n:
        lst.append(str)
        return
    pattenrs(i + 1, n, str + "0", lst),
    pattenrs(i + 1, n, str + "1", lst)


patterns_i = []
pattenrs(0, h, "", patterns_i)

patterns_j = []
pattenrs(0, w, "", patterns_j)

total_black = count(c)
res = 0
for pattern_i in patterns_i:
    for pattern_j in patterns_j:
        copied = copy.deepcopy(c)
        cnt = total_black
        i_list = list(map(int, pattern_i))
        j_list = list(map(int, pattern_j))
        for i in range(len(i_list)):
            for j in range(len(j_list)):
                if 1 == i_list[i] or 1 == j_list[j]:
                    cnt -= 1 if "
        res += 1 if cnt == k else 0

print(res)

Solution (Python):
H, W, K = map(int, input().split())
c = []
for i in range(H):
    c.append(input().strip())
    
out = 0
import itertools

def getset(n):
    l = []
    curr = 0
    while n:
        if n & 1:
            l.append(curr)
        curr += 1
        n //= 2
    return l

for hSet in range(2 ** H):
    hL = getset(hSet)
    for cSet in range(2 ** W):
        cL = getset(cSet)
        cnt = 0
        for i in hL:
            for j in cL:
                if c[i][j] == '
                    cnt += 1
        if cnt == K:
            out += 1
print(out)

Solution (Python):
import sys
import itertools

import numpy as np


def main():
    def readline() -> str:
        s = sys.stdin.readline()
        return s.rstrip()

    h, w, k = map(int, readline().split())  
    field: np.ndarray = np.array(
        tuple(
            tuple(0 if c == "." else 1 for c in readline()) for _ in range(h)
        )
    )

    answer: int = 0

    for pattern_num in range(2 ** (h + w)):
        test_field = field.copy()
        pattern_num_bin = format(pattern_num, f"0{h+ w}b")
        h_bin: str = pattern_num_bin[:h]
        w_bin: str = pattern_num_bin[h:]

        for row in range(h):
            if h_bin[row] == "1":
                test_field[row] = np.ones((w,)) * 2

        for column in range(w):
            if w_bin[column] == "1":
                test_field[:, column] = np.ones((h,)) * 2

        if np.sum(test_field == 1) == k:
            answer += 1

    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    h,w,k = [int(v) for v in input().split()]
    c = []
    for _ in range(h):
        c.append(int('0b'+input().replace('
    imax = 1 << w
    bc = [0] * imax
    for i in range(imax):
        bc[i] = len([v for v in list(bin(i)) if v=='1'])

    sum = 0
    for ih in range(1<<h):
        for iw in range(1<<w):
            cnt = 0
            for j in range(h):
                if ih & (1 << j):
                    cnt += bc[c[j] & iw]   
            if cnt==k:
                sum += 1
    
    print(sum)

main()

Solution (Python):
import itertools
import copy

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

result = 0
product = itertools.product(range(2), repeat=(h + w))
for p in product:
    operation_target = copy.deepcopy(C)
    rows = p[:w]
    cols = p[w:]
    for idx, i in enumerate(rows):
        if i == 1:
            for j in range(h):
                operation_target[j][idx] = '.'
    for idx, i in enumerate(cols):
        if i == 1:
            for j in range(w):
                operation_target[idx][j] = '.'
    counter = 0
    for i in range(h):
        for j in range(w):
            if operation_target[i][j] == '
                counter += 1
    if counter == k:
        result += 1
print(result)

Solution (Python):
import itertools
import copy

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

cnt = 0
h_l = list(range(0,h,1))
w_l = list(range(0,w,1))

for inum in range(h):
    for ilis in itertools.combinations(h_l, inum):
        ilis = list(ilis)

        for jnum in range(w):
            for jlis in itertools.combinations(w_l, jnum):
                jlis = list(jlis)
                c_list = copy.copy(c)

                if len(ilis) != 0:
                    for i in ilis:
                        c_list[i] = '0' * w
                if len(jlis) != 0:
                    for j in jlis:
                        for i in range(h):
                            if not c_list[i] == '0' * w:
                                c_list[i] = c_list[i][0:j] + '0' + c_list[i][j+1:]
                c_str = ''.join(c_list)
                if c_str.count('
                    cnt += 1

print(cnt)

Solution (Python):

import copy
n, *masu = [i.split() for i in open(0)]
h, w, k = map(int, n)
c = 0
masu = [list(*i) for i in masu]
for i in range(2**h):
    hi = []
    for j in range(h):
        if i>>j &1:
            hi.append(j)
    for p in range(2**w):
        wi = []
        for q in range(w):
            if p>>q &1:
                wi.append(q)
        d = copy.deepcopy(masu)
        for r in hi:
            d[r] = ["."] * w

        for r in wi:
            for o in range(h):
                d[o][r] = "."
        if k == sum(s == "
            c += 1
print(c)

Solution (Python):
from itertools import combinations
H, W, K = map(int, input().split())
C = [input() for _ in range(H)]
ans = 0
for i in range(1 << H):
    hs = []
    for h in range(H):
        if (i >> h) & 1:
            hs.append(h)
    for j in range(1 << W):
        ws = []
        for w in range(W):
            if (j >> w) & 1:
                ws.append(w)
        tmp = 0
        for h in range(H):
            if h in hs:
                continue
            for w in range(W):
                if w in ws:
                    continue
                tmp += C[h][w] == '
        if tmp == K:
            ans += 1

print(ans)

Solution (Python):
[H,W,K] = [int(x) for x in input().split()]
data = [input() for x in range(H)]

result = 0

for y in range(1 << H):
    for x in range(1 << W):
        count = 0
        for i,d1 in enumerate(data):
            if (y >> i) & 1:
                continue
            for j,d2 in enumerate(d1):
                if (x >> j) & 1:
                    continue
                if d2 == '
                    count += 1
        if count == K:
            result += 1

print(result)