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 numpy as np
from copy import deepcopy
from heapq import heappop, heappush
from bisect import bisect_left, bisect
from collections import Counter, defaultdict, deque
from itertools import product, permutations, combinations

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

for h in range(H):
    s = list(input())
    for w in range(W):
        if s[w] == ".":
            c[w, h] = 0
        else:
            c[w, h] = 1

n = 0

for wt in product([1, 0], repeat=W):
    for ht in product([1, 0], repeat=H):
        d = deepcopy(c)
        for i in range(W):
            if wt[i] == 1:
                d[i, :] = 0
        for i in range(H):
            if ht[i] == 1:
                d[:, i] = 0
        if np.count_nonzero(d) == K:
            n += 1
print(n)
exit()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

h, w, k = map(int, input().split())
arr = np.empty((0, w), int)
for _ in range(h):
    s = list(input().replace(".", "0").replace("#", "1"))
    arr = np.append(arr, np.array([list(map(int, s))]), axis=0)
cnt = 0
for i in product((0, 1), repeat=h):
    tmp = (arr.T * i).T
    cnt += sum(sum(sum(tmp * j)) == k for j in product((0, 1), repeat=w))
print(cnt)

Submission status: Accepted

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

ans = 0
for hselection in range(1 << H):
    for wselection in range(1 << W):
        count = 0
        for h in range(H):
            for w in range(W):
                if hselection & (1 << h) or wselection & (1 << w):
                    continue
                if C[h][w] == "#":
                    count += 1
        if count == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

h, w, k = map(int, input().split())
clist0 = []
result = 0
for i0 in range(h):
    c = list(input())
    clist0.append(c)
for i in range(2**h):
    for j in range(2**w):
        clist = copy.deepcopy(clist0)
        for hi in range(h):
            #print(i, hi)
            if((i & 2**hi) == 2**hi):
                #print(i, hi)
                for j2 in range(w):
                    clist[hi][j2] = "1"
        for wi in range(w):
            if((j & 2**wi) == 2**wi):
                for i2 in range(h):
                    clist[i2][wi] = "1"
        temp = 0
        #print(clist)
        for ci in clist:
            temp += ci.count("#")
        if(temp == k):
            result +=1
print(result)

Submission status: Accepted

Solution code:
H, W, K = list(map(int, input().split()))
c = []
for _ in range(H):
    c.append( input() )
count = 0
for h_pattern in range( 2**H ):
    for w_pattern in range( 2**W ):
        black_count = 0
        for h in range(H):
            for w in range(W):
                if (h_pattern>>h)&1 and (w_pattern>>w)&1 and c[h][w]=='#':
                    black_count+=1
        if black_count==K:
            count += 1
print(count)

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def fn(mask_r,mask_c):
    cells=0
    for cur_r in range(r):
        for cur_c in range(c):
            if mask_c &(1<<cur_c)==0 or mask_r&(1<<cur_r)==0:continue
            if a[cur_r][cur_c]=='#':cells+=1
    return cells==k
for _ in range(1):#int(stdin.readline())):
    # n=int(stdin.readline())
    ans=0
    r,c,k= map(int,stdin.readline().split())
    a=[input() for _ in range(r)]
    for mask_r in range(1<<r):
        for mask_c in range(1<<c):
            # print(bin(mask_r)[2:],bin(mask_c)[2:])
            if fn(mask_r,mask_c):ans+=1
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
n,m,k = map(int,input().split())
mat = []
for _ in range(n):
    mat.append(list(input()))

def black(row,col):
    new = [mat[i] for i in range(n) if i not in row]
    if not new:return 0
    new = list(zip(*new))
    new = [new[i] for i in range(m) if i not in col]
    if not new:return 0
    return sum([i.count("#") for i in new])
ans = 0
rows = []
cols = []
for i in range(0,n+1):
    rows += list(combinations([i for i in range(n)],i))
