Problem:


Score : 300 points

Problem Statement

We have a grid of H rows and W columns of squares. The color of the square at the i-th row from the top and the j-th column from the left (1 \leq i \leq H, 1 \leq j \leq W) is given to you as a character c_{i,j}: the square is white if c_{i,j} is ., and black if c_{i,j} is #.

Consider doing the following operation:

Choose some number of rows (possibly zero), and some number of columns (possibly zero). Then, paint red all squares in the chosen rows and all squares in the chosen columns.

You are given a positive integer K. How many choices of rows and columns result in exactly K black squares remaining after the operation? Here, we consider two choices different when there is a row or column chosen in only one of those choices.

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

H W K
c_{1,1}c_{1,2}...c_{1,W}
c_{2,1}c_{2,2}...c_{2,W}
:
c_{H,1}c_{H,2}...c_{H,W}

Output

Print an integer representing the number of choices of rows and columns satisfying the condition.

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

One choice, which is choosing nothing, satisfies the condition.

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

6 6 8
..##..
.#..#.
#....#
######
#....#
#....#

Sample Output 4

208



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


Sample output:
5

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product
import numpy as np
from copy import copy
H, W, K, *data = map(str, open(0).read().split())

H = int(H)
W = int (W)
K = int(K)

# Set . to 0, set # to + 1, let red be 0

encoder = dict()
encoder["."] = 0
encoder["#"] = +1

mat = np.zeros([H,W], dtype=int)
for i, row_raw in enumerate(data):
    row = [encoder[char] for char in row_raw]
    mat[i,:] = row

counter = 0
for H_red in product([True, False], repeat=H):
    for W_red in product([True, False], repeat=W):
        mat_c = copy(mat)
        mat_c[H_red, :] = 0
        mat_c[:, W_red] = 0
        black_count = np.sum(mat_c)
        if black_count == K:
            counter += 1

print(counter)

Submission status: Accepted

Solution code:
import itertools as itr

def get_val(c, x_list, y_list):
    cnt = 0
    for y in range(len(c)):
        if y_list[y] == 0: # その行が塗りつぶされていなければ入る
            for x in range(len(c[y])):
                if (x_list[x] == 0) and (c[y][x] == '#'):
                    cnt += 1
    return (cnt)

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

c_tmp = []
for i in range(h):
    c_tmp.append(input())

ans = 0
for y in list(itr.product([0,1], repeat=h)):
    for x in list(itr.product([0,1], repeat=w)):
        if get_val(c_tmp, x, y) == k:
            ans += 1
print(ans)

Submission status: Accepted

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

for i in range(h):
  c_now = input()
  c[i] = [0 if cc=="." else 1 for cc in c_now]
  
  

for i in range(2**h):
  ii = bin(i)[2:].zfill(h)
  for j in range(2**w):
    jj = bin(j)[2:].zfill(w)
    
    count_now = 0
    for hh in range(h):
      if(ii[hh] == '1'):
        continue
      
      for ww in range(w):
        if(jj[ww] == '1'):
          continue
        if(c[hh][ww] == 1):
          count_now += 1
    if(count_now == k):
      count += 1
        
print(count)

Submission status: Accepted

Solution code:
import copy
h,w,k = list(map(int,input().split()))
hw_origin = [[0]*w for i in range(h)]
for i in range(h) :
    c = input()
    for j in range(w) :
        hw_origin[i][j] = c[j]

ans = 0
for i in range(2**h) :
    for j in range(2**w) :
        hw = copy.deepcopy(hw_origin)
        for l in range(h) :
            if (i>>l)&1 :
                for m in range(w) :
                    hw[l][m] = 1
        for m in range(w) :
            if (j>>m)&1 :
                for l in range(h) :
                    hw[l][m] = 1
        countb = 0
        for l in range(h) :
            for m in range(w) :
                if hw[l][m] == '#' :
                    countb += 1
        if countb == k :
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

h, w, k = map(int, input().split())
l = []
ans = 0

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


for i in itertools.product("01", repeat = h + w):
    m = copy.deepcopy(l)
    cnt = 0
    for j in range(h + w):
        if j <= h - 1:
            if i[j] == "1":
                for p in range(w):
                    m[j][p] = "."
        else:
            if i[j] == "1":
                for o in range(h):
                    m[o][j - h] = "."
    for j in range(h):
        cnt += m[j].count("#")
    if cnt == k:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import *

