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:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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


ANS = []
def dfs(l):
    if len(l) == H + W:
        h = l[:H]
        w = l[-W:]
        # print("l: {}".format(l))
        # print("h: {}".format(h))
        # print("w: {}".format(w))
        # quit()
        cnt = 0
        for y in range(H):
            for x in range(W):
                if h[y] or w[x]:
                    continue
                if masu[y][x] == "#":
                    cnt += 1
        # print(cnt)
        if cnt == K:
            # print("l: {}".format(l))
            # print("h: {}".format(h))
            # print("w: {}".format(w))
            # print("----------=")
            ANS.append(1)
        return
    for b in [0, 1]:
        l.append(b)
        dfs(l)
        l.pop()
    
dfs([])
ans = len(ANS)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import copy
h, w, k = map(int, input().split())
m = []
for i in range(h):
  tmp_m = []
  s = input()
  for j in range(w):
    if s[j] == ".":
      tmp_m.append(0)
    else:
      tmp_m.append(1)
  m.append(tmp_m)

m = np.array(m)
n = h + w
cnt = 0
for i in range(2 ** n):
  l = []
  for j in range(n):
    if ((i >> j) & 1):
      l.append(j)
  curr_m = copy.deepcopy(m)
  for a in l:
    if a < w:
      if a != w:
        curr_m[:, a] = 0
    else:
      a -= w
      if a != h:
        curr_m[a, :] = 0
  if np.sum(curr_m) == k:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
input =sys.stdin.readline
import numpy as np
import itertools

H,W,K=(int(x) for x in input().rstrip('\n').split())

for i in range(H):
  x = list(input().rstrip('\n'))
  y = [0 if p=='.' else 1 for p in x]
  if i == 0:
    stage=np.array([y])
    stage=np.reshape(stage,(1,W))
  else:
    sta = np.array([y])
    sta=np.reshape(sta,(1,W))
    stage = np.append(stage,sta,axis=0)
total_h = [x for x in itertools.product((0,1),repeat=H)]
total_w = [x for x in itertools.product((0,1),repeat=W)]
res = 0
for h in total_h:
  for w in total_w:
    sta2 = [[0]*W]*H
    for i in range(H):
      if h[i]==1:
        sta2[i]=[1]*W
      else:
        sta2[i]=list(w)
    sta2 =np.array(sta2)
    sta_n = stage-sta2
    if np.sum(sta_n>0)==K:
      res += 1
print(res)

Submission status: Accepted

Solution code:

# count # char
def count_black(grid,painted_row,painted_col):
    count = 0
    for id_row,row in enumerate(grid):
        for id_col,item in enumerate(row):
            if painted_row[id_row] == 0 and painted_col[id_col] == 0 and item == "#":
                count += 1
    return count


# generate a binary array, len = limit
def generate_selection(limit=0):
    result = []
    arr = [0 for i in range(limit)]
    max_result_len = limit**2

    while True:
        result.append(arr.copy())

        pos_to_change = -1
        for i in range(limit-1,-1,-1):
            if arr[i] == 0:
                pos_to_change = i
                break
        
        if pos_to_change == -1:
            break
        
        arr[pos_to_change] = 1
        for i in range(pos_to_change+1,limit):
            arr[i] = 0
    
    return result

if __name__ == "__main__":
    h,w,k = [int(i) for i in input().split()]
    grid = []
    for i in range(h):
        row = input()
        grid.append(row)
    
    # generate configuration for row and col selection
    row_selections = generate_selection(limit=h)
    col_selections = generate_selection(limit=w)


    result = 0
    for row_selection in row_selections:
        for col_selection in col_selections:
            if count_black(grid,row_selection,col_selection) == k:
                result += 1
    
    print(result)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
ss = []
for i in range(h):
    s = list(input())
    ss.append(s)
ans = 0
for i in range(2**h):
    for j in range(2**w):
        count = 0
        for x in range(h):
            for y in range(w):
                if i>>x&1 == 1 or j>>y&1 == 1:continue
                if ss[x][y] == "#" : 
                    count += 1 
        if count == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations 
def powerset(string): 
    al=[]
    for i in range(0,len(string)+1): 
        sl=[]
        for element in combinations(string,i): 
            al.append(element)
    return al
import sys
def check(l,row,col,el,r,c):
    cc=0
    
    for i in range(r):
        for j in range(c):
            if(l[i][j]=="#" and i not in row and j not in col):
                cc+=1
    
    if cc==el:
        return True;
    return False



