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):
from collections import Counter
import copy
from itertools import combinations


def A(x):
  return 1000 - x % 1000 if x % 1000 != 0 else 0


def B(n, ss):
  keys_values = Counter(ss)
  orders = ['AC', 'WA', 'TLE', 'RE']
  for order in orders:
    if order in keys_values:
      print("{} x {}".format(order, keys_values[order]))
    else:
      print("{} x {}".format(order, 0))


def _get_num_black(c_list, r_list, h, w, g):
  num_black = 0
  for i in range(h):
    if i in r_list:
      continue
    for j in range(w):
      if j in c_list:
        continue
      num_black += (1 if g[i][j] == '
  return num_black


def C(h, w, k, g):
  num_choice = 0
  for i in range(k + 1):
    for j in range(k - i + 1):
      for c_list in list(combinations(range(w), j)):
        for r_list in list(combinations(range(h), i)):
          if _get_num_black(c_list, r_list, h, w, g) == k:
            num_choice += 1
          
  return num_choice


def C2(H, W, K, g):
  """All copied."""
  c = []
  for i in range(H):
    c.append([])
    for j in range(W):
      c[i].append(g[i][j])

  ans = 0
  for h in range(H + 1):
    for w in range(W + 1):
      for h2 in combinations(list(range(H)), h):
        for w2 in combinations(list(range(W)), w):
          paint = copy.deepcopy(c)
          for h3 in h2:
            for i in range(W):
              paint[h3][i] = "r"
          for i in range(H):
            for w3 in w2:
              paint[i][w3] = "r"
          count_black = 0
          for i in range(H):
            count_black += paint[i].count("
            
          if count_black == K:
            ans += 1

  return ans


def C3(h, w, k, g):
  """
  - Change the calculation of count_black.
  - Change the name of variables.
  """
  num_choice = 0
  for i in range(h + 1):
    for j in range(w + 1):
      for h2 in combinations(list(range(h)), i):
        for w2 in combinations(list(range(w)), j):
          if _get_num_black(w2, h2, h, w, g) == k:
            num_choice += 1
  return num_choice


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


if __name__ == '__main__':
  main()

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

masme = []
for i in range(H):
    masme.append(list(input()))



h_p = []
for h in range(pow(2,H)):
    h_p.append(str(bin(h))[2:].zfill(H))



w_p = []
for w in range(pow(2,W)):
    w_p.append(str(bin(w))[2:].zfill(W))



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

def delete_row(mas, i):
    ilist = list(i)
    
    ans = []
    for n in range(H):
        
        if ilist[n] == "0":
            ans.append(mas[n])
            
    return ans

def delete_column(mas, i):
    ilist = list(i)
    ans = []
    for row in mas:
        
        tmp_row=[]
        for n in range(W):
            if(ilist[n] == "0"):
                tmp_row.append(row[n])
        
        ans.append(tmp_row)
    return ans


ans_cnt = 0
for h in h_p:
    for w in w_p:
        tmp = delete_row(masme, h)
        tmp2= delete_column(tmp, w)
        cnt = count(tmp2)
        if(cnt == K):
            ans_cnt += 1

print(ans_cnt)

Solution (Python):
import copy
H, W, K = map(int, input().split())
li = []
black = 0
result = 0

for i in range(H):
    li.append(list(input()))
    black += li[i].count("

for j in range(2 ** H):
    sum_h = 0
    li_a = copy.copy(li)
    for k in range(H):
        if j & (1 << k):
            sum_h += li[k].count("
            li_a[k] = ["r"]*len(li_a[k])
    for l in range(2 ** W):
        sum_w = 0
        for m in range(W):
            if (1 << m) & l:
                for n in range(H):
                    if li_a[n][m] == "
                        sum_w += 1
        if sum_h + sum_w == black - K:
            result += 1

print(result)

Solution (Python):
h, w, k = map(int, input().split())
c = []
b = 0
ans = 0
count = [[0] * w for i in range(h)]
for i in range(h):
    ci = input()
    c.append(ci)
    b += ci.count("
    for j in range(w):
        count[i][j] += (ci[j] == "

for i in range(2**(h + w)):
    x, y = [], []
    for j in range(h + w):
        if (i >> j) & 1:
            if j <= h - 1:
                y.append(j)
            else:
                x.append(j - (h - 1) - 1)
    n = 0
    for xi in x:
        n += sum([ci[xi] for ci in count])
    for yi in y:
        n += sum(count[yi])
    for yi in y:
        for xi in x:
            if count[yi][xi]:
                n -= 1
    ans += (b - n == k)
print(ans)

Solution (Python):
import copy
h,w,k = map(int, input().split())
lc = []
for _ in range(h):
  ch = [1 if c == "
  lc.append(ch)

ans = 0

for i1 in range(2**h):
  for j1 in range(2**w):
    lc_tmp = copy.deepcopy(lc) 
    for i2 in range(h):
      if (i1 >> i2) &1 == 1:
        for j in range(w):
          lc_tmp[i2][j] = 0

    for j2 in range(w):
      if (j1 >> j2) &1 == 1:
        for i in range(h):
          lc_tmp[i][j2] = 0

    cnt = 0
    for i in range(h):
      cnt += sum(lc_tmp[i])
    ans += 1 if cnt == k else 0
print(ans)

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



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



def count(arr):
    cnt = 0
    for l in arr:
        for i in l:
            if i == "
                cnt += 1

    return cnt


ans = 0
for i in range(2 ** w):
    tmp = copy.deepcopy(c)
    for j in range(w):
        if ((i >> j) & 1):
            for s in range(h):
                tmp[s][j] = '$'

    for t in range(2 ** h):
        tmp2 = copy.deepcopy(tmp)
        for j in range(h):
            if ((t >> j) & 1):
                for s in range(w):
                    tmp2[j][s] = '$'
        
        
        if count(tmp2) == k:
            ans += 1

print(ans)

Solution (Python):
import logging

logging.basicConfig(level=logging.INFO)
logging.info('info')


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

    logging.info("hello")

    blacks = 0
    ans = 0

    for i in range(2 ** H):
        for j in range(2 ** W):
            blacks = 0
            for i_2 in range(H):
                for j_2 in range(W):
                    if ((i >> i_2) & 1) and ((j >> j_2) & 1):
                        if C_ij[i_2][j_2] == "
                            blacks += 1
            if blacks == K:
                ans += 1
    
    print(ans)
                   

if __name__ == "__main__":
    main()

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

c = []

ans = 0

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

k = 0

for i in range(2**(H+W)):
    x = []
    y = []
    for j in range(H+W):
        if i >> j & 1:
            if j < W:
                x.append(j)
            else:
                y.append(j-W)
    k = 0
    for X in x:
        for Y in y:
            if c[Y][X] == '
                k += 1
    if k == K:
        ans +=1


print(ans)

Solution (Python):
from itertools import*
h,*m=open(0)
h,w,k=map(int,h.split())
s=0
for i in range(h+1):
    for a in combinations(range(h),i):
        a={*a}
        for j in range(w+1):
            for b in combinations(range(w),j):
                b={*b}
                c=0
                for y in range(h):
                    if y in a:continue
                    for x in range(w):
                        if x in b:continue
                        c+=m[y][x]=='
                s+=c==k
print(s)

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

sol = 0
for rm in range(1<<n):
    for cm in range(1<<m):
        x = 0
        for i in range(n):
            for j in range(m):
                if (rm & (1<<i)) and (cm & (1<<j)) and w[i][j] == '
                    x += 1
        if x == k:
            sol += 1

print(sol)

Solution (Python):

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

ans = 0

for i in range(1 << h):
    for j in range(1 << w): 
        cnt = 0
        for x in range(h):
            for y in range(w):
                if c[x][y] == '
                    cnt += 1
        if cnt == k:
            ans += 1

print(ans)

Solution (Python):
import copy


def countBlack(c, k):
    cnt = 0
    for i in range(len(c)):
        for j in range(len(c[i])):
            if c[i][j] == '
                cnt += 1
                if cnt == k + 1:
                    return cnt

    return cnt


def createPaintedC(c, rows, cols):
    c_copy = copy.deepcopy(c)
    for i in range(len(c_copy)):
        for j in range(len(c_copy[i])):
            if i in rows or j in cols:
                c_copy[i] = c_copy[i][:j] + '$' + (c_copy[i][j + 1:] if j < len(c_copy[i]) else '')

    return c_copy

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

    cnt = 0
    painted_rows_list = [[]]
    for i in range(H):
        new_rows_list = []
        for rows in painted_rows_list:
            rows_copy = copy.copy(rows)
            rows_copy.append(i)
            new_rows_list.append(rows_copy)
        painted_rows_list += new_rows_list

    painted_cols_list = [[]]
    for i in range(W):
        new_cols_list = []
        for cols in painted_cols_list:
            cols_copy = copy.copy(cols)
            cols_copy.append(i)
            new_cols_list.append(cols_copy)
        painted_cols_list += new_cols_list

    for rows in painted_rows_list:
        for cols in painted_cols_list:
            new_c = createPaintedC(c, rows, cols)
            black_count = countBlack(new_c, K)
            if black_count == K:
                cnt += 1

    print(cnt)

Solution (Python):
from collections import Counter
import copy
from itertools import combinations


def A(x):
  return 1000 - x % 1000 if x % 1000 != 0 else 0


def B(n, ss):
  keys_values = Counter(ss)
  orders = ['AC', 'WA', 'TLE', 'RE']
  for order in orders:
    if order in keys_values:
      print("{} x {}".format(order, keys_values[order]))
    else:
      print("{} x {}".format(order, 0))


def _get_num_black(c_list, r_list, h, w, g):
  num_black = 0
  for i in range(h):
    if i in r_list:
      continue
    for j in range(w):
      if j in c_list:
        continue
      num_black += (1 if g[i][j] == '
  return num_black


def C(h, w, k, g):

  num_choice = 0
  for i in range(k + 1):
    for j in range(k - i + 1):
      comb_c = list(combinations(range(w), j))
      comb_r = list(combinations(range(h), i))
      for c_list in comb_c:
        for r_list in comb_r:
          num_black = _get_num_black(c_list, r_list, h, w, g)
          if num_black == k:
            num_choice += 1
          print(h, i, r_list, w, j, c_list, num_black, k)
  return num_choice


def C2(H, W, K, g):
  """All copied."""
  c = []
  for i in range(H):
    c.append([])
    for j in range(W):
      c[i].append(g[i][j])

  ans = 0
  for h in range(H + 1):
    for w in range(W + 1):
      for h2 in combinations(list(range(H)), h):
        for w2 in combinations(list(range(W)), w):
          paint = copy.deepcopy(c)
          for h3 in h2:
            for i in range(W):
              paint[h3][i] = "r"
          for i in range(H):
            for w3 in w2:
              paint[i][w3] = "r"
          count_black = 0
          for i in range(H):
            count_black += paint[i].count("
            
          if count_black == K:
            ans += 1

  return ans


def C3(H, W, K, g):
  """Change the calculation of count_black."""
  c = []
  for i in range(H):
    c.append([])
    for j in range(W):
      c[i].append(g[i][j])

  ans = 0
  for h in range(H + 1):
    for w in range(W + 1):
      for h2 in combinations(list(range(H)), h):
        for w2 in combinations(list(range(W)), w):
          if _get_num_black(w2, h2, H, W, c) == K:
            ans += 1

  return ans


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


if __name__ == '__main__':
  main()

Solution (Python):
import itertools
H,W,K=map(int,input().split())
c=[list(input()) for i in range(H)]
count=0
for bit_h in itertools.product([0,1],repeat=H):
    for bit_w in itertools.product([0,1],repeat=W):
        black=0
        for h,w in itertools.product(range(H),range(W)):
            if c[h][w]=="
                black+=1
        if black==K:
            count+=1
print(count)

Solution (Python):
import itertools
import numpy as np

N,W,K = map(int,input().split())
g_all = np.array([list(input()) for i in range(N)])

K_all = np.count_nonzero(g_all == '
count = 0

def dfs(i,g):
  if (i<N):
    g[i,:] = ['r']*W
  else:
    g[:,i-N] = ['r']*N
  return g

g = g_all

for L in range(2**(N+W)):
  g = g_all.copy()
  for i in range(N+W):
    if (i<N):
      if ((L>>i)&1):
        g[i,:] = ['r']*W
    else:
      if ((L>>i)&1):
        g[:,i-N] = ['r']*N
  if np.count_nonzero(g == '
    count+=1
print(count)

Solution (Python):
h,w,x=map(int,input().split())
c=[input() for _ in [0]*h]
print(sum(x==sum(i>>k&1 and j>>l&1 and c[k][l]=='
)

Solution (Python):
h,w,k=map(int,input().split())
c = [input() for _ in range(h)]
ans = 0
for i in range(1<<h):
    for j in range(1<<w):
        cnt = 0
        for x in range(h):
            for y in range(w):
                if (i>>x) & 1 and (j>>y) & 1 and c[x][y] == "
                    cnt+=1
        if cnt ==k:
            ans += 1
print(ans)

Solution (Python):
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    h, w, K = map(int, input().split())
    field = []
    base = 0
    for i in range(h): 
        s = input()
        s = [1 if _ == '
        field.append(s)
        base += sum(s)
    ans = 0  
    for i in range(2**h):
        for j in range(2**w):
            num = base
            for k in range(h):
                if (i >> k) & 1:
                    num -= sum(field[k])
                else:
                    for l in range(w):
                        if (j >> l) & 1 and field[k][l] ==1:
                            num -= 1
        
            if num == K:
                ans += 1
    print(ans)

            

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
import copy
from itertools import combinations


def A(x):
  return 1000 - x % 1000 if x % 1000 != 0 else 0


def B(n, ss):
  keys_values = Counter(ss)
  orders = ['AC', 'WA', 'TLE', 'RE']
  for order in orders:
    if order in keys_values:
      print("{} x {}".format(order, keys_values[order]))
    else:
      print("{} x {}".format(order, 0))


def C(h, w, k, g):

  def _get_num_black(c_list, r_list):
    num_black = 0
    for i in range(h):
      if i in r_list:
        continue
      for j in range(w):
        if j in c_list:
          continue
        num_black += (1 if g[i][j] == '
    return num_black

  num_choice = 0
  for i in range(k + 1):
    for j in range(k - i + 1):
      comb_c = list(combinations(range(w), j))
      comb_r = list(combinations(range(h), i))
      for c_list in comb_c:
        for r_list in comb_r:
          num_black = _get_num_black(c_list, r_list)
          if num_black == k:
            num_choice += 1
          print(h, i, r_list, w, j, c_list, num_black, k)
  return num_choice


def C2(H, W, K, g):
  """All copied."""
  c = []
  for i in range(H):
    c.append([])
    for j in range(W):
      c[i].append(g[i][j])

  ans = 0
  for h in range(H + 1):
    for w in range(W + 1):
      for h2 in combinations(list(range(H)), h):
        for w2 in combinations(list(range(W)), w):
          paint = copy.deepcopy(c)
          for h3 in h2:
            for i in range(W):
              paint[h3][i] = "r"
          for i in range(H):
            for w3 in w2:
              paint[i][w3] = "r"
          count_black = 0
          for i in range(H):
            count_black += paint[i].count("
            
          if count_black == K:
            ans += 1

  return ans

def C3(H, W, K, g):
  """Change the calculation of count_black."""
  c = []
  for i in range(H):
    c.append([])
    for j in range(W):
      c[i].append(g[i][j])

  ans = 0
  for h in range(H + 1):
    for w in range(W + 1):
      for h2 in combinations(list(range(H)), h):
        for w2 in combinations(list(range(W)), w):
          count_black = 0
          for i in range(H):
            if i in h2:
              continue
            for j in range(W):
              if j in w2:
                continue
              count_black += (1 if c[i][j] == '
          if count_black == K:
            ans += 1

  return ans


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


if __name__ == '__main__':
  main()

Solution (Python):
H,W,K = map(int,input().split())
c = [input() for _ in range(H)]
ans = 0
for i in range(1<<H):
    for j in range(1<<W):
        cnt = 0
        for k in range(H):
            if i >> k & 1: continue
            for l in range(W):
                if j >> l & 1: continue
                if c[k][l] == "
        if cnt == K: ans += 1
print(ans)

Solution (Python):
import itertools
H,W,K = map(int,input().split())
sx = list(itertools.product([0,1],repeat = H))
sy = list(itertools.product([0,1],repeat = W))
data = list(input() for num in range(int(H)))
data2 = []
for num in range(int(H)):
  data2 += [list(data[num])]
ans = 0
for numx in range(len(sx)):
  for numy in range(len(sy)):
    count = 0
    for i in range(H):
      for j in range(W):
        if(sx[numx][i]==1)&(sy[numy][j]==1)&(data2[i][j]=="
          count += 1
    if(count == K):
      ans += 1
      
print(ans)

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

m = []
b_list = []

for i in range(h):
    inc = list(input())
    m.append(inc)
    for j, el in enumerate(inc):
        if el == '
            b_list.extend([i*w + j])





ans = 0

for bit_h in range(1 << h):
    for bit_w in range(1 << w):
        black = 0
        for i in range(h):
            for j in range(w):
                if m[i][j] == '
                    black += 1
        if black == k:
            ans += 1

print(ans)

Solution (Python):
from __future__ import annotations

import itertools
from dataclasses import dataclass
from typing import List


@dataclass
class Cell:
    row_idx: int
    col_idx: int
    color: str

    def to_red(self) -> Cell:
        return Cell(self.row_idx, self.col_idx, color='R')


@dataclass
class Board:
    cells: List[Cell]

    @classmethod
    def create(cls, H: int, W: int, C: List[List[str]]) -> Board:
        cells = []

        for i in range(H):
            for j in range(W):
                cell = Cell(i + 1, j + 1, C[i][j])
                cells.append(cell)

        return Board(cells)

    def count_black_cells(self) -> int:
        return len([cell for cell in self.cells if cell.color == '

    def paint_row(self, row_idx: int) -> Board:
        new_cells = []

        for cell in self.cells:
            if cell.row_idx == row_idx:
                new_cells.append(cell.to_red())
            else:
                new_cells.append(cell)

        return Board(new_cells)

    def paint_col(self, col_idx: int) -> Board:
        new_cells = []

        for cell in self.cells:
            if cell.col_idx == col_idx:
                new_cells.append(cell.to_red())
            else:
                new_cells.append(cell)

        return Board(new_cells)


def actual(H, W, K, C):
    count = 0

    
    
    
    
    paint_patterns = list(itertools.product(range(2), repeat=H + W))

    for pattern in paint_patterns:
        board = Board.create(H, W, C)

        row_paint_pattern = pattern[:H]  
        col_paint_pattern = pattern[H:]  

        for row_idx, will_paint_the_row in enumerate(row_paint_pattern, start=1):
            if will_paint_the_row == 1:
                board = board.paint_row(row_idx)

        for col_idx, will_paint_the_col in enumerate(col_paint_pattern, start=1):
            if will_paint_the_col == 1:
                board = board.paint_col(col_idx)

        if board.count_black_cells() == K:
            count += 1

    return count

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

print(actual(H, W, K, C))

Solution (Python):
H, W, k = map(int, input().split())
field = []
for i in range(H):
    s = list(input())
    field.append(s)
ans = 0


for maskR in range((1 << H)):
    for maskC in range((1 << W)):
        
        black = 0
        for i in range(H):
            for j in range(W):
                if ((maskR >> i) & 1 == 0) and (
                    (maskC >> j) & 1 == 0) and field[i][j] == '
                    black += 1
        if black == k:
            ans += 1

print(ans)

Solution (Python):
h,w,x=map(int,input().split())
c=[input() for _ in range(h)]
a=0
for i in range(2**h):
  for j in range(2**w):
    t=0
    for k in range(h):
      for l in range(w):
        if i>>k&1 and j>>l&1 and c[k][l]=='
    if t==x: a+=1
print(a)

Solution (Python):

H, W, K = map(int, input().split())
total_black = 0
row_black = list()
column_black = list()
matrix = [[] for _ in range(H)]
for i in range(H):
  t = input()
  total_black += t.count("
  row_black.append(t.count("
  for j in range(W):
    matrix[i].append(t[j])

for i in range(W):
  count = 0
  for j in range(H):
    if matrix[j][i] == "
      count += 1
  column_black.append(count)

ans = 0
for i in range(2**H):
  count_row = 0
  select_row = list()
  
  for l in range(H):
    if (i >> l) & 1:
      
      count_row += row_black[l]
      select_row.append(l)
  
  for j in range(2**W):
    count_column = 0
    select_column = list()
    for k in range(W):
      if (j >> k) & 1:
        
        count_column += column_black[k]
        select_column.append(k)
    
    count_duplication = 0
    for r in select_row:
      for c in select_column:
        if matrix[r][c] == "
          count_duplication += 1

    
    if total_black - count_row - count_column + count_duplication == K:
      ans += 1
      
print(ans)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from itertools import product
def resolve():
    m, n, k = map(int, input().split())
    grid = [list(input()) for _ in range(m)]
    ans = 0
    for U, V in product(range(1 << m), range(1 << n)):
        tmp = [a[:] for a in grid]
        for i in range(m):
            if not U >> i & 1:
                continue
            for j in range(n):
                tmp[i][j] = '.'
        for j in range(n):
            if not V >> j & 1:
                continue
            for i in range(m):
                tmp[i][j] = '.'
        ans += sum(tmp[i][j] == '
    print(ans)
resolve()

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

for i in range(h):
    line = list(input())
    masu.append(line)

masu_tmp = copy.deepcopy(masu)
res=0
for i in range(2 ** h):
    masu_tmp = copy.deepcopy(masu)
    binary_i = format(i, 'b')
    i_len=len(binary_i)
    binary_i = "0"*(h-i_len)+binary_i
    for ii in range(len(binary_i)):
        if binary_i[ii] == "1":
            masu_tmp[ii]=list("-"*w)
    masu_tmp_2 = copy.deepcopy(masu_tmp)
    for j in range(2 ** w):
        masu_tmp_2 = copy.deepcopy(masu_tmp)
        counter = 0
        binary_j = format(j, 'b')
        i_len=len(binary_j)
        binary_j = "0"*(w-i_len)+binary_j
        
        for l in range(len(binary_j)):
            if binary_j[l] == "1":
                for m in range(h):
                    masu_tmp_2[m][l]="-"
                
        for n in range(h):
            for o in range(w):
                if masu_tmp_2[n][o] == "
                    counter +=1
                
        if counter == k:
            res += 1
        
print(res)

Solution (Python):
h,w,k=map(int,input().split())
c=[]
ans=0
for _ in range(h):
    c.append(list(input()))
for i in range(2**h):
    for j in range(2**w):
        b=0
        for x in range(h):
            for y in range(w):
                if (i>>x)&1==False and (j>>y)&1==False:
                    if c[x][y]=='
                        b+=1
        if b==k:
            ans+=1
print(ans)

Solution (Python):

import sys
import math


from sys import stdin,stdout
from collections import deque,defaultdict
from math import ceil,floor,inf,sqrt,factorial,gcd,log2
from copy import deepcopy
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
mod=1000000007

n,m,k=iia()
arr=[input()for i in range(n)]
res=0
for i in range(2**n):
    for j in range(2**m):
        ans=0
        for ii in range(n):
            for jj in range(m):
                if i>>ii & 1 and j>>jj &1 and arr[ii][jj]=='
                    ans+=1
        if ans==k:
            res+=1
print(res)

Solution (Python):
import itertools
h, w, k = map(int, input().split())
bw = []
for i in range(h):
    bw.append(input())
h_list = [i+1 for i in range(h)]
w_list = [i+1 for i in range(w)]

cnt = 0
for m in range(1, h+1):
    for n in range(1, w+1):
        for H in itertools.combinations(h_list, m):
            for B in itertools.combinations(w_list, n):
                a = []
                for hh in H:
                    for bb in B:
                        a += bw[hh-1][bb-1]
                if a.count('
                    cnt += 1

print(cnt)

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue

from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W, K = il()
    line = [iss() for _ in range(H)]

    ret = 0
    for h in range(1 << H):
        for w in range(1 << W):
            cnt = 0
            for i in range(H):
                for j in range(W):
                    if h >> i & 1 and w >> j & 1 and line[i][j] == '
                        cnt += 1
            if cnt == K:
                ret += 1
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
h,w,k=map(int, input().split())
L=[]
for i in range(h):
	S=list(input())
	for j in range(w):
		L.append(S[j])
import itertools
import copy
t=[1,0]
cnt=0

for v in itertools.product(t, repeat=h+w):
	LL=copy.copy(L)
	for i in range(h+w):
		if v[i]==1 and i<h:
			for j in range(w):
				LL[w*i+j]='r'
		if v[i]==1 and i>=h:
			for j in range(h):
				LL[w*j+(i-h)]='r'
	s=LL.count('
	if s==k:
		cnt+=1
print(cnt)

Solution (Python):
import copy

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

  def del_row(num, m):
    res = copy.deepcopy(m)
    b = format(num, "0{}b".format(H))
    
    for i in range(H):
      if b[H-i-1]=="1":
        res[H-i-1]=["R" for i in range(W)]
    return res

  def del_col(num, m):
    res = copy.deepcopy(m)
    b = format(num, "0{}b".format(W))
    
    for i in range(W):
      if b[W-i-1]=="1":
        for j in range(H):
          res[j][W-i-1] = "R"
    return res

  def judge(row_bin, col_bin):
    res = del_row(row_bin, C)
    res = del_col(col_bin, res)
    c = 0
    for i in range(H):
      for j in range(W):
        if res[i][j]=="
          c+=1
    return c==K

  c=0
  for i in range(2**H):
    for j in range(2**W):
      if judge(i, j):
        c+=1

  print(c)

if __name__ == "__main__":
    main()

Solution (Python):
import copy;

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

  original = [[0 for _ in range(W)] for _ in range(H)]
  ans = 0

  for i in range(H):
    S = [str(s) for s in input()]
    
    for j, v in  enumerate(S):
      if(v == "
        original[i][j] = 1
      else:
        original[i][j] = 0

  for i in range(1 << H):
    for j in range(1 << W):
      m = copy.deepcopy(original);

      count = 0
      for k in range(H):
        if(i >> k & 1):
          m[k] = [0] * W
      
      for k in range(W):
        if(j >> k & 1):
          for l in m:
            l[k] = 0

      for row in m:
        count += row.count(1);

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

  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):
import itertools

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

del_row = lambda items, del_indexes: [
    item for index, item in enumerate(items) if index not in del_indexes
]

total = 0

for i in range(h):
    for j in range(w):
        for ic in itertools.combinations(range(h), i):
            for jc in itertools.combinations(range(w), j):
                if k == sum(
                    del_row(c[ii], jc).count("
                ):
                    total += 1

print(total)

Solution (Python):
import itertools
H,W,K=map(int,input().split())
c=[list(input()) for i in range(H)]
count=0
for bit_h,bit_w in itertools.product(range(1<<H),range(1<<W)):
    black=0
    for h,w in itertools.product(range(H),range(W)):
        if c[h][w]=="
            black+=1
    if black==K:
        count+=1
print(count)