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
input = sys.stdin.readline
H, W, K = map(int, input().split())
S = [input()[:-1] for _ in [0]*H]
N = H+W
ans = 0
for bitH in range(1 << H):
    T = []
    for h in range(H):
        if bitH >> h & 1:
            T.append(S[h])

    for bitW in range(1 << W):
        cnt = 0
        for w in range(W):
            if bitW >> w & 1:
                for t in T:
                    cnt += 1 if t[w] == "#" else 0

        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

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

for paint_h in range(2**h):#全行の塗り潰し方を数値に当てはめ
    for paint_w in range(2**w):#全列の塗り潰し方を数値に当てはめ
        cnt = 0
        for i in range(h):
            for j in range(w):
                if (paint_h >> i) & 1 == 0 and (paint_w >> j) & 1 == 0:
#各行のi番目のビットと各列のj番目のビットが共に0であればそのマスは塗られていない
                    if board[i][j]=='#':#塗られていなくてマスが黒ならば
                        cnt+=1
        if cnt==k:#各塗りかたに対して個数を確認するためにこのインデントになる
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

#print((-3)&3)
'''for i in range(10):
    j=i-(i&(-i))
    print(j)
    k=j-(j&(-j))
    print(k)
    print()'''
import copy
H,W,K=map(int,input().split())
L=[[x for x in input().rstrip()] for i in range(H)]
ans=0
#print(L[:])
for i in range(2**H):
    for j in range(2**W):
        C=copy.deepcopy(L)
        #print(C)
        for k in range(H):
            if (i>>k&1):
                C[k]=["r"]*W
        for l in range(W):
            if (j>>l&1):
                for m in range(H):
                    C[m][l]="r"
        count=0
        for p in range(H):
            for q in range(W):
                if C[p][q]=="#":
                    count+=1
        if count==K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
from math import factorial as fact
import math
import sys
from itertools import product
import numpy as np
from collections import Counter
import datetime
from collections import deque
from bisect import bisect_left, bisect_right
import heapq



#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

def swap(a,b):
	tmp=a
	a=b
	b=tmp
	return a,b

H,W,K=input2()
c=[list(input()) for _ in range(H)]

ans=0

for row_line in product(range(2),repeat=H): #[行]0:そのまま，1:赤く塗る
	for col_line in product(range(2), repeat=W): #[列]0:そのまま，1:赤く塗る
		# 黒("#")の数え上げ
		cnt=0
		for row in range(H):
			for col in range(W):
				if c[row][col]=="#" and row_line[row]==0 and col_line[col]==0:
					cnt+=1

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

Submission status: Accepted

Solution code:
from itertools import product
h,w,k=map(int,input().split())
a=0
c=[[0 if l=='.' else 1 for l in input()] for _ in range(h)]
for i in product([0,1] , repeat=h):
  for j in product([0,1] , repeat=w):
    b=0
    for H,W in product(range(h),range(w)):
      b+=c[H][W]*i[H]*j[W]
    if b == k:
      a+=1
print(a)

Submission status: Accepted

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

for i in range(2 ** H - 1):
    for j in range(2 ** W - 1):
        sum = 0
        for ih in range(H):
            if 2 ** ih & i > 0:
                continue
            for iw in range(W):
                if 2 ** iw & j > 0:
                    continue
                if c[ih][iw] == '#':
                    sum += 1
        if sum == K:
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import copy
H,W,K=map(int,input().split())
L=[]
for i in range(H):
  L_=list(input())
  L.append(L_)

cnt=0
for i in  range(2**H):
  l=copy.deepcopy(L)
  
  for k in range(H):
    if (i>>k)&1:
      l[k]=['.']*W
    
  for j in range(2**W):
    ll=copy.deepcopy(l)
   
    for m in range(W):
      if (j>>m)&1:
        for n in range(H):
          if ll[n][m]=='#':
            ll[n][m]='.'
            
    counted=0
    for o in range(H):
      counted+=ll[o].count('#')
    #print(ll)
    if counted==K:
      cnt+=1    