r,c,k=map(int,input().split())
l=[]
for i in range(r):
    tt=list(input())
    l.append(tt)
s1=[]
for i in range(r):
    s1.append(i)
s2=[]
for i in range(c):
    s2.append(i)
row=powerset(s1)
col=powerset(s2)
ans=0

for i in row:
    for j in col:
        if(check(l,i,j,k,r,c)):
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

H, W, K = map(int, input().split())
c = [[] for _ in range(H)]
for i in range(H):
    s = input()
    for j in s:
        if j == '.':
            c[i].append(0)
        else:
            c[i].append(1)

ans = 0
for bit in range(1 << (H+W)):
    red_array = np.full((H, W), False)
    cnt = 0
    for i in range(H+W):
        # print(bin(bit), i, bit>>i, bit>>i == 1, i<H, i-H)
        if (bit>>i)&1 == 1:
            if i < H:
                red_array[i,:] = True
            else:
                red_array[:,i-H] = True
    # print(bin(bit))
    # print(red_array)
    for y in range(H):
        for x in range(W):
            # print(bit, y, x, c[y][x], red_array[y,x],c[y][x] == 1 and not red_array[y, x])
            if c[y][x] == 1 and not red_array[y, x]:
                cnt += 1
    # print(cnt)
    if cnt == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

H, W, K = map(int, input().split())
# C = [["."] * (W + 1)]
C = []

for _ in range(H):
    # c = ["."] + list(input())
    c = list(input())

    C.append(c)

C = np.array(C)
# print(C)
cnt = 0

chooseH = list(product([False, True], repeat=(H)))
chooseW = list(product([False, True], repeat=(W)))

for array_h in chooseH:
    for array_w in chooseW:
        D = np.copy(C)
        D[array_h, :] = "R"
        D[:, array_w] = "R"
        # print(array_h, array_w, D.flatten(), np.sum(D.flatten() == "#"))
        if np.sum(D.flatten() == "#") == K:
            cnt += 1


# for i in range(H + 1):
#     for j in range(W + 1):
#         D = np.copy(C)
#         D[i, :] = "R"
#         D[:, j] = "R"
#         print(i, j, D.flatten(), np.sum(D.flatten() == "#"))
#         if np.sum(D.flatten() == "#") == K:
#             cnt += 1

print(cnt)

Submission status: Accepted

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

# 縦横の黒の数
y=[0]*w
x=[0]*h
for i in range(h):
    x[i]=c[i].count('#')

for i in range(w):
    for j in range(h):
        if c[j][i]=='#':
            y[i]+=1
qq=sum(x)

ans=0
for i in range(2**h):
    p=[]
    for i2 in range(h):
        if (i>>i2)&1:
            p.append(i2)
    for j in range(2 ** w):
        cnt = qq
        q = []
        for j2 in range(w):
            if (j >> j2) & 1:
                q.append(j2)
        for v in p:
            cnt -= x[v]
        for v2 in q:
            cnt -= y[v2]
        for v3 in p:
            for v4 in q:
                if c[v3][v4] == '#':
                    cnt += 1

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

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    h, w, k = MI()
    C = []
    for _ in range(h):
        C.append(input())
    c_h = [0]*h
    c_w = [0]*w
    cnt = 0
    for i in range(h):
        for j in range(w):
            if C[i][j] == '#':
                c_h[i] += 1
                c_w[j] += 1
                cnt += 1
    ans = 0
    for i in range(2**h):
        for j in range(2**w):
            cnt_temp = cnt
            row = []
            col = []
            for ii in range(h):
                if ((i >> ii) & 1):
                    cnt_temp -= c_h[ii]
                    row.append(ii)
            for jj in range(w):
                if ((j >> jj) & 1):
                    cnt_temp -= c_w[jj]
                    col.append(jj)
            for ro in row:
                for co in col:
                    if C[ro][co] == '#':
                        cnt_temp += 1
            if cnt_temp == k:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

count = 0
for i in range(2**h):
    row = []
    r = 0
    while i:
        if i & 1:
            row.append(r)
        i >>= 1
        r += 1

    for j in range(2**w):
        col = []
        c = 0
        while j:
            if j & 1:
                col.append(c)
            j >>= 1
            c += 1

        black = 0
        for r in row:
            for c in col:
                if grid[r][c] == "#":
                    black += 1

        if black == k:
            count += 1

print(count)

Submission status: Accepted

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

