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
import numpy as np

def input():
    return sys.stdin.readline()[:-1]

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

def bin_list(num, keta):
    return [i for i, x in enumerate(map(int, format(num, f'0{keta}b'))) if x==1]

cnt = 0
for row in range(2**h):
    for col in range(2**w):
        tmp = np.array(s_li)
        tmp[bin_list(row, h),:] = '.'
        tmp[:,bin_list(col, w)] = '.'
        if np.count_nonzero(tmp=='#')==k:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations
    from copy import deepcopy

    h, w, k = map(int, input().split())
    m = [list(input()) for _ in range(h)]
    c = (sum(m,[])).count('#')
    cnt = 0
    for i in range(w + 1):
        for w_ in combinations(list(range(w)), i):
            for j in range(h + 1):
                for h_ in combinations(list(range(h)), j):
                    m_ = deepcopy(m)
                    tmp = c
                    for x in w_:
                        for p in range(h):
                            if m_[p][x] == '#':
                                tmp -= 1
                    for y in h_:
                        for p in range(w):
                            if m_[y][p] == '#':
                                tmp -= 1
                    for x in w_:
                        for y in h_:
                            if m_[y][x] == '#':
                                tmp += 1

                    if tmp == k:
                        cnt += 1

    print(cnt)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools, copy

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

c = []

for _ in range(h):
    c.append(list(input()))

ans = 0

iter_h_list = list(itertools.product([0,1], repeat=h))
iter_w_list = list(itertools.product([0,1], repeat=w))

for iter_h in iter_h_list:
    for iter_w in iter_w_list:
        temp_c = copy.deepcopy(c)

        for i in range(h):
            if iter_h[i] == 1:
                temp_c[i] = ["r" for x in temp_c[i]]

        for j in range(w):
            for i in range(h):
                if iter_w[j] == 1:
                    temp_c[i][j] = "r"

        sum_of_shape = [x.count("#") for x in temp_c]
        if sum(sum_of_shape) == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from itertools import product
h, w, k = map(int, input().split())
C = []
for i in range(h):
    C.append(list(input()))

"""
for i in range(h):
    print(C[i])
"""

def count(C):
    ans = 0
    for i in range(h):
        for j in range(w):
            #rint(i, j)
            #print(C[i][j])
            if C[i][j] == "#":
                ans += 1
    return ans

#print(count(C))

def rewrite(C, h_pat, w_pat):
    ans = deepcopy(C)
    for i, is_write in enumerate(h_pat):
        if is_write == True:
            for j in range(w):
                ans[i][j] = 0
    for j, is_write in enumerate(w_pat):
        if is_write == True:
            for i in range(h):
                ans[i][j] = 0
    return ans

counter = 0
for h_pat in product([0, 1], repeat=h):
    for w_pat in product([0, 1], repeat=w):
        r = rewrite(C, h_pat, w_pat)
        if count(r) == k:
           counter += 1
print(counter)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys
import numpy as np
import itertools
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x, file=sys.stderr)


def solve(H, W, K, data):
    "void()"
    data = (data == 35)
    ret = 0
    for x in itertools.product((0, 1), repeat=W):
        dX = data * x
        for y in itertools.product((0, 1), repeat=H):
            s = (dX.T * y).sum()
            if s == K:
                ret += 1
    return ret


def main():
    H, W, K = map(int, input().split())
    data = np.array([list(input().strip()) for i in range(H)])
    print(solve(H, W, K, data))


T1 = """
2 3 2
..#
###
"""


T2 = """
2 3 4
..#
###
"""

T3 = """
2 2 3
##
##
"""