print(cnt)

Submission status: Accepted

Solution code:
from itertools import product
h, w, k = map(int, input().split())
c = [[1 if j == '#' else 0 for j in input()] for i in range(h)]
print(sum(sum(c[i][j]*br[i]*bc[j] for i, j in product(range(h), range(w))) == k for br in product([0, 1], repeat=h) for bc in product([0, 1], repeat=w)))

Submission status: Accepted

Solution code:
from itertools import product
h, w, k = map(int, input().split())
c = [[1 if j == '#' else 0 for j in input()] for i in range(h)]
cnt = 0
for br in product([0, 1], repeat=h):
    for bc in product([0, 1], repeat=w):
        if sum(c[i][j]*br[i]*bc[j] for i, j in product(range(h), range(w))) == k:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
ls = [str(input()) for _ in range(h)]
a = [[] for _ in range(2**h)]
b = [[] for _ in range(2**w)]
for i in range(2**h):
    for j in range(h):
        if (i>>j)&1:
            a[i].append(j)
for s in range(2**w):
    for l in range(w):
        if (s>>l)&1:
            b[s].append(l)
p = 0
for e in range(2**h):
    for f in range(2**w):
        cnt = 0
        for g in range(len(ls)):
            if g not in a[e]:
                di = list(ls[g])
                for t in range(len(di)):
                    if t not in b[f]:
                        if di[t] == "#":
                            cnt += 1
        if cnt == k:
            p += 1
print(p)

Submission status: Accepted

Solution code:
H, W, K = [int(i) for i in input().split()]
a = [[] for i in range(H)]
for i in range(H):
    a[i] = list(input())
counter = 0
for i in range( 2 ** H):
    for p in range( 2 ** W):
        tmp = 0
        for j in range(H):
            for q in range(W):
                if ((i >> j) & 1):
                    if ((p >> q) & 1):
                        if a[j][q] == '#':
                            tmp += 1
        if tmp == K:
            counter += 1
print(counter)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0

for hi in range(2**h):
  for wi in range(2**w):
    c_cp = [[n for n in i] for i in c]
    
    for hj in range(h):
      if (hi & (1<<hj)) != 0:
        c_cp[hj] = ['R' for n in c_cp[hj]]
    
    for wj in range(w):
      if (wi & (1<<wj)) != 0:
        for hk in range(h):
          c_cp[hk][wj] = 'R'
    
    cnt = list(itertools.chain.from_iterable(c_cp)).count('#')
    
    if cnt == k:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy

H, W, K = map(int, input().split())
inputdata = [list(str(input())) for i in range(H)]
data = []
temp = []
give = 0

for x in inputdata:
  data.append(list(x))

for i in range(2 ** H):
  for j in range(2 ** W):
    ans = 0
    temp = copy.deepcopy(data)
    for m in range(H):
      for n in range(W):
        if ((int(bin(i)[2:]) >> m) & 1) or ((int(bin(j)[2:]) >> n) & 1):
          temp[m][n] = "@"
        if temp[m][n] == "#":
          ans += 1
    if ans == K:
      give += 1

print(give)

Submission status: Accepted

Solution code:
H, W, K = map(lambda x: int(x), input().split())
 
matrix = []
for i in range(H):
	row = input()
	dots = []
	for j in range(W):
		dots.append(row[j])
	matrix.append(dots)


ans = 0
for a in range(1<<H):
    for b in range(1<<W):
        cnt=0 
        for c in range(H):
            if a&(1<<c): 
                for d in range(W):
                 if b&(1<<d): 
                    cnt+=matrix[c][d]=='#'
        ans+=cnt==K
 
print(ans)

Submission status: Accepted

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

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

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

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


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    #n, k = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    #a = list(map(int, input().split()))
    #b = list(map(int, input().split()))
    h, w, k = map(int, input().split())
    a = []
    for __ in range(h):
        a += [[k for k in input()]]
    ans = 0
    for ch1 in range(2**h):
        for ch2 in range(2**w):
            rowchosen = binary(ch1, h)
            colchosen = binary(ch2, w)
            count = 0
            for i in range(h):
                for j in range(w):
                    if rowchosen[i] != '1' and colchosen[j] != '1' and a[i][j] == '#':
                        count += 1
            if count == k:ans+=1
    print(ans)