h,w,k = map(int,input().split())
maps = [list(input()) for _ in range(h)]
seqw = [ i for i in range(w)]
seqh = [ i for i in range(h)]
ind = []
cnt = 0
for y in range(h):
    for x in range(w):
        if maps[y][x] == "#":
            ind.append((x,y)) 

from itertools import *

chosew = []
for i in range(2 ** w):
    bit_set = []
    for j in range(w):
        if ((i >> j) & 1):
            bit_set.append(seqw[j])
    chosew.append(bit_set)
#print(chosew)

choseh = []
for i in range(2 ** h):
    bit_set = []
    for j in range(h):
        if ((i >> j) & 1):
            bit_set.append(seqh[j])
    choseh.append(bit_set)
#print(choseh)

p = list(product(chosew, choseh))

ans = 0
for cw,ch in p:
    tmp = []
    for x,y in ind:
        if x not in cw and y not in ch:
            tmp.append((x,y))
    if len(tmp) == k:
        ans += 1
print(ans)

Submission status: Accepted

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

from itertools import product
a = list(product([0,1],repeat=h))
b = list(product([0,1],repeat=w))

co2=0
for p in a:
    for q in b:
        co1=0
        for i in range(h):
            for j in range(w):
                if p[i]==0 and q[j]==0:
                    if u[i][j]=='#':
                        co1+=1
        if co1==k:
            co2+=1
print(co2)

Submission status: Accepted

Solution code:
import copy
H, W, K = map(int, input().split())
A = [list(input()) for i in range(H)]
ans = 0
for i in range(2**H):
    for j in range(2**W):
        B = copy.deepcopy(A)
        for a in range(H):
            if i>>a & 1:
                B[a] = ["."]*W
        for a in range(W):
            if j>>a & 1:
                for m in range(H):
                    B[m][a] = "."
        s = 0
        for m in range(H):
           for n in range(W):
                if B[m][n] == "#":
                    s += 1
        if s == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
mp = []
total = 0
for i in range(h):
    mp.append(list(input()))
    total += mp[-1].count("#")
# print(total)
# for i in mp:
#     print(*i)
ans = 0
for row_mask in range(2**h):
    for col_mask in range(2**w):
        vis_arr = [[False for i in range(w)] for j in range(h)]
        rm = bin(row_mask)[2:]
        rm = "0" * (h - len(rm)) + rm
        cm = bin(col_mask)[2:]
        cm = "0" * (w - len(cm)) + cm
        cnt = 0
        for rowp in range(h):
            for colp in range(w):
                if (cm[colp] == "1" or rm[rowp] == "1") and (vis_arr[rowp][colp] == False and mp[rowp][colp] == "#"):
                    cnt += 1
                    vis_arr[rowp][colp] = False
        # print(rm, cm, cnt)
        if total-cnt == k:
            ans += 1
            # print(rm, cm, cnt)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
h, w, k = map(int, input().split())
m = []
br = []
bc = []
for i in range(h):
    i = input()
    m.append(list(i))
    br.append(i.count('#'))
mm = list(zip(*m))
for c in mm:
    bc.append(c.count('#'))
b = sum(br)
p = 0
for r in product([0, 1], repeat=h):
    for c in product([0, 1], repeat=w):
        ris = [i for i, x in enumerate(r) if x == 1]
        cis = [i for i, x in enumerate(c) if x == 1]
        c = 0
        for ri in ris:
            c += br[ri]
            for ci in cis:
                c -= 1 if m[ri][ci] == '#' else 0
        for ci in cis:
            c += bc[ci]
        if c == b - k:
            p += 1
print(p)

Submission status: Accepted

