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



Sample input:
2 3 2
..#
###


Sample output:
5

Submission status: Accepted

Solution code:
from sys import exit
import copy
import numpy as np
#from collections import deque


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


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] = '$'
        # for l in tmp2:
        #     print(l)
        if count(tmp2) == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:

h, w, k = map(int, input().split())
c = [input() for _ in range(h)] # 行列の入力楽

ans = 0

for i in range(1 << h):#bit全探索行準備塗らない場所の選び方
    for j in range(1 << w): #bit全探索列準備塗らない場所の選び方
        cnt = 0
        for x in range(h):
            for y in range(w):
                if c[x][y] == '#' and (i >> x) & 1 and (j >> y) & 1: #c[x][y]が黒で赤色に塗られていない
                    cnt += 1
        if cnt == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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] == '#' else 0)
  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("#")
            #print(count_black,paint[i])
          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()

Submission status: Accepted

Solution code:
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]=="#" and bit_h[h]&1 and bit_w[w]&1:
                black+=1
        if black==K:
            count+=1
print(count)

Submission status: Accepted

Solution code:
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 == '#') ==K:
    count+=1
print(count)

Submission status: Accepted

Solution code:
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]=='#' for k in range(h) for l in range(w)) for i in range(2**h) for j in range(2**w))
)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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 _ == '#' else 0 for _ in s]
        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()

Submission status: Accepted

Solution code:
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] == '#' else 0)
    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("#")
            #print(count_black,paint[i])
          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] == '#' else 0)
          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()

Submission status: Accepted

Solution code:
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] == "#": cnt += 1
        if cnt == K: ans += 1
print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])


# print(m)
# print(b_list)

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] == '#' and (bit_h >> i) & 1 and (bit_w >> j) & 1:
                    black += 1
        if black == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
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

    # ある行や列を赤く塗るかどうかをビットパターンで表現する
    # ex: H=2, W=3 で、1行目と、2列目と3列目を塗る場合
    #     (0,  1, |  0,   1,   1)
    #     H=1 H=2 | W=1, W=2, W=3
    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]  # ex: (0, 1)
        col_paint_pattern = pattern[H:]  # ex: (0, 1, 1)

        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))

Submission status: Accepted

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

# bit全探索
for maskR in range((1 << H)):
    for maskC in range((1 << W)):
        # print(maskR,maskC)
        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)

Submission status: Accepted

Solution code:
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]=='#': t+=1
    if t==x: a+=1
print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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:
      # l行を選択
      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:
        #k列を選択
        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)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
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] == '#' for i in range(m) for j in range(n)) == k
    print(ans)
resolve()

Submission status: Accepted

Solution code:
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
        # print(binary_j)
        for l in range(len(binary_j)):
            if binary_j[l] == "1":
                for m in range(h):
                    masu_tmp_2[m][l]="-"
                # print(m,l)
        for n in range(h):
            for o in range(w):
                if masu_tmp_2[n][o] == "#":
                    counter +=1
                # print(n,o)
        if counter == k:
            res += 1
        # print(masu_tmp_2)
print(res)
# print(masu_tmp)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# cook your dish here
import sys
import math
# sys.stdin=open('input.txt','r')
# sys.stdout=open('output2.txt','w')
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
# print('hi')
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)

Submission status: Accepted

Solution code:
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('#') == k:
                    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))
    # print(b)
    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))
    # print(b)
    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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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("#") for ii in set(ic) ^ set(range(h))
                ):
                    total += 1

print(total)

Submission status: Accepted

Solution code:
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]=="#" and (bit_h>>h)&1 and (bit_w>>w)&1:
            black+=1
    if black==K:
        count+=1
print(count)

Submission status: Accepted

Solution code:
import itertools
import copy
H, W, K = map(int, input().split())
C = []
for _ in range(H):
    C.append([c for c in input()])

H_list = [i for i in range(H)]
H_comb = []
for i in range(1, H):
    H_comb += itertools.combinations(H_list, i)

W_list = [i for i in range(W)]
W_comb = []
for i in range(1, W):
    W_comb += itertools.combinations(W_list, i)

ans = 0
cnt = 0
for w in C: cnt += w.count('#')
if cnt == K: ans += 1

for wc in W_comb:
    temp_C0 = copy.deepcopy(C)
    for i in sorted(wc, reverse=True):
        for w in temp_C0: w.pop(i)
    cnt = 0
    for w in temp_C0 : cnt += w.count('#')
    if cnt == K: ans += 1

for hc in H_comb:
    temp_C1 = copy.deepcopy(C)
    for i in sorted(hc, reverse=True): temp_C1.pop(i)
    cnt = 0
    for w in temp_C1: cnt += w.count('#')
    if cnt == K: ans += 1
    for wc in W_comb:
        temp_C2 = copy.deepcopy(temp_C1)
        for j in sorted(wc, reverse=True):
            for w in temp_C2: w.pop(j)
        cnt = 0
        for w in temp_C2 : cnt += w.count('#')
        if cnt == K: ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
h, w, K = map(int, input().split())

C = []

for i in range(h):
    c = list(input())
    # print(c)
    C.append(c)
# print(C)
ans = 0
for i in reversed(range(2 ** (h + w))):
    d = copy.deepcopy(C)
    x = []
    for j in reversed(range(h + w)):
        if ((i >> j) & 1):
            x.append(j)
            if j < h:
                del d[j]
            if h <= j:
                m = j - h
                for k in range(len(d)):
                    del d[k][m]
    # print(x)
    count = 0
    for n in d:
        count += n.count('#')
    if count == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	h, w, k = tin()
	bl = [[1 if c == '#' else 0 for c in list(input())] for _ in range(h)]
	#print(bl)
	cc = 0
	for hhi in range(2**h - 
	1):
		for wwi in range(2**w -	1):
			n = 0
			for hi, l in enumerate(bl):
				if hhi & (2**hi) > 0:
					continue
				for wi, v in enumerate(l):
					if wwi & (2**wi) > 0:
						continue
					n += v
			if n == k:
				#pa((hhi, wwi))
				cc += 1
			
	return cc
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)