H,W,K = map(int,input().split())
c = int_mtx(H)
ans = 0

for ih in range(2**H):

    for iw in range(2**W):

        ca = c.copy()

        for jh in range(0,H):

            for jw in range(0,W):

                if ((ih >> jh) & 1):
                    ca[jh,:] = 0
                if ((iw >> jw) & 1):
                    ca[:,jw] = 0

        if np.count_nonzero(ca == "#") == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

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

blackCount = 0
for c in cL:
    for item in c:
        if item == "#":
            blackCount += 1

ans = 0
for x in range(w + 1):
    for y in range(h + 1):
        for x2 in itertools.combinations(range(w), x):
            for y2 in itertools.combinations(range(h), y):
                yCnt = 0
                xCnt = 0
                for y4 in y2:
                    # 該当のそれぞれのコマ数
                    xCnt += cL[y4].count("#")
                for x4 in x2:
                    for y3 in range(h):
                        if cL[y3][x4] == "#":
                            yCnt += 1
                th = 0
                for xa in x2:
                    for ya in y2:
                        if cL[ya][xa] == "#":
                            th += 1
                _sum = blackCount - yCnt - xCnt + th
                if k == _sum:
                    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import copy

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

ans = 0
cnt = 0

for Hbit in product([0,1], repeat = H):
    c = copy.deepcopy(d)
    for x,name in enumerate(Hbit):
        if name == 1:
            for j in range(W):
                c[x][j] = "r"
    e = copy.deepcopy(c)
    for Wbit in product([0,1], repeat = W):
        c = copy.deepcopy(e)
        for x,name in enumerate(Wbit):
            if name == 1:
                for j in range(H):
                    c[j][x] = "r"
        
        for i in range(H):
            for j in range(W):
                if c[i][j] == "#":
                    cnt += 1
        
        if cnt == K:
            ans += 1
        
        cnt = 0

print(ans)

#bit全探索
#2^10の例

Submission status: Accepted

Solution code:
from itertools import combinations as comb


def main():

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

    for h in range(H):
        for w in range(W):
            for i in comb(range(H), h):
                for j in comb(range(W), w):
                    black_sum = 0
                    for k1 in range(H):
                        if k1 in i:
                            continue
                        for k2 in range(W):
                            if k2 in j or lst[k1][k2] == ".":
                                continue
                            black_sum += 1
                    if black_sum == K:
                        # print(f"{i = }, {j = }, {black_sum = }, {ans = }")
                        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(input())

ans=0
for i in range(H+1):
  for j in range(W+1):
    for n in itertools.combinations(list(range(H)),i):
      for m in itertools.combinations(list(range(W)),j):
        count = 0
        for a in n:
          for b in m:
            if(C[a][b]=="#"):count+=1
        if(count == K):
          ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
import numpy as np
H, W, K = map(int, input().split())
C = np.array([[1 if a == '#' else 0 for a in input()] for _ in range(H)])

HA = 2 ** H
WA = 2 ** W



ans = 0
for i in range(HA):
    R = np.copy(C)
    for j in range(H):
        if (i >> j) & 1:
            R[j] = 0
    for k in range(WA):
        RR = np.copy(R)
        for l in range(W):
            if (k>>l) & 1:
                RR[:,l]=0
        if np.sum(RR) == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

ans = 0

for i in H:
    for j in W:
        for e in range(h):
                d[e] = c[e]
        #print(d)
        a = 0
        for x in range(h):
            if i[x] == 1:
                d[x] = 'xxxxxx'
            else:
                for y in range(w):
                    if j[y] == 1:
                        d[x] = d[x][:y] + 'x' + d[x][y+1:]
            for D in d[x]:
                if D == '#':
                    a += 1
        #print(d, i, j)
        if a == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

ans = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        bin_i = format(i, '0{}b'.format(h))
        bin_j = format(j, '0{}b'.format(w))
        black = 0
        for ch in range(h):
            for cw in range(w):
                if bin_i[ch] == '1':
                    continue
                if bin_j[cw] == '1':
                    continue
                if board[ch][cw] == '#':
                    black += 1
        if black == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy


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

R = [format(i, "0" + str(h) + "b") for i in range(2**h)]
C = [format(j, "0" + str(w) + "b") for j in range(2**w)]