for i in range(0,m+1):
    cols += list(combinations([i for i in range(m)],i))
#print(rows,cols)
for row in rows:
    for col in cols:
        if black(set(row),set(col))==k:
            #print(row,col)
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
a = [input() for i in range(H)]
ans = 0
for i in range(1 <<H):
    for j in range(1 <<W):
        black = 0
        for k in range(H):
            for l in range(W):
                if (i >>k)&1 ==0 and (j >>l)&1 == 0 and a[k][l] == '#':
                    black += 1
        if black == 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())
l = []
for _ in range(h):
    s = input().replace(".", "0")
    s = map(int, list(s.replace("#", "1")))
    l.append(np.array(list(s)))
arr = np.array(l)
cnt = 0
for i in product((0, 1), repeat=h):
    tmp = (arr.T * i).T
    for j in product((0, 1), repeat=w):
        if sum(sum(tmp * j)) == k:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import sys
import distutils.util

h, w, k = (int(x) for x in input().split())
count = 0
map = ''
for i in range(h):
    map += sys.stdin.readline().replace('\n','')
map2 = [True]*len(map)
for i in range(len(map)):
    if map[i]=='.': map2[i]=False
map2 = np.array(map2, dtype=bool).reshape((h, w))

for i in range(2**h):
    tmp = bin(i)[2:]
    tmp = '0'*(h-len(tmp)) + tmp
    a = list((bool(distutils.util.strtobool(tmp[i]))
              for i in range(len(tmp))))
    tmp = np.array(a*w).reshape(w, h).transpose()
    for j in range(2**w):
        tmp2 = bin(j)[2:]
        tmp2 = '0'*(w-len(tmp2)) + tmp2
        b = list((bool(distutils.util.strtobool(tmp2[i]))
                  for i in range(len(tmp2))))
        tmp2 = np.array(b*h).reshape(h, w)
        if sum(sum(list(tmp & tmp2 & map2)))==k: count+=1

print (count)

Submission status: Accepted

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

count = 0
for binh in range(2**h):
    for binw in range(2**w):
        redh, redw = bin(binh)[2:].zfill(h), bin(binw)[2:].zfill(w)  # remove suffix '0x'
        squares = [list(row) for row in c]
        for i, rh in enumerate(redh):
            for wh in range(w):
                if rh == '1':
                    squares[i][wh] = '*'
        for j, rw in enumerate(redw):
            for hw in range(h):
                if rw == '1':
                    squares[hw][j] = '*'
        count += sum(row.count('#') for row in squares) == k

print(count)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

count = 0
for ph in itertools.product([0, 1], repeat=h):
    for pw in itertools.product([0, 1], repeat=w):
        squares = np.array([[1 if cell == '#' else -1 for cell in row] for row in c])
        squares[np.array(ph) == 1, :] *= 0
        squares[:, np.array(pw) == 1] *= 0
        count += np.count_nonzero(squares == 1) == k

print(count)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

count = 0
for ph in itertools.product([0, 1], repeat=h):
    for pw in itertools.product([0, 1], repeat=w):
        squares = np.array([[1 if cell == '#' else -1 for cell in row] for row in c])
        squares[np.array(ph) == True, :] *= 0
        squares[:, np.array(pw) == True] *= 0
        if np.count_nonzero(squares == 1) == k:
            count += 1

print(count)

Submission status: Accepted

Solution code:

H, W, K = [int(n) for n in input().split(" ")]
M = []
for _ in range(H):
    a = [n for n in input()]
    assert(len(a) == W)
    M.append(a)

import copy
import itertools
"""
M = [[".", ".", "#"],
     ["#", "#", "#"]
]
W = len(M[0])
H = len(M)
K = 2
"""