Solution code:
from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    h,w,K=map(int,input().split())
    g=[[_ for _ in input()] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if g[i][j]=='.':
                g[i][j]=0
            else:
                g[i][j]=1
    n=h+w
    cnt=0
    for i in range(2 ** n):
        gg=deepcopy(g)
        for j in range(n):
            if ((i >> j) & 1):
                if j-h<0:
                    for k in range(w):
                        gg[j][k]=2
                else:
                    for l in range(h):
                        gg[l][j-h]=2
        
        ans=0
        for i in range(h):
            for j in range(w):
                if gg[i][j]==1:
                    ans+=1

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


    
resolve()

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect
INF = 10**18
def judge(li_tate,li_yoko,li2):
    for i in range(len(li_tate)):
        if li_tate[i]:
            for j in range(len(li2[i])):
                li2[i][j] = "red"
    for i in range(len(li_yoko)):
        if li_yoko[i]:
            for j in range(h):
                li2[j][i] = "red"
    cnt = 0
    for i in range(len(li_tate)):
        for j in range(len(li_yoko)):
            if li2[i][j] == "#":
                cnt+=1
    return cnt


if __name__ == "__main__":
    h,w,k = map(int,input().split())
    li = []
    for i in range(h):
        s = list(input())
        li.append(s)
    
    ans = 0
    for i in range(2**h):
        li_tate = [False]*(h)
        for j in range(h):
            if (i>>j)&1:
                li_tate[h-j-1] = True
        for j in range(2**w):
            li_yoko = [False]*(w)
            for l in range(w):
                if (j>>l)&1:
                    li_yoko[w-l-1] = True
            li2 = copy.deepcopy(li)
            a = judge(li_tate,li_yoko,li2)
            if a == k:
                ans += 1
    print(ans)

Submission status: Accepted

Solution code:
H,W,K = list(map(int, input().split()))
c,h,w = [],[],[]
for i in range(H):
  oneline = input()
  c.append(oneline)
for i in range(H):
  temp = 0
  for j in range(W):
    if(c[i][j]=="#"):
      temp += 1
  h.append(temp)
for j in range(W):
  temp = 0
  for i in range(H):
    if(c[i][j]=="#"):
      temp += 1
  w.append(temp)
num = H+W
ans = 0
totalblack = sum(h)
for k in range(2**(H+W)):
  b = format(k, '0%db'%num)
  hb = b[:H]
  wb = b[-W:]
  #print(b, hb, wb, h, w, end=" ")
  delsum, cov = 0 ,0
  for i in range(H):
    if(hb[i]=="1"):
      delsum += h[i]
  for j in range(W):
    if(wb[j]=="1"):
      delsum += w[j]
  for i in range(H):
    for j in range(W):
      if(hb[i]=="1" and wb[j]=="1" and c[i][j]=="#"):
        cov += 1
  remainblack = totalblack - delsum + cov
  #print(remainblack, delsum, cov, end=" ")
  if(remainblack == K):
    ans += 1
print(ans)

Submission status: Accepted

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

lish = [-1]
lisw = [-1]
num = [i for i in range(1,h+1)]
numw = [i for i in range(1,w+1)]
numm = [[i] for i in range(1,h+1)]
numww = [[i] for i in range(1,w+1)]
lish.extend(numm)
lisw.extend(numww)
for i in range(2,h+1):
    lish.extend(list(itertools.combinations(num,i)))
for i in range(2,w+1):
    lisw.extend(list(itertools.combinations(numw,i)))

ans = 0
for i in lish:
    for j in lisw:
        tmp = copy.deepcopy(c)
        tmpan = 0
        if i!=-1:
            for ii in i:
                for jj in range(w):
                    tmp[ii-1][jj] = -1
        if j!=-1:
            for jj in j:
                for ii in range(h):
                    tmp[ii][jj-1] = -1
        for ii in range(h):
            for jj in range(w):
                if tmp[ii][jj] == "#":
                    tmpan +=1
        if tmpan ==k:
            ans+=1

print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

def to_list(v):
    b = bin(v)
    l = []
    for i, flg in enumerate(reversed(b[2:])):
        if flg == '1':
            l.append(i)
    return l

def check(field, hl, wl):
    count_black = 0
    #print('hl', 'wl', hl, wl) # debug
    for h in hl:
        for w in wl:
            if field[h][w] == '#':
                count_black += 1
    #print('count_black', count_black) # debug
    return count_black


def solve(field, h, w, k):
    mh = 2 ** h
    mw = 2 ** w
    whole = check(field, to_list(mh - 1), to_list(mw - 1))
    #print('whole') # debug
    #print(whole) # debug
    #
    count = 0
    for hh in range(mh):
        hl = to_list(hh)
        if len(hl) == 0:
            continue
        for ww in range(mw):
            wl = to_list(ww)
            if len(wl) == 0:
                continue
            kk = check(field, hl, wl)
            if k == kk:
                count += 1
    return count



if __name__ == '__main__':
    h, w, k = list(map(int, input().split()))
    field = []
    for _ in range(h):
        l = input()
        field.append(l)
    ans = solve(field, h, w, k)
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

Solution code:
def main():
    import sys
    import copy
    input = sys.stdin.readline
    H, W, K = [int(x) for x in input().strip().split()]
    C = [[0] * W for h in range(H)]
    sum_ = 0
    for h in range(H):
        C[h] = list(input().strip())
        sum_ += sum([1 if s == '#' else 0 for s in C[h]])

    ans = 0
    for i in range(2**H):
        sum_t = sum_
        D = copy.deepcopy(C)
        for ii in range(H):
            if (i >> ii) % 2:
                for c in range(W):
                    if D[ii][c] == '#':
                        sum_t -= 1
                        D[ii][c] = '.'
        if sum_t < K:
            continue
        # print(D)
        for j in range(2**W):
            E = copy.deepcopy(D)
            sum_t2 = sum_t
            for jj in range(W):
                if (j >> jj) % 2:
                    for c in range(H):
                        if E[c][jj] == '#':
                            sum_t2 -= 1
                            E[c][jj] = '.'
            # print('i={}, j={}, sum_t={}, sum_t2={}'.format(i, j, sum_t, sum_t2))
            # for t in range(H):
            #     print(E[t])
            if sum_t2 == K:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    import itertools
    import numpy as np
    H,W,K=list(map(int,sys.stdin.readline().split()))
    C=np.zeros((H,W))
    for i in range(H):
        C[i]=[1 if x=='#' else 0 for x in sys.stdin.readline().strip()]

    nums = [0,1]
    count=0
    for pat in itertools.product(nums, repeat=H+W):
        patH=list(i for i,x in enumerate(pat[:H]) if x==1)
        patW=list(i for i,x in enumerate(pat[H:]) if x==1)
        CH=C[patH]
        if CH.shape[0]:
            CHW=CH[:,patW]
            p=np.count_nonzero(CHW)
            if p==K:
                count+=1


    print(count)

    


main()

Submission status: Accepted

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

ans = 0
for i in range(2**h):
    red1 = []
    for k in range(h):
        if ((i>>k)&1):
            red1.append(k)

    for j in range(2**w):
        red2 = []
        for l in range(w):
            if ((j>>l)&1):
                red2.append(l)
        
        cnt = 0
        for a in range(h):
            for b in range(w):
                if (c[a][b]=='#')and(a in red1)and(b in red2):
                    cnt +=1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right
from copy import deepcopy

def solve():
    H, W, K = MI()
    C = np.array(LLS(H))
    D = np.zeros_like(C, np.int)

    for i, c in enumerate(C):
        for j, cc in enumerate(c):
            if cc == '#':
                D[i, j] = 1
            else:
                D[i, j] = 0
    # print(D, D.dtype)

    h_zero = np.zeros(H)
    w_zero = np.zeros(W)

    ans = 0
    for i in range(1 << H):
        tmp1 = []
        for j in range(H):
            if (i >> j) & 1:
                tmp1.append(j)

        G = D.copy()
        for b1 in tmp1:
            G[b1, :] = w_zero.copy()

        for k in range(1 << W):
            tmp2 = []
            G2 = G.copy()
            for l in range(W):
                if (k >> l) & 1:
                    tmp2.append(l)

            for b2 in tmp2:
                G2[:, b2] = h_zero.copy()
            
            if np.sum(G2) == K:
                ans += 1

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

ans = 0
for i in range(2**H):
  for j in range(2**W):
    a = bin(i)[2:].zfill(H)
    b = bin(j)[2:].zfill(W)
    cnt = sum([
      (x + y == '00') and (c[k][l] == '#')
      for k, x in enumerate(a) for l, y in enumerate(b)
    ])
    if cnt == K:
      ans += 1 
print(ans)

Submission status: Accepted

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

count_match = 0
H_skip = []
for x in range(0, H + 1, 1):
    tmp = list(itertools.combinations(range(H), x))
    for y in tmp:
        H_skip.append(y)

W_skip = []
for v in range(0, W + 1, 1):
    tmp = list(itertools.combinations(range(W), v))
    for w in tmp:
        W_skip.append(w)

for h_skip in H_skip:
    for w_skip in W_skip:
        count = 0
        for q in range(H):
            for r in range(W):
                if maps[q][r] == "#" and q not in h_skip and r not in w_skip:
                    count += 1

        if count == K:
            count_match += 1

print(count_match)

Submission status: Accepted

Solution code:
import copy
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    h,w,k=INTM()
    c=[]
    ct=0
    for i in range(h):
        c.append(list(input()))
    for i in range(2**h):
        h2=str(format(i, 'b').zfill(h))
        for j in range(2**w):
            w2=str(format(j, 'b').zfill(w))
            #print(h2,w2)
            c_t=copy.deepcopy(c)
            
            for i2 in range(h):
                if h2[i2]=='1':
                    c_t[i2]=['.']*w
                    
            #print(c_t)
            for j2 in range(w):
                #print(j2)
                if w2[j2]=='1':
                    for i3 in range(h):
                        c_t[i3][j2]='.'
            
            temp=0
            for i2 in range(h):
                temp+=c_t[i2].count('#')
            
            if temp==k:
                ct+=1
                
    
    print(ct)
            
    
    
        
if __name__ == '__main__':
    do()

Submission status: Accepted

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

from itertools import product

Raw=list(product([0,1],repeat=h))
Column=list(product([0,1],repeat=w))

ans=0
for r in Raw:

    tmp=[]
    for i in range(len(r)):
        if r[i]==1:
            tmp.append(grid[i])
        
    if len(tmp)==0:
        continue

    for c in Column:
        cnt=0

        n=len(tmp)
        for l in range(n):
            for j in range(len(c)):
                if c[j]==1 and tmp[l][j]=='#':
                    cnt+=1
        if cnt==k:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip() # input string
ni = lambda: int(readline().rstrip()) # input int
nm = lambda: map(int, readline().split()) # input multiple int 
nl = lambda: list(map(int, readline().split())) # input multiple int to list

h, w, k = nm()
c = [[c for c in input()] for _ in range(h)]
ans = 0

for i in range(1 << h):
    for j in range(1 << w):
        black = 0
        check_h = []
        check_w = []
        now_i = i
        now_j = j
        for row in range(h):
            is_delete_i = now_i % 2
            check_h.append(is_delete_i)
            now_i = now_i >> 1
        for col in range(w):
            is_delete_j = now_j % 2
            check_w.append(is_delete_j)
            now_j = now_j >> 1
        for row in range(h):
            for col in range(w):
                if not(check_h[row] == 1 or check_w[col] == 1) and c[row][col] == "#":
                    black += 1
        if black == k:
            ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(0, pow(2,H)):
    for j in range(0, pow(2,W)):
        cnt = 0
        x = format(i, '06b')
        x = x[::-1]
        x = x[:H]
        y = format(j, '06b')
        y = y[::-1]
        y = y[:W]
        for h in range(H):
            for w in range(W):
                if x[h] == '0' and y[w] == '0':
                    if C[h][w]== '#':
                        cnt += 1
        if cnt == K:
            ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
h,w,k=list(map(int,input().split()))
c=[]
for i in range(h):
  c.append(list(input()))
  
bit_gyou=[]
for i in range(2**h):
    b_gyou=[]
    for j in range(h):
        if (i>>j & 1):
            b_gyou.append(1)
        else:
            b_gyou.append(0)
    bit_gyou.append(b_gyou)

    
bit_retu=[]
for i in range(2**w):
    b_retu=[]
    for j in range(w):
        if (i>>j & 1):
            b_retu.append(1)
        else:
            b_retu.append(0)
    bit_retu.append(b_retu)
ans=0
for i in bit_gyou:
  for j in bit_retu:
    cnt=0
    for gyou in range(len(i)):
      for retu in range(len(j)):
        if i[gyou]==1 and j[retu]==1 and c[gyou][retu]=="#":
          cnt=cnt+1
    if cnt==k:
      ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
import itertools
from copy import deepcopy
import itertools

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

ite = list(itertools.product([0, 1], repeat=h+w))

ans = 0

for d in ite:
    c2 = deepcopy(c)
    for i in range(h):
        if d[i] == 1:
            for j in range(w):
                c2[i][j] = 'R'
    for k in range(h,h+w):
        if d[k] == 1:
            for l in range(h):
                c2[l][k-h] = 'R'
    c3 = list(itertools.chain.from_iterable(c2))
    if c3.count('#') == kk:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
#import functools
#import operator
from itertools import combinations as comb
#from itertools import combinations_with_replacement as comb_with
#from itertools import permutations as perm
#import collections as C #most_common
#import math
#import sympy

#N = int(input())
H,W,K= map(int,input().split())
h=[x for x in range(H)]
w=[x for x in range(W)]
ans=0
#P = list(map(int,input().split()))
#S = str(input())
#T = str(input())
l=[]
for i in range(H):
    S = str(input())
    S=list(S)
    for i in S:
        l.append(i)
l=np.array(l)
l=l.reshape((H,W))
for i in range(H):
    for v in comb(h,i):
        for j in range(W):
            for b in comb(w, j):
                o=0
                #print(v,b)
                L=l.copy()
                for n in v:
                    L[n]=0
                for m in b:
                    L[:,m]=0
                #print(L)
                o=np.count_nonzero(L=='#')
                if o==K:
                    ans+=1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int,input().split())