ans = 0
for r in R:
    for c in C:
        tmp = deepcopy(grid)
        for i in range(h):
            if r[i] == "1":
                for j in range(w):
                    tmp[i][j] = "R"
        for j in range(w):
            if c[j] == "1":
                for i in range(h):
                    tmp[i][j] = "R"
        cnt = 0
        for i in range(h):
            for j in range(w):
                if tmp[i][j] == "#":
                    cnt += 1
        if cnt == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    H, W, K = map(int, input().split())
    c_list = [input() for i in range(H)]
    c_list_list = [ [(0 if c[j]=="." else 1) for j in range(W) ] for c in c_list]

    counter = 0
    for i in range(pow(2, H+W)):
        bin_i = format(i, "b").zfill(H+W)
        this_c_list_list = [c_list[:] for c_list in c_list_list]
        for row in range(H):
            if bin_i[row] == "1":
                this_c_list_list[row] = [0]*W
        for column in range(W):
            if bin_i[H+column] == "1":
                for j in range(H):
                    this_c_list_list[j][column] = 0
        sum_1 = sum([sum(c_list) for c_list in this_c_list_list])
        #print(this_c_list_list)
        if sum_1 == K:
            counter += 1
        #print(bin_i, sum_1)
    print(counter)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

h, w, k = map(int, input().split())
c = np.empty((h, w), dtype='U1')
for i in range(h):
    c[i] = list(input())

res = 0
for arr in product(range(2), repeat=h+w):
    a = arr[:h]
    b = arr[h:]
    d = np.copy(c)
    for i in range(h):
        if not a[i]:
            continue
        d[i] = ['R'] * w
    for i in range(w):
        if not b[i]:
            continue
        d[:, i] = ['R'] * h
    if np.count_nonzero(d == '#') == k:
        res += 1
print(res)

Submission status: Accepted

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

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

h_list = list(range(H))
w_list = list(range(W))

h_result=[]
for n in range(1,len(h_list)+1):
    for conb in itertools.combinations(h_list, n):
        h_result.append(list(conb)) #タプルをリスト型に変換
h_result.append([100])
#print(h_result)

w_result=[]
for n in range(1,len(w_list)+1):
    for conb in itertools.combinations(w_list, n):
        w_result.append(list(conb)) #タプルをリスト型に変換
w_result.append([100])
#print(w_result)

ans = 0

for H_item in h_result:
    for W_item in w_result:

        tmp = 0
        for k in range(H):
            if k in H_item:
                continue
            for l in range(W):
                if l in W_item:
                    continue
                if M[k][l] == '#':
                    tmp += 1
        if K == tmp:
            ans += 1

print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2 ** H):
    for k in range(2 ** W):
        black = 0
        for j in range(H):
            if (i >> j) & 1:
                for l in range(W):
                    if (k >> l) & 1:
                        if c[j][l] == "#":
                            black += 1
        if black == K: ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

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

for h in range(2**H):
    for w in range(2**W):
        tmp = copy.deepcopy(C)
        w_bin = bin(w)[2:].zfill(W)
        h_bin = bin(h)[2:].zfill(H)
        for index_w,flag_w in enumerate(w_bin):
            for index_h,flag_h in enumerate(h_bin):
                if flag_h == '1':
                    tmp[index_h] = ['.' for _ in range(W)]
                if flag_w == '1':
                    tmptmp = [list(x) for x in zip(*tmp)]
                    tmptmp[W-index_w-1] = ['.' for _ in range(H)]
                    tmp = [list(x) for x in zip(*tmptmp)]
        a = 0
        for i in tmp:
            a += i.count('#')
        if K == a:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

matrix = np.zeros((H, W))
for x in range(H):
    for y in range(W):
        if C[x][y] == '#':
            matrix[x, y] = 1

n_success = 0
for h in range(H + 1):
    for rows in itertools.combinations(range(H), h):
        for w in range(W + 1):
            for cols in itertools.combinations(range(W), w):
                X = matrix.copy()
                X[rows, :] = 0
                X[:, cols] = 0
                if X.sum() == K:
                    n_success += 1
print(n_success)

Submission status: Accepted

Solution code:

from collections import deque



# for #!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


# # region fastio

# BUFSIZE = 8192


# class FastIO(IOBase):
#     newlines = 0

#     def __init__(self, file):
#         self._fd = file.fileno()
#         self.buffer = BytesIO()
#         self.writable = "x" in file.mode or "r" not in file.mode
#         self.write = self.buffer.write if self.writable else None

#     def read(self):
#         while True:
#             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
#             if not b:
#                 break
#             ptr = self.buffer.tell()
#             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
#         self.newlines = 0
#         return self.buffer.read()