def makeCombination(candidate, n, lessFlag):
    if len(candidate) <= 0:
        return [[]]
    _candidate = [n for n in candidate]
    _candidate = sorted(_candidate)
    result = []
    if lessFlag is False:
        tmp = list(set(list(itertools.combinations(_candidate, n))))
        for t in tmp:
            result.append(list(t))
    else:
        for i in range(n):
            result += makeCombination(candidate, i + 1, False)
        result += [[]]
    return result


def check(m, h, w):
    MM = copy.deepcopy(m)
    for a in h:
        for i in range(W):
            MM[a][i] = "R"
    for a in w:
        for i in range(H):
            MM[i][a] = "R"

    count = 0
    for i in range(len(MM)):
        for j in range(len(MM[i])):
            if MM[i][j] == "#":
                count += 1
    return count


HHH = makeCombination([n for n in range(H)], H, True)
WWW = makeCombination([n for n in range(W)], W, True)

OK = 0

for i in range(len(HHH)):
    for j in range(len(WWW)):
        if check(M, HHH[i], WWW[j]) == K:
            OK += 1
print(OK)

Submission status: Accepted

Solution code:
row, col, num = map(int, input().split())

tmp_l = []
board = []
for i in range(row):
  str = input()
  for j in range(col):
    if str[j] == '.':
      tmp_l.append(0)
    if str[j] == '#':
      tmp_l.append(1)
  board.append(tmp_l)
  tmp_l = []

onoff = []
bi = [32, 16, 8, 4, 2, 1]
for i in range(64):
  tmp = i
  for j in bi:
    tmp_l.insert(0, int(tmp / j))
    tmp %= j
  onoff.append(tmp_l)
  tmp_l = []

count = 0
ans = 0
for i in range(2**row):
  for j in range(2**col):
    for k in range(row):
      if onoff[i][k] == 1:
        for l in range(col):
          if onoff[j][l] == 1:
            if board[k][l] == 1:
              count += 1
    if count == num:
      ans += 1
    count = 0

print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
l=[]
for i in range(H):
    S=input()
    l.append(S)
l_2d="".join(l)
x=l_2d.count("#")
for i in range(W):
    S=""
    for j in range(H):
        S+=l[j][i]
    l.append(S)
ans=0
for i in range(2**(H+W)):
    bag=[]
    h=[]
    w=[]
    for j in range(H+W):
        if ((i>>j)&1):
            bag.append(l[j])
            if j<H:
                h.append(j)
            else:
                w.append(j-H)
    bag_2d="".join(bag)
    y=bag_2d.count("#")
    for k in h:
        for m in w:
            if l[k][m]=="#":
                y-=1
    if x-y==K:
        ans+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
a = [input() for i in range(H)]
ans = 0
for i in range(1 << H):
    for j in range(1 << W):
        black = 0
        for k in range(H):
            for l in range(W):
                if (i >> k) & 1 == 0 and (j >> l) & 1 == 0 and a[k][l] == '#':
                    black += 1
        if black == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,K = map(int,input().split())
a = [input() for i in range(h)]
ans = 0
for i in range(1<<h):
    for j in range(1<<w):
        black = 0
        for k in range(h):
            for l in range(w):
                
                if (i>>k)&1 == 0 and (j>>l)&1 == 0 and a[k][l]=='#':
                    black += 1
                    
        if black == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
c = []
row = [0]*H
col = [0]*W
total = 0

for i in range(H):
    c.append(list(input()))
    for j in range(W):
        if c[i][j] == '#':
            row[i] += 1
            col[j] += 1
            total += 1

#print(total)
ans = 0
for i in range(2**(H+W)):
    x = [0]*(H+W)
    ii = i
    for j in range(H+W):
        x[j] = ii % 2
        ii//=2
    #print(x)
    D = 0
    for j in range(H):
        D += row[j]*x[j]
    for j in range(H,H+W):
        D += col[j-H]*x[j]

    for j in range(H):
        for k in range(W):
            if c[j][k] == '#':
                D -= x[j]*x[H+k]
    
    if total -D == K:
        ans += 1
    #print(x,ans)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    ans = 0
    for b1 in range(2**H):
        for b2 in range(2**W):

            c = 0
            for i in range(H):
                for j in range(W):
                    if (b1 >> i) & 1 or (b2 >> j) & 1:
                        continue
                    else:
                        c += f[i][j] == '#'

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