Submission status: Accepted

Solution code:
# 問題　解釈違い…最近多い…

import sys
h,w,k=map(int,input().split())
a=list(sys.stdin.read().split())
ans=0
for i in range(2**h-1):
    for j in range(2**w-1):
        cnt=0
        for y in range(h):
            if i>>(y)&1:
                continue
            for x in range(w):
                if j>>(x)&1:
                    continue
                if a[y][x]=="#":
                  cnt+=1
                
        if cnt==k:
            ans+=1
print(ans)

Submission status: Accepted

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

def main(H, W, Matrix, i, K):
    Blacl_Count = 0 
    Bin = format(i, '12b')
    for a, line in enumerate(Matrix):
        for b, raw in enumerate(line):
            if Bin[-(a+1)] == '1' or Bin[-(b+H+1)] == '1':
                continue
            elif raw == '#':
                Blacl_Count += 1
    if Blacl_Count == K:
        return 1
    else:
        return 0

for h in range(H):
    line = input()
    Matrix.append(line)

iteration = 2**(H+W)

for i in range(iteration):
    answer += main(H, W, Matrix,i, K)

print(answer)

Submission status: Accepted

Solution code:
from itertools import product

H,W,K=map(int,input().split())
masu=[input() for _ in range(H)]
ans=0
ROW=list(product([False,True],repeat=H))
COL=list(product([False,True],repeat=W))
for row in ROW:
  for col in COL:
    cnt=0
    for i in range(H):
      for j in range(W):
        if row[i]==False and col[j]==False and masu[i][j]=="#":
          cnt+=1
    if cnt==K:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools, copy
h,w,k = map(int, input().split())
c = []
for i in range(h):
    cc = list(input())
    c.append(cc)
li_h = range(h)
li_w = range(w)
count = 0
for n in range(0, len(li_h)+1):
    for conb_h in itertools.combinations(li_h, n):        
        for m in range(0, len(li_w)+1):
            for conb_w in itertools.combinations(li_w, m):
                ccc = copy.deepcopy(c)
                for i in list(conb_h):
                    for ii in range(w):
                        ccc[int(i)][ii] = '.'
                for j in list(conb_w):
                    for jj in range(h):
                        ccc[jj][int(j)] = '.'
                _count = 0
                for item in ccc:
                    _count += item.count('#')
                if _count == k:
                    count += 1
print(count)

Submission status: Accepted

Solution code:
import sys

h,w,k=map(int,next(sys.stdin).split())
a=list(sys.stdin)

ans=0
for y in range(1<<h):
    for x in range(1<<w):
        ct=0
        for i in range(h):
            if y&(1<<i): continue
            for j in range(w):
                if x&(1<<j): continue
                ct+=a[i][j]=='#'
        ans+=ct==k

print(ans)

Submission status: Accepted

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

    c = [list(input()) for _ in range(H)]
    ans = 0

    for i in range(2**H):

        for j in range(2**W):

            now = 0
            for x in range(H):
                for y in range(W):

                    if 2**x & i > 0 and 2**y & j > 0:
                        if c[x][y] == "#":
                            now += 1

            if now == K:
                ans += 1

    print(ans)


resolve()

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
c = [list(input()) for i in range(h)]
ans = 0
for i in range(2**h):
    h_list = [False] * h
    for j in range(h):
        if (i >> j) & 1:
            h_list[h - 1 - j] = True
    
    for l in range(2**w):
        w_list = [False] * w
        for m in range(w):
            if (l >> m) & 1:
                w_list[w - 1 - m] = True

        cnt = 0
        for a in range(h):
            for b in range(w):
                if c[a][b] == '#' and not h_list[a] and not w_list[b]:
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