C = []
for _ in range(H):
    C.append(input())
ans = 0
for h in range(2**H):
    temp = C.copy()
    hi = format(int(h), "b").zfill(H)
    for i in range(H):
        if hi[i] == '1':
            temp[i] = 'r'*W
    for w in range(2**W):
        tempw = temp.copy()
        wi = format(int(w), "b").zfill(W)
        for j in range(W):
            if wi[j] == '1':
                for i in range(H):
                    tempw[i] = tempw[i][:j] + 'r' + tempw[i][j+1:]
        num = 0
        for i in range(H):
            for j in range(W):
                if tempw[i][j] == '#':
                    num += 1
        if num == K:
            ans += 1
print(ans)

Submission status: Accepted

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

# Bit全探索
ans = 0
for hbits in range(1<<H):
    hignore = [False for __ in range(H)]
    for hi in range(H):
        if hbits & (1<<hi):
            hignore[hi] = True

    for wbits in range(1<<W):
        wignore = [False for __ in range(W)]
        for wi in range(W):
            if wbits & (1<<wi):
                wignore[wi] = True
    
        # count
        cnt = 0
        for ix in range(H):
            if hignore[ix]:
                continue
            for jx in range(W):
                if wignore[jx]:
                    continue
                if C[ix][jx] == '#':
                    cnt += 1
        
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