def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations

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

ans = 0
for i in range(h+1):
  for j in range(w+1):
    for ci in combinations(list(range(h)),i):
      for cj in combinations(list(range(w)),j):
        cnt = 0
        for l in ci:
          for m in cj:
            if c[l][m] == "#":
              cnt += 1
        if cnt == k:
          ans += 1
print(ans)

Submission status: Accepted

Solution code:
#C-HandV
import copy
ans = 0
S = []
S_red = []
S_kuro = []
H_parameter = [[0]]
W_parameter = [[0]]
Hsize = 0
Wsize = 0
n1 = 0
n2 = 0
n3 = 0
n4 = 0
n5 = 0
n6 = 0

#入力
H,W,K   = map(int, input().split())
for i in range(H):
    S.append(list(map(str, input())))

#red操作
#H
for n1 in range(1,H+1,1):
    H_parameter.append([n1])
    for n2 in range(1,H+1,1):
        if n2 > n1:
            H_parameter.append([n1,n2])
            for n3 in range(1,H+1,1):
                if n3 > n2:
                    H_parameter.append([n1,n2,n3])
                    for n4 in range(1,H+1,1):
                        if n4 > n3:
                            H_parameter.append([n1,n2,n3,n4])
                            for n5 in range(1,H+1,1):
                                if n5 > n4:
                                    H_parameter.append([n1,n2,n3,n4,n5])
                                    for n6 in range(1,H+1,1):
                                        if n6 > n5:
                                            H_parameter.append([n1,n2,n3,n4,n5,n6])
Hsize = len(H_parameter)
#print(H_parameter)
#print(Hsize)

#W
n1 = 0
n2 = 0
n3 = 0
n4 = 0
n5 = 0
n6 = 0

for n1 in range(1,W+1,1):
    W_parameter.append([n1])
    for n2 in range(1,W+1,1):
        if n2 > n1:
            W_parameter.append([n1,n2])
            for n3 in range(1,W+1,1):
                if n3 > n2:
                    W_parameter.append([n1,n2,n3])
                    for n4 in range(1,W+1,1):
                        if n4 > n3:
                            W_parameter.append([n1,n2,n3,n4])
                            for n5 in range(1,W+1,1):
                                if n5 > n4:
                                    W_parameter.append([n1,n2,n3,n4,n5])
                                    for n6 in range(1,W+1,1):
                                        if n6 > n5:
                                            W_parameter.append([n1,n2,n3,n4,n5,n6])
Wsize = len(W_parameter)
#print(W_parameter)
#rint(Wsize)
Qcount = 0

for l in range(Hsize):
    ll = len(H_parameter[l])
    for m in range(Wsize):
        S_red.clear()
        S_red = copy.deepcopy(S)
        mm = len(W_parameter[m])
        for q in range(ll):
            for r in range(mm):
                if H_parameter[l] != [0]:
                    for p in range(W):
                        S_red[H_parameter[l][q]-1][p]= 'R'
                if W_parameter[m] != [0]:            
                    for s in range(H):
                        S_red[s][W_parameter[m][r]-1]= 'R'
                
        # 黒の数
        Q = 0
        Qcount += 1
        S_kuro.clear()
        for j in range(H):
            for k in range(W):
                S_kuro.append(S_red[j][k])
        Q =S_kuro.count('#')
        #print(l,m,Q)
        #print(S_kuro)          
        if Q == K : ans += 1

# 出力
print(ans)

Submission status: Accepted

Solution code:
info = list(map(int, input().split()))
matrix = [[""] * info[1] for i in range(info[0])]