#     def readline(self):
#         while self.newlines == 0:
#             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
#             self.newlines = b.count(b"\n") + (not b)
#             ptr = self.buffer.tell()
#             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
#         self.newlines -= 1
#         return self.buffer.readline()

#     def flush(self):
#         if self.writable:
#             os.write(self._fd, self.buffer.getvalue())
#             self.buffer.truncate(0), self.buffer.seek(0)


# class IOWrapper(IOBase):
#     def __init__(self, file):
#         self.buffer = FastIO(file)
#         self.flush = self.buffer.flush
#         self.writable = self.buffer.writable
#         self.write = lambda s: self.buffer.write(s.encode("ascii"))
#         self.read = lambda: self.buffer.read().decode("ascii")
#         self.readline = lambda: self.buffer.readline().decode("ascii")


# sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
# input = lambda: sys.stdin.readline().rstrip("\r\n")
from bisect import bisect_left as bl
from math import log2,ceil
from heapq import heappush, heappop
from itertools import permutations
# from copy import deepcopy 
def main():
    # for t in range(int(input())):
        # n = int(input())
        # d = dict()
        h,w,k = [int(j) for j in input().split()]
        l = [i for i in range(h)]
        m = [i for i in range(w)]
        l_ = [[0], []]
        for i in range(1,h):
            # print(i)
            # print(l_)
            # print(l_)
            for ls in range(len(l_)):
                # print(ls)
                l_.append(l_[ls]+[l[i]])
        m_ = [[0], []]
        for i in range(1,w):
            # print(i)
            # print(l_)
            # print(l_)
            for ls in range(len(m_)):
                # print(ls)
                m_.append(m_[ls]+[m[i]])
                # break
        # print(l_)
        ct = 0
        ip = []
        for i in range(h):
            ip.append(list(input()))
            for j in range(w):
                if ip[i][j]=='#':
                    ct+=1
        fct = 0
        for lh in l_:
            for lw in m_:
                ct_ = ct
                for r in range(h):
                    for c in range(w):
                        if ip[r][c]=='#':
                            if (r in lh or c in lw):
                                ct_-=1
                if ct_==k:
                    fct+=1
        print(fct)
            # heappush(h, l[i])

        


        
        




# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# C

import copy
import itertools

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

ans = 0

for i in range(2**w):
    _c_l = copy.deepcopy(list(zip(*c_l)))
    for x in range(w):
        if (i >> x) & 1:
            _c_l[x] = [0] * h
    _c_l = list(zip(*_c_l))
    for j in range(2**h):
        __c_l = copy.deepcopy(_c_l)
        for y in range(h):
            if (j >> y) & 1:
                __c_l[y] = [0] * w
        _list = list(itertools.chain.from_iterable(__c_l))
        if _list.count("#") == k:
            ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import itertools
from sys import stdin
input = stdin.readline


def main():
  H, W, K = list(map(int, input().split()))
  map_ = [input()[:-1] for _ in range(H)]
  # print(map_)
  hseq = range(H)
  wseq = range(W)
  hcomb = []
  wcomb = []
  for i in range(H):
    hcomb.extend(list(itertools.combinations(hseq, i)))
  for i in range(W):
    wcomb.extend(list(itertools.combinations(wseq, i)))

  # print(hcomb)
  # print(wcomb)
  num_comb = 0
  for i in range(len(hcomb)):
    for j in range(len(wcomb)):
      cnt = 0
      # print(hcomb[i], wcomb[j])
      if not(len(hcomb[i]) or len(wcomb[j])):
        for hh in range(H):
          for ww in range(W):
            if map_[hh][ww] == '#':
              cnt += 1

      if not len(hcomb[i]):
        # print('h')
        for hh in range(H):
          for ww in wcomb[j]:
            if map_[hh][ww] == '#':
              cnt += 1

      elif not len(wcomb[j]):
        # print('w')
        for hh in hcomb[i]:
          for ww in range(W):
            if map_[hh][ww] == '#':
              cnt += 1

      else:
        for hh in hcomb[i]:
          for ww in wcomb[j]:
            if map_[hh][ww] == '#':
              cnt += 1
      if cnt == K:
        # print(i, j)
        num_comb += 1

  print(num_comb)


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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:
 #           print(gyo[Gyo],retu[Retu])
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
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 == '#')
    #print(f"black={black}")
    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 == '#')
                    #print(f"black={black} iconb={iconb} jconb={jconb}")
                    if black == K:
                        count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

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