T4 = """
6 6 8
..##..
.#..#.
#....#
######
#....#
#....#
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    208
    """


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    0
    """


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    1
    """


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    5
    """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
import numpy as np
H, W, K = list(map(int, input().split()))
cnt = 0
mtx = np.zeros((H, W), dtype = np.int)
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            mtx[i][j] = 1

for i in range(2**H):
    mtx_1 = mtx.copy()
    for h in range(H):
        if i >> h & 1:
            mtx_1[h] = [0] * W
    
    for j in range(2**W):
        mtx_2 = mtx_1.copy()
        for w in range(W):
            if j >> w & 1:
                mtx_2[:, w] = [0] * H
        if np.sum(mtx_2) == K:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys, math,os
from io import BytesIO, IOBase
#data = BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from bisect import bisect_left as bl, bisect_right as br, insort
# from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
# from decimal import Decimal
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
#sys.setrecursionlimit(100000 + 1)
INF = 10**9
mod = 998244353


def recur1(r,c,a):
    global ans
    if a==w:
        cnt=0
        for i in range(h):
            for j in range(w):
                if i in r or j in c:
                    continue
                if mat[i][j] == '#':
                    cnt += 1
        if cnt==k:
            ans+=1
    else:
        recur1(r,c, a + 1)
        c1=c.copy()
        c1.add(a)
        recur1(r,c1, a + 1)

def recur(r,a):
    if a==h:
        recur1(r,set(),0)
    else:
        recur(r,a+1)
        r1=r.copy()
        r1.add(a)
        recur(r1,a+1)

h,w,k=mdata()
ans=0
mat=[data() for i in range(h)]
recur(set(),0)
out(ans)

Submission status: Accepted

Solution code:
a = list(map(int, input().split()))
H = int(a[0])
W = int(a[1])
K = int(a[2])
c_h_list = []
for i in range(H):
    c_h_list.append(input())

c_h = []
for i in range(H):
    for j in range(W):
        if c_h_list[i][j] == '.':
            c_h.append(0)
        elif c_h_list[i][j] == '#':
            c_h.append(1)
ret = 0
for h_count in range(2**H):
    for w_count in range(2**W):
        c_h_copy = c_h.copy()
        if h_count % 2 == 1:
            for i in range(W):
                c_h_copy[i] = 0
        if h_count//2 % 2 == 1:
            for i in range(W):
                c_h_copy[i + W * 1] = 0
        if h_count//4 % 2 == 1:
            for i in range(W):
                c_h_copy[i + W * 2] = 0
        if h_count//8 % 2 == 1:
            for i in range(W):
                c_h_copy[i + W * 3] = 0
        if h_count//16 % 2 == 1:
            for i in range(W):
                c_h_copy[i + W * 4] = 0
        if h_count//32 % 2 == 1:
            for i in range(W):
                c_h_copy[i + W * 5] = 0
        if w_count % 2 == 1:
            for i in range(H):
                c_h_copy[i * W] = 0
        if w_count//2 % 2 == 1:
            for i in range(H):
                c_h_copy[i*W + 1] = 0
        if w_count//4 % 2 == 1:
            for i in range(H):
                c_h_copy[i*W + 2] = 0
        if w_count//8 % 2 == 1:
            for i in range(H):
                c_h_copy[i*W + 3] = 0
        if w_count//16 % 2 == 1:
            for i in range(H):
                c_h_copy[i*W + 4] = 0
        if w_count//32 % 2 == 1:
            for i in range(H):
                c_h_copy[i*W + 5] = 0
        if sum(c_h_copy) == K:
            ret += 1
print(ret)

Submission status: Accepted

Solution code:
import copy

def nuri(is_tate, n, hako):
    if is_tate:
        for i in range(len(hako)):
            hako[i][n] = 'r'

    else:
        for i in range(len(hako[n-1])):
            hako[n][i] = 'r'
        

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

for i in range(2 ** (h+w)):
    c_ex = copy.deepcopy(c)
    for j in range(h+w):
        if ((i >> j) & 1):
            if j >= h:
                idx = j-h
                nuri(True, idx, c_ex)
            else:
                idx = j
                nuri(False, idx, c_ex)

    num = 0
    for j in range(len(c_ex)):
        num += c_ex[j].count('#')
    if num == k:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np
import copy

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    #n = int(stdin.readline().rstrip())
    h,w,k = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    words = [stdin.readline().rstrip() for _ in range(h)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    n = h + w
    ans =0
    for i in range(2**n):
        word = copy.deepcopy(words)
        black= 0
        for j in range(n):
            if ((i >> j) & 1):
                if j <= h-1:
                    wo = "." * w
                    word[j] = wo
                else:
                    gyo = ""
                    for e in range(h):
                        wo = list(word[e])
                        wo[j-h] = "."
                        wo = "".join(wo)
                        word[e] = wo
            else:
                pass
        for j in range(h):
            r = word[j]
            black += r.count("#")
        if black == k:
            ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

c = [list(input()) for i in range(H)]

cnt = 0
for i in range(2**H):
    for j in range(2**W):
        cnt_black = 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_black += 1
        if cnt_black == K:
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
H,W,K=map(int, input().split())
m=[[0] * W for i in range(H)]
for i in range(H):
	row = str(input())
	m[i]=list(row)

ans=0

for i in range(2 ** H):
	mpart = []
	for j in range(H):
		if ((i >> j) & 1):
			mpart.append(m[j])
	
	for k in range(2 ** W):
		m2=[]
		for l in range(W):
			if ((k >> l) & 1):
				for _ in range(len(mpart)):
					m2.append(mpart[_][l])
		
		
		if m2.count("#")==K:
			ans+=1


print(ans)



# 2darray

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

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

ans = 0
for i in np.array(list(product([0, 1], repeat=h)), np.bool):
    for j in np.array(list(product([0, 1], repeat=w)), np.bool):
        if np.any(i) and np.any(j):
            arr = grid[i].copy()
            arr = arr[:, j]
            arr = arr.flatten()
            if np.where(arr == "#")[0].shape[0] == k:
                ans += 1

print(ans)

Submission status: Accepted

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

ans = 0

c = []

ab = 0

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

for i in c:
    ab += i.count("#")

for s in range(2**h):
    for t in range(2**w):
        blk = ab
        ipaint = []
        jpaint = []
        for i in range(h):
            if (s >> i) & 1:
                ipaint.append(i)
        
        for j in range(w):
            if (t >> j) & 1:
                jpaint.append(j)

        for ip in ipaint:
            blk -= c[ip].count("#")

        for jp in jpaint:
            for ih in range(h):
                if c[ih][jp] == "#":
                    blk -= 1

        for iip in ipaint:
            for jjp in jpaint:
                if c[iip][jjp] == "#":
                    blk += 1

        if blk == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
h,w,k=map(int,input().split())
l=list()
for i in range(h):
    l.append(input())
ans=0
"""
sh=[]
sw=[0 for i in range(w)]
for i in range(h):
    sh.append(l[i].count('#'))