for i in range(info[0]):
    matrix[i] = list(input())


Black = 0

for i in range(info[0]):
    for j in range(info[1]):
        if matrix[i][j] == "#":
            Black += 1


combination = 0

for i in range(2 ** info[0]):
    non_selected = set()
    count = 0

    for j in range(info[0]):
        if (i >> j) & 1:
            
            for k in range(info[1]):
                if matrix[j][k] == "#":
                    count += 1
        else:
            non_selected.add(j)
    

    for l in range(2 ** info[1]):

        count2 = count
        for t in range(info[1]):
            if (l >> t) & 1:

                for s in non_selected:
                    if matrix[s][t] == "#":
                        count2 += 1

        if (Black - count2) == info[2]:
            combination += 1


print(combination)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
X = [[1 if a == "#" else 0 for a in input()] for _ in range(h)]
ans = 0
for ii in range(1 << h):
  for jj in range(1 << w):
    if sum([sum([X[i][j] for j in range(w) if jj >> j & 1]) for i in range(h) if ii >> i & 1]) == k:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split(' '))
ls, rst = [], 0
for i in range(H):
    ls.append(list(input()))

for i in range(1 << H):
    for j in range(1 << W):
        cnt = 0
        for s in range(H):
            if i >> s & 1:
                continue
            for t in range(W):
                if j >> t & 1:
                    continue
                if ls[s][t] == '#':
                    cnt += 1
        if cnt == K:
            rst += 1
print(rst)

Submission status: Accepted

Solution code:
import copy
H, W, K = map(int, input().split())
lst = []
num = 0
for i in range(H):
    arrange = input()
    num += arrange.count('#')
    lst.append(arrange)
# print(num)
count = 0

for i in range(2**H):
    # print("初期化")
    rlst = copy.copy(lst)
    counted = 0
    rstr = str(format(i, '0' + str(H) + 'b'))
    # print("rstr:" + rstr)
    while '1' in rstr:
        index = rstr.find('1')
        counted += rlst[index].count('#')
        rlst[index] = "." * W
        rstr = rstr.replace('1','0',1)
    # print(counted)
    for j in range(2**W):
        ccounted = counted
        clst = copy.copy(rlst)
        cstr = str(format(j, '0' + str(W) + 'b'))
        # print("cstr:" + cstr)
        while '1' in cstr:
            index = cstr.find('1')
            dlst = ""
            for k in range(H):
                dlst += clst[k][index]
                clst[k] = clst[k][:index] + '.' + clst[k][index+1:]
            ccounted += dlst.count("#")
            cstr = cstr.replace('1','0',1)
        # print(clst)
        # print(str(num-ccounted))
        if num - ccounted == K:
            count += 1

print(count)

Submission status: Accepted

Solution code:
import itertools
# import math
# import sys
# import numpy as np

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
H, W, K = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# S = input()

# d = sorted(d.items(), key=lambda x:x[0])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

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

rows = list(itertools.product((0,1), repeat=H))
columns = list(itertools.product((0,1), repeat=W))

def num_of_blacks(row, column):
    tot = 0
    for i in range(H):
        if row[i] == 0:
            continue
        for j in range(W):
            if column[j] == 0:
                continue
            if cells[i][j] == "#":
                tot += 1
    return tot

ans = 0
for row in rows:
    for column in columns:
        _ = num_of_blacks(row, column)
        if _ == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
number=list(map(int,input().split()))
H,W,K=number[0],number[1],number[2]
masu=[]
for i in range(H):
    tmp=list(str(input()))
    masu.append(tmp)
count=0
ans=0
for cowmask in range(1<<H):
    for rowmask in range(1<<W):
        count=0
        for x in range(H):
            for y in range(W):
                if (cowmask>>x)&1==0 and (rowmask>>y)&1==0 and masu[x][y]=="#":
                    count+=1
        if count==K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
# ABC_173_C_H_and_V.py

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