h, w, k = map(int, input().split())
C = []
for _ in range(h): C.append(input())
from itertools import *
ans = 0
for bit in range(1<<(h+w)):
    c = 0
    for i, j in product(range(w, h+w), range(w)):
        if bit>>i & 1 and bit>>j & 1: c += C[i-w][j] == '#'
    if c == k: ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def f(c, h_patterns, w_patterns, black_count):
    used = [[False for _ in range(len(w_patterns))]
            for _ in range(len(h_patterns))]

    for index, h_pattern in enumerate(h_patterns):
        if h_pattern != 1:
            continue

        for w_dash in range(len(w_patterns)):
            if not used[index][w_dash] and c[index][w_dash] == '#':
                used[index][w_dash] = True
                black_count -= 1

    for index, w_pattern in enumerate(w_patterns):
        if w_pattern != 1:
            continue

        for h_dash in range(len(h_patterns)):
            if not used[h_dash][index] and c[h_dash][index] == '#':
                used[h_dash][index] = True
                black_count -= 1

    return black_count


def main():
    from itertools import product

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

    for hi in range(h):
        for wi in range(w):
            if c[hi][wi] == '#':
                black_count += 1

    for h_patterns in product([1, 0], repeat=h):
        for w_patterns in product([1, 0], repeat=w):
            fi = f(c, h_patterns, w_patterns, black_count)

            if fi == k:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    for ib in range(1<<h):
        for jb in range(1<<w):
            ct = 0
            for i in range(h):
                for j in range(w):
                    if (ib>>i)&1 and (jb>>j)&1 and G[i][j]=="#":
                        ct+=1
            
            if ct == k:
                ans+=1
    
    print(ans)
main2()

Submission status: Accepted

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

ans = 0
for i in range(1 << h):
    for j in range(1 << w):
        cnt = 0
        for k in range(h):
            for l in range(w):
                if i >> k & 1:
                    continue
                if j >> l & 1:
                    continue
                if lc[k][l] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

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

matrix = []
for i in range(H):
	row = input()
	dots = []
	for j in range(W):
		dots.append(row[j])
	matrix.append(dots)

ans = 0
for bitR in range(1 << H):
	for bitC in range(1 << W):
		black = 0
		for i in range(H):
			for j in range(W):
				if ((bitR >> i) & 1) == 0 and ((bitC >> j) & 1) == 0 and matrix[i][j] == '#':
					black += 1
		if black == K:
			ans += 1

print(ans)

Submission status: Accepted

Solution code:

h,w,k=map(int,input().split())
c=[[0]*w for i in range(h)]
d=[[0]*w for i in range(h)]
ans=0
for i in range(h):
    a=input()
    for j in range(w):
        c[i][j]=a[j]
for i in range(2**(h+w)):
    for m in range(h):
        for n in range(w):
            d[m][n]=c[m][n]
    for j in range(h):
        if (i >> j)&1:
            for x in range(w):
                d[j][x]="r"
    for j in range(h,w+h):
        if (i >> j)&1:
            for x in range(h):
                d[x][j-h]="r"
    f=0
    for q in range(h):
        for s in range(w):
            if d[q][s]=="#":
                f+=1
            
        
    if f==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())
matrix = []
for i in range(H):
    matrix.append(input())

matrix_int = np.ones((H, W), dtype=np.uint8)
# 1 == 黒、 0 == 白
for row in range(H):
    for column in range(W):
        if matrix[row][column] == ".":
            matrix_int[row, column] = 0

count = 0
for row_options in range(2**H):
    for col_options in range(2**W):
        tmp_matrix_int = deepcopy(matrix_int)
        tmp_row_options = row_options
        tmp_col_options = col_options

        for row in range(H):
            mod = tmp_row_options % 2
            if mod == 0:
                tmp_matrix_int[row,:] = 0
            tmp_row_options = tmp_row_options // 2
        
        for col in range(W):
            mod = tmp_col_options % 2
            if mod == 0:
                tmp_matrix_int[:,col] = 0
            tmp_col_options = tmp_col_options // 2
        # print(tmp_matrix_int.sum())
        if tmp_matrix_int.sum() == K:
            count += 1