def delete_g(board, gyou, retu, w):
  for i in gyou:
    board[i] = [0] * w
  for i in retu:
    for j in range(len(board)):
      board[j][i] = 0
  k = 0
  for b in board:
    k += b.count("#")
  return k
      


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

gyou = [i for i in range(H)]
retu = [i for i in range(W)]

g = []
r = []
for i in range(H+1):
  for subset in itertools.combinations(gyou, i):
    g.append(list(subset))
    
for i in range(W+1):
  for subset in itertools.combinations(retu, i):
    r.append(list(subset))
    
for i in g:
  for j in r:
    board_cp = copy.deepcopy(board)
    k = delete_g(board_cp, i, j,W)
    if k == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[]
for i in range(h):
  ct=str(input())
  ct=list(ct)
  c.append(ct)
ans=0
for i in range(2 ** h):
  tempc=[]
  for j in range(h):
    if (i >> j)%2==1:
      tempc.append(c[j])
  if len(tempc)>0:
    for f in range(2 ** w):
      tempc2=[]
      for l in range(w):
        if (f >> l)%2==1:
          for m in range(len(tempc)):
            tempc2.append(tempc[m][l])
      if tempc2.count("#")==k:
        ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
h, w, K = map(int, input().split())
c = [input() for _ in range(h)]
hpr = list(product([0, 1], repeat=h))
wpr = list(product([0, 1], repeat=w))
ans = 0
for hp in hpr:
    for wp in wpr:
        tf = [[False]*w for _ in range(h)]
        for i in range(h):
            for j in range(w):
                if hp[i]:
                    for k in range(w):
                        tf[i][k] = True
                if wp[j]:
                    for k in range(h):
                        tf[k][j] = True
        cnt = 0
        for i in range(h):
            for j in range(w):
                if not tf[i][j]:
                    if c[i][j] == '#':
                        cnt += 1

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

Submission status: Accepted

Solution code:
import itertools

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

cij=[[""]*w for i in range(h)]
for i in range(h):
    cij[i]=list(input())

icnt=0
for i in itertools.product([0,1], repeat=h):
    for j in itertools.product([0,1], repeat=w):
        csum=0
        for ii in range(h):
            if i[ii]==1:
                for jj in range(w):
                    if j[jj]==1:
                        if cij[ii][jj]=="#":
                            csum+=1
        if csum==k:
            icnt+=1

print(icnt)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
c = [0]*h
for i in range(h):
    c[i] = list(input())
lis = []
for i in range(h):
    for j in range(w):
        if c[i][j] == "#":
            lis.append([i,j])
ans = 0
for i in range(2**(w+h)):
    num = 0
    lis_w = []
    lis_h = []
    for j in range(w+h):
        if (i >> j)&1:
            if j >= w:
                lis_h.append(j-w)
            else:
                lis_w.append(j)
    for I,J in lis:
        sw = 1
        if I in lis_h:
            sw = 0
        if J in lis_w:
            sw = 0
        if sw == 1:
            num += 1
    if num == k:
        ans += 1
print(ans)