# bitDP2回ぶん回せば行けるのでは？
# bitが1は残す方で

ans=0
for i in range(1,2**H):
    for j in range(1,2**W):
        resx=[]
        resy=[]
        ct=0
        for k in range(H):
            if (i>>k)&1:
                resx.append(k)
        for l in range(W):
            if (j>>l)&1:
                resy.append(l)
        # print(resx,resy)
        B=[[A[k][l] for l in resy] for k in resx]
        for k in range(len(resx)):
            ct+=B[k].count('#')
        # print(ct)
        if ct==K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
hwk=input().split()
H=int(hwk[0])
W=int(hwk[1])
K=int(hwk[2])
bits=np.zeros(H+1,dtype='int64')
c = [input() for _ in range(H)]
ans=int(0)
while bits[H]==0:
    dp=np.zeros(H*W+1,dtype='int64')
    dp[0]+=1
    for j in range(W):
        kaz=0
        for i in range(H):
            if bits[i]==1 and c[i][j]=='#':
                kaz+=1
        for i in range(H*W,kaz-1,-1):
            dp[i]+=dp[i-kaz]
    ans+=dp[K]

    bits[0]+=1
    bas=0
    while bits[bas]==2:
        bits[bas]=0
        bas+=1
        bits[bas]+=1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
c = [input() for _ in range(H)]
ans = 0
for case in range(2**(H+W)):
    black = 0
    for i in range(H):
        for j in range(W):
            if (case >> i) & 1 and (case >> j + H) & 1 and c[i][j] == "#":
                black += 1
    if black == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
h0, w0, k0 = [ int(x) for x in input().split() ]
found, buf = 0, {}
for i in range(h0): buf[1 << i] = { 1 << j for j,x in enumerate(input()) if x == '#' }
for i in range(1, 1 << h0):
  idx = {}
  for k,vs in buf.items():
    if k & i == 0: continue
    for v in vs: idx[v] = idx.get(v, 0) + 1
  for j in range(1, 1 << w0):
    n = sum([ v for k,v in idx.items() if k & j ])
    if n == k0: found += 1
print(found)

Submission status: Accepted

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

for h in range(2**H):
  for w in range(2**W):
    c = 0
    for i in range(H):
      for j in range(W):
        if (h>>i)&1==0 and (w>>j)&1==0 and C[i][j]=="#":
          c+=1
    if c==K:
      ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline
 
def SI(): return str(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
   
    H, W, K = MI()
    grid = [SI().rstrip('\n') for _ in range(H)]

    n = H + W
    ans = 0
    
    for i in itertools.product(range(2),repeat = H):
        for j in itertools.product(range(2),repeat = W):
            count = 0
            for k in range(H):
                if i[k] == 1:
                    continue
                for l in range(W):
                    if j[l] == 1:
                        continue
                    if grid[k][l] == "#":
                        count += 1
            if count == K:
                ans +=1
    print(ans)
main()

Submission status: Accepted

Solution code:
h,w,k = list(map(int, input().split()))
masu = [input() for _ in range(h)]
ans = 0

def count_num(m, target, goal):
    for i in range(h):
        count = sum(map(lambda x: x.count(target), m))
    
    return count == goal

def change_row(m, i_row_0):
    m[i_row_0] = 'r'*w    
    return m

def change_col(m, j_col_0):
    for i in range(h):
        if j_col_0 < w:
            m[i] = m[i][:j_col_0]+'r'+ m[i][j_col_0+1:]
    return m




for idx_h in range(2**h):
    for idx_w in range(2**w):
        m = masu.copy()
        for i_row, row in enumerate(m):
            if idx_h & (2 ** i_row) > 0:
                m = change_row(m, i_row)

            for j_col, col in enumerate(row):
                if idx_w & (2 ** j_col) > 0:
                    m = change_col(m, j_col)
        
        #print(m)
        if count_num(m, '#', k):
            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())
  