print(count)

Submission status: Accepted

Solution code:
import copy

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

for i in range(1 << (h + w)):
    l = copy.deepcopy(c)
    for p in range(h):
        if i >> p & 1:
            l[p] = ['r'] * w
    for m in range(w):
        if i >> (m + h) & 1:
            for o in range(h):
                l[o][m] = 'r'
    s = ''
    for i in range(h):
        s += ''.join(l[i])
    if s.count('#') == k:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
M = [[1 if c == "#" else 0 for c in 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):
            if hselection & (1 << h):
                continue
            for w in range(W):
                if wselection & (1 << w):
                    continue
                count += M[h][w]
        if count == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

def countKuro( t,p1,p2 ):
    count=0
    for i in range(h):
      if p1 & (1<<i) :
        for j in range(w):
            if p2 & (1<<j) :
                if t[i][j]=="#":
                    count+=1
    return count


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

t=copy.copy(s)
ans=0
for i in range(1<<h):
    for j in range(1<<w):
        # print(i,j, countKuro(s,i,j))
        if k==countKuro(s, i,j):
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy

H, W, K = list(map(int, input().split()))
c = [0]*H
for i in range(H):
    char = input()
    c[i] = []
    for j in range(W):
        if char[j] == "#":
            c[i].append(1)
        else:
            c[i].append(0)

count = 0

for i in range(2**H):
    for j in range(2**W):
        d = copy.deepcopy(c)
        i2 = i
        j2 = j
        for k in range(H):
            if i2 & 1:
                d[k] = [0]*W
            i2 >>= 1
        for l in range(W):
            if j2 & 1:
                for m in range(H):
                    d[m][l] = 0
            j2 >>= 1
        s = sum(map(sum, d))
        if s == K:
            count += 1

print(count)

Submission status: Accepted

Solution code:
import itertools

h,w,k=map(int,input().split())
c=[list(input()) for i in range(h)]
ans=0
for filter_row in range(2**h):
  for filter_col in range(2**w):
    cnt=0
    for i in range(h):
      for j in range(w):
        if (filter_row>>i&1)!=0 and (filter_col>>j&1)!=0 and c[i][j]=='#':
          cnt+=1
    if cnt==k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy

def solve(h,w,k,stage,nh,nw):
    if nh == h and nw == w:
        res = 0
        for row in stage:
            res += row.count('#')
        if res == k:
            return 1
        else:
            return 0
    
    elif nh == h:
        nwn = nw + 1
        stagen = copy.deepcopy(stage)
        for i in range(h):
            stagen[i][nw] = '.'

        return solve(h,w,k,stage,nh,nwn) + solve(h,w,k,stagen,nh,nwn)
    
    else:
        nhn = nh + 1
        stagen = copy.deepcopy(stage)
        stagen[nh] = list('.'*w)
        return solve(h,w,k,stage,nhn,nw) + solve(h,w,k,stagen,nhn,nw)




if __name__ == '__main__':
    h,w,k = map(int,input().split())
    stage = []
    for i in range(h):
        row = list(input())
        stage.append(row)
    
    print(solve(h,w,k,stage,0,0))

Submission status: Accepted

Solution code:
import sys, math, operator, itertools, collections, heapq, bisect
# sys.setrecursionlimit(10**4)


class Solution:
    def __init__(self):
        pass

    def solve(self, *Input):
        ans = 0
        h,w,k,matrix = Input
        # print(matrix)
        for r in range(h):
            rows = list(itertools.combinations(range(h),r))
            for c in range(w):
                # print(r,c)
                cols = list(itertools.combinations(range(w), c))
                # print(list(rows), list(cols))
                for row in rows:
                    for col in cols:
                        # print(row,col)
                        new_matrix = [[x for x in ROW] for ROW in matrix]
                        ans += self.create(h,w,k,new_matrix,row,col)
                        # print(ans)

        return ans

    def create(self, *Input):
        h,w,k,matrix,rows,cols = Input
        for i in range(h):
            for j in cols:
                matrix[i][j] = '.'
        for r in rows:
            matrix[r] = ['.'] * w
        # print(matrix)
        return self.check(k,matrix)

    def check(self, *Input):
        k,matrix = Input
        cnt = 0
        for row in matrix:
            cnt += row.count('#')
        return cnt == k

    def sieve_classic(self,a,b):
        self.primes = [True] * (b+1)
        self.primes[0] = self.primes[1] = False
        for i in range(2,b+1):
            if self.primes[i] and i*i <= b:
                for j in range(i*i,b+1,i):
                    self.primes[j] = False
        self.primes = [x for x,y in enumerate(self.primes) if y]
        ind = bisect.bisect_left(self.primes,a)
        self.primes[:ind] = []
        return None


if __name__=='__main__':
    solution = Solution()

    inputs = iter(sys.stdin.readlines())
    h,w,k = map(int, next(inputs).split())
    matrix = [list(next(inputs).rstrip()) for _ in range(h)]
    ans = solution.solve(h,w,k,matrix)
    print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=list(list(input()) for _ in range(h))
ans=0
for n in range(2**(h+w)):
    l={}
    o={}
    x=0
    for m in range(h+w):
        if (n>>m)&1:
            if m>=h:
                o[m-h]=1
            else:
                l[m]=1
    for i in range(h):
        if not i in l:
            for j in range(w):
                if not j in o:
                    if c[i][j]=="#":
                        x+=1
    if x==k:
        ans+=1
print(ans)

Submission status: Accepted

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

ans = 0
for tate in range(2 ** H):
    for yoko in range(2 ** W):
        tate_ = tate
        T = []
        for _ in range(H):
            T.append(tate_ % 2 == 0)
            tate_ //= 2
        Y = []
        yoko_ = yoko
        for _ in range(W):
            Y.append(yoko_ % 2 == 0)
            yoko_ //= 2
#         print(tate, T, yoko, Y)
        count = 0
        for h in range(H):
            if T[h]: continue
            for w in range(W):
                if Y[w]: continue
                if C[h][w] == '#':
                    count += 1
        if count == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
hwk = input().split()
h, w, k = int(hwk[0]), int(hwk[1]), int(hwk[2])
field = []
for i in range(h):
    row = input()
    field.append([1 if c == '#' else 0 for c in row])
    # field.append(row)
count = 0


def test(i, j):
    _sum = 0
    for r in range(h):
        if r in i: continue
        for c in range(w):
            if c in j: continue
            _sum += field[r][c]
            if _sum > k: return False
    return _sum == k


def subset(n):
    res = []
    i = 0
    while True:
        num_s = bin(i)[2:].zfill(n)
        tmp = []
        flag = True
        for idx in range(n):
            if num_s[idx] == '1':
                tmp.append(idx)
            else:
                flag = False
        res.append(tmp)
        i += 1
        if flag:
            break
    return res


row_idxs = subset(h)
col_idxs = subset(w)

for r_i in row_idxs:
    for c_j in col_idxs:
        if test(r_i, c_j):
            count += 1

print(count)

Submission status: Accepted

Solution code:
from itertools import product


def solve(string):
    h, w, k, *c = string.split()
    h, w, k = map(int, [h, w, k])
    ans = 0
    for f in product([True, False], repeat=h + w):
        count = 0
        for _f, _c in zip(f, c):
            if _f:
                continue
            count += sum(1 if __f and v == "#" else 0 for __f, v in zip(f[h:], _c))
        ans += 1 if count == k else 0
    return str(ans)

    pass


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from itertools import product


def solve(string):
    h, w, k, *c = string.split()
    h, w, k = map(int, [h, w, k])
    ans = 0
    for f in product([True, False], repeat=h + w):
        count = 0
        for _f, _c in zip(f, c):
            if _f:
                continue
            count += sum(1 if not __f and v == "#" else 0 for __f, v in zip(f[h:], _c))
        ans += 1 if count == k else 0
    return str(ans)

    pass


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))