for i in range(w):
    for j in range(h):
        sw[i]+=l[j][i]=='#'
print(sh,sw)
"""
for i in product((0,1),repeat=h+w):
    p=0
    #print(i,type(i))
    for j in range(h):
        for m in range(w):
            if i[j]==0 and i[m+h]==0 and l[j][m]=='#':
                p+=1
    #print(p,i)
    if p==k:
        ans+=1
        #print(ans)
print(ans)

Submission status: Accepted

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

h=[0]*H
w=[0]*W
ans=0
  
def cycle(x):
  for i in range(len(x)):
    if x[i]==0:
      x[i]=1
      break
    else:
      x[i]=0
  return x

c=0

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


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

    matrix = np.zeros(shape=(H, W), dtype=int)
    for i in range(H):
        cs = input()
        cs = cs.replace('#', '1')
        cs = cs.replace('.', '0')
        matrix[i] = np.array(list(map(int, cs)), dtype=int)

    total = 0

    for h in range(2 ** H):
        for w in range(2 ** W):
            tmp = matrix.copy()
            for i in range(H):
                if (h >> i) & 1:
                    tmp[i] *= 0
            for j in range(W):
                if (w >> j) & 1:
                    tmp[:, j] *= 0
            if tmp.sum() == K:
                total += 1

    return total


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
h, w, k = [int(w) for w in input().split()]
lc = [[1 if w == "#" else 0 for w in list(input())] for _ in range(h)]

lc = np.array(lc)

ans = 0
for i in range(2 ** h):
    # を採用したとき
    cntb = np.zeros(w)
    for j in range(h):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            cntb += lc[j]

    for ii in range(2 ** w):
        t = 0
        for jj in range(w):
            if ((ii >> jj) & 1):
                t += cntb[jj]
        if t == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from itertools import chain


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



C = []
for _ in range(H):
    C.append(list(input()))

for a in product(*((0, 1) for _ in range(H))):
    for b in product(*((0, 1) for _ in range(W))):
        D = []
        E = []
        for i in range(H):
            if a[i]:
                D.append(C[i])
        if not D:
            break
        D = list(zip(*D))
        for j in range(W):
            if b[j]:
                E.append(D[j])
        F = list(chain.from_iterable(E))
        if F.count("#") == K:
            res += 1

print(res)

Submission status: Accepted

Solution code:
from itertools import product
h, w, k = [int(_) for _ in input().split()]

c = [input() for i in range(h)]
ans = 0
for x in product([0, 1], repeat=h):
    for y in product([0, 1], repeat=w):
        d = 0
        for i in range(h):
            for j in range(w):
                if c[i][j] == '#' and x[i] and y[j]:
                    d += 1
        if d == k:
            ans += 1

print(ans)

Submission status: Accepted

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

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

cnt_black = 0

for i in range(H):
    for j in range(W):
        if c[i][j] == "#":
            cnt_black += 1

ans = 0


def bit_full_search(H, W):
    global ans
    # 縦
    for i in range(2 ** H):
        # 横
        for j in range(2 ** W):
            changed = [[False for _ in range(W)] for _ in range(H)]
            cnt = 0
            for h in range(H):
                if (i >> h) & 1:
                    for w in range(W):
                        if not changed[h][w] and c[h][w] == "#":
                            changed[h][w] = True
                            cnt += 1
            for w in range(W):
                if (j >> w) & 1:
                    for h in range(H):
                        if not changed[h][w] and c[h][w] == "#":
                            changed[h][w] = True
                            cnt += 1

            if cnt_black - cnt == K:
                ans += 1


bit_full_search(H, W)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    H,W,K = map(int, input().split())
    C = []
    for _ in range(H):
        S = input()
        cc = []
        for s in S:
            cc.append(1 if s == "#" else 0)
        C.append(cc)
    ans = 0
    for h in range(1<<H):
        for w in range(1<<W):
            tmp = 0
            for kh in range(H):
                if h>>kh & 1:
                    for kw in range(W):
                        if w>>kw & 1:
                            tmp += C[kh][kw]
            if tmp == K:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

c = [list(input()) for i in range(H)]

tate = 2 ** H
yoko = 2 ** W

ans = 0
for i in range(1, tate+1):
    for j in range(1, yoko+1):
        kuro = 0
        for x in range(H):
            for y in range(W):
                if i >> x & 1 and j >> y & 1 and c[x][y] == '#':
                    kuro += 1
        if kuro == K:
            ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2 ** H):
    gyou = [False]*H
    for j in range(H):
        if ((i >> j) & 1):
            gyou[H - 1 - j] = True
    #print(gyou)
    for k in range(2 ** W):
        retu = [False]*W
        for l in range(W):
            if ((k >> l) & 1):
                retu[W - 1 - l] = True
        #print(retu)
        count = 0
        for m in range(H):
            for n in range(W):
                if C[m][n] == "#" and gyou[m] == True and retu[n] == True:
                    count += 1
        if count == K:
            ans += 1

print(ans)

Submission status: Accepted

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

rbits=[]
for i in range(2**h):
    s=bin(i)
    s=s[s.index('b')+1:]
    s=(h-len(s))*'0'+s
    rbits.append(s)

cbits=[]
for i in range(2**w):
    s=bin(i)
    s=s[s.index('b')+1:]
    s=(w-len(s))*'0'+s
    cbits.append(s)


    
ans=0


for i in rbits:
    for j in cbits:
        a=0
        for c in range(h):
            if i[c]=='1':
                for e in range(w):
                    if j[e]=='1' and d[c][e]=='#':
                        a+=1
        if a==k:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

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

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

    cnt = 0
    for bit_h in range(2**h):
        for bit_w in range(2**w):
            b_cnt = b_init

            for i in range(h):
                for j in range(w):
                    if ((bit_h >> i) & 1) or ((bit_w >> j) & 1):
                        if c[i][j] == '#':
                            b_cnt -= 1

            if b_cnt == k:
                cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations as cmb

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

black = 0
for i in range(H):
    for j in range(W):
        if C[i][j] == "#":
            black += 1

if black < K:
    print(0)
    exit()

res = 0
for h in range(1, H + 1):
    hc = cmb(range(H), h)
    for a in hc:
        for w in range(1, W + 1):
            wc = cmb(range(W), w)
            for b in wc:
                cnt = 0
                for i in a:
                    for j in b:
                        if C[i][j] == "#":
                            cnt += 1
                if cnt == K:
                    # print(a, b)
                    res += 1

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

H,W,K = inpl()
field = [[] for _ in range(H)]
for ii in range(H):
    C = str(input())
    for c in C:
        field[ii].append(c)
ans = 0
kumi = list(itertools.product([0,1],repeat=(H+W)))
for k in kumi:
    fieldf = copy.deepcopy(field)
    for i,o in enumerate(k):
        if o==1:
            if i <= H-1:
                for j in range(W):
                    fieldf[i][j] = '.'
            else:
                for jj in range(H):
                    fieldf[jj][i-H] = '.'
    count = 0
    for l in range(H):
        for ll in range(W):
            if fieldf[l][ll] == '#':
                count += 1
    if K ==count:
        ans+= 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

H, W, K = LI()
c = [[0 for j in range(W)] for i in range(H)]

for h in range(H):
    c[h] = list(str(input()))

# print(c)
for h in range(H):
    for w in range(W):
        if c[h][w] == ".":
            c[h][w] = 0
        else:
            c[h][w] = 1 


"""
2 ** (H + W)通り試せば良い
"""
ans = 0
# 10進数のnを2進数のリストに変換


def n2kdigit(n,k):
    digits = [0 for i in range(H + W)]
    tmp = 0
    while n > 0:
        digits[tmp] = n % k
        n = n // k
        tmp += 1

    return digits

for i in range(2 ** (H + W)):
    cnt = 0
    c_ = copy.deepcopy(c)
    digits = n2kdigit(i, k = 2)
    for j, digit in enumerate(digits):
        if digit == 1:
            if j >= H:
                for h in range(H):
                    # print(j - H -1)
                    c_[h][j - H - 1] = 0
            else:
                "Hを示す"
                c_[j] = [0 for k in range(W)]
    # print(c_)
    for h in range(H):
        cnt += sum(c_[h])
    if cnt == K:
        ans += 1

print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**h):
    h_i = bin(i)
    h_i = ("0"*(h-len(h_i)+2))+h_i[2:]
    for j in range(2**w):
        w_i = bin(j)
        w_i = ("0"*(w-len(w_i)+2))+w_i[2:]
        cnt=0
        for k in range(h):
            if h_i[k]=="1":
                continue
            for m in range(w):
                if w_i[m]=="1":
                    continue
                if l[k][m]=="#":
                    cnt+=1
        if cnt==p:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools as it
h, w, k = map(int, input().split())

c = [list(input()) for _ in range(h)]

hprols = list(it.product(range(2), repeat=h))
wprols = list(it.product(range(2), repeat=w))

ans = 0


for hpro in hprols:
    for wpro in wprols:
        tmpk = 0
        for i in range(len(hpro)):
            for j in range(len(wpro)):
                if hpro[i] == 0:
                    if wpro[j] == 0:
                        if c[i][j] == "#":
                            tmpk += 1
        if tmpk == k:
            ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
import sys

h, w, k = map(int, input().split())
c = [i.split() for i in sys.stdin.readlines()]
ans = [0]

def dfs(A):
    if len(A) == h+w:
        tmp = ""
        cnt = 0
        for i in range(h+w):
            if i < h:
                if A[i]:
                    tmp += "".join(c[i])
            else:
                if A[i]:
                    cnt += tmp[i-h::w].count("#")
        if cnt == k:
            ans[0] += 1
        return

    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()

dfs([])
print(ans[0])

Submission status: Accepted

Solution code:
from copy import deepcopy
def toCount(L):
    return [ 1 if i == "#" else 0 for i in L]
    
def resolve():
    H,W,K = map(int,input().split())
    C=[toCount(input()) for i in range(H)]
    count = 0

    rc = list(BitSeacher(H))

    for rows in rc:
        for cc in range(2**W):
            
            cols = bst(cc,W)

            TC = deepcopy(C)
            for i in rows:
                TC[i]=[0]*W
            for i in cols:
                for j in range(H):
                    TC[j][i]=0

            if K==sum(map(sum,TC)):
                count +=1

    print(count)

def bst(val,bitcount):
        ans =[]
        flg =1
        for i in range(bitcount):
            if flg & val != 0:
                ans.append(i)
            flg = flg.__lshift__(1)
        return ans


class BitSeacher:
    def __init__(self,bitcount):
        self.counter =0
        self.bitcount = bitcount
        self.mx = 2**bitcount-1
    
    def __next__(self):
        if self.counter > self.mx:
            raise StopIteration()
        ans =[]
        flg =1
        for i in range(self.bitcount):
            if flg & self.counter != 0:
                ans.append(i)
            flg = flg.__lshift__(1)
        self.counter+=1
        return ans

    def __iter__(self):
        return self

resolve()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

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

A = np.zeros((H, W), dtype=int)
for r in range(H):
    for c, v in enumerate(input()):
        A[r, c] = 1 if v == '#' else 0

ans = 0
ttl = A.sum().item()

for choses_r in product([0, 1], repeat=H):
    for choses_c in product([0, 1], repeat=W):
        mask = np.zeros_like(A)
        mask[np.flatnonzero(choses_r), :] = 1
        mask[:, np.flatnonzero(choses_c)] = 1

        if ttl - A[mask > 0].sum() == K:
            ans += 1

print(ans)