def countb(c):
  num = 0
  for i in range(h):
    num += c[i].count("#")
  return(num)

def printb(c, row, col):
  c = c[:]
  #print(row,col)
  cnt = 0
  while row != 0:
    if row  & 0b1:
     
      c[cnt] = "."*w
    cnt += 1
    row = row >> 1
  
  cnt = 0
  while col != 0:
    #print(col&0b1)
    if col & 0b1:
      for i in range(h):
        c[i] = c[i][:cnt]+"."+c[i][cnt+1:]
    cnt += 1
    col = col >> 1
    
  #print("\n".join(c))
  return countb(c)

ans = 0
for i in range(2**h):
  for j in range(2**w):
    if printb(c,i,j) == k:
      ans += 1
print(ans)

Submission status: Accepted

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

masu = [input() for _ in range(h)]

ans = 0
for idx_h in range(2 ** h):
    for idx_w in range(2 ** w):
        m = masu.copy()
        for i_row, row in enumerate(m):
            for j_col, col in enumerate(row):
                if idx_h & (2 ** i_row) > 0 or idx_w & (2 ** j_col) > 0:
                    # m[i_row][j_col] = 'r'
                    m[i_row] = m[i_row][:j_col] + 'r' + m[i_row][j_col+1:]
        
        count_black = sum(map(lambda x: x.count('#'), m))
        if count_black == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

h,w,k = map(int,input().split())
lines = [input() for v in range(h)]
ans = 0

for ir in range(2**h):
    for ic in range(2**w):
        cnt = 0
        for i in range(h):
            for j in range(w):
                if (ir>>i) & 1 == 0 and (ic>>j) & 1 == 0:
                    if lines[i][j]  == '#':
                      cnt += 1
        if cnt == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
ans=0
for paint_h in range(2**h): #すべての行の塗りつぶし方を2進数で列挙する
 for paint_w in range(2**w): #すべての列の塗りつぶし方を2進数で列挙する
   cnt=0
   for i in range(h): #すべてのi行目j列目の要素についてみる
     for j in range(w):
       if (paint_h>>i)&1==0 and (paint_w>>j)&1==0: #各行のi番目のビットと各列のj番目のビットがともに0であればそのマスは塗りつぶされない
         if board[i][j]=='#': #塗りつぶされないマスが黒マスであれば個数を+1する
           cnt+=1
   if cnt==k: #塗りつぶされない黒マスの個数がKに等しければ答えを+1する
     ans+=1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import copy
import itertools
import numpy as np

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

for i in range(h):
    row = list(input())
    # print(row)
    row = [0 if x=="." else 1 for x in row]
    row = np.array(row).reshape(1, w)
    if i == 0:
        c_matrix = row
    else:
        c_matrix = np.append(c_matrix, row, axis=0)
    
# print(c_matrix, "\n")
row_list = list(range(h))
col_list = list(range(w))
count = 0
for i in range(h+1):
    row_idx = list(itertools.combinations(row_list, i))
    for j in range(w+1):
        col_idx = list(itertools.combinations(col_list, j))
        # print(row_idx, col_idx)
        for row in row_idx:
            for col in col_idx:
                tmp = copy.deepcopy(c_matrix)
                tmp[row, :] = 0 
                tmp[:, col] = 0
                ans = np.sum(np.sum(tmp, axis=1))
                if ans == k:
                    count += 1
                    # print(tmp)
            
print(count)

Submission status: Accepted

Solution code:
from itertools import product

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

p1 = list(product([False, True], repeat=H))
p2 = list(product([False, True], repeat=W))
ans = 0

for i in range(len(p1)):
    for j in range(len(p2)):
        count = 0
        for a in range(H):
            for b in range(W):
                if C[a][b] == "#" and not p1[i][a] and not p2[j][b]:
                    count += 1
        if count == K:
            ans += 1
print(ans)