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:
#!/usr/bin/env python3

import itertools
import copy

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

ccs = []

hnum = list(range(h))
wnum = list(range(w))

def countBlack(cc):
    ans = 0
    for i in range(h):
        ans += cc[i].count('#')
    return ans

ans = 0
# column
for i in range(w+1):
    for comb_column in list(itertools.combinations(wnum, i)):
        for p in range(h+1):
            for comb_row in list(itertools.combinations(hnum, p)):

                if len(comb_column)==w or len(comb_row)==h:
                    break

                cc = copy.deepcopy(c) 
                # print('comb_column =', comb_column)
                # print('len(comb_column) =', len(comb_column))
                # print('comb_row =', comb_row)
                # print('len(comb_row) =', len(comb_row))
                # column を塗る
                for j in range(len(comb_column)):
                    for j2 in range(h):
                        cc[j2][comb_column[j]] = 'R'

                # row を塗る
                for q in range(len(comb_row)):
                    for r in range(w):
                        cc[comb_row[q]][r] = 'R'

                # matrix
                # for s in range(h):
                #     print(cc[s])
                # print()

                ccs.append(cc)

for i in ccs:
    if k == countBlack(i):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from copy import deepcopy

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

ans = 0
for hl in product([0, 1], repeat=h):
    for wl in product([0, 1], repeat=w):
        cc = deepcopy(c)
        for i, hi in enumerate(hl):
            for j, wj in enumerate(wl):
                if hi == 1 or wj == 1:
                    cc[i][j] = 'r'
        cnt = 0
        for s in cc:
            cnt += sum(si == '#' for si in s)
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np


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

c = np.empty(0)

for i in range(H):
    tmp = list(input())
    c = np.append(c, tmp)
    
c = c.reshape([H, W])

num = 0
_max = 2 ** (H+W)
count = 0

for i in range(_max):
    bin_num = format(num, 'b')
    for j in range((H+W) - len(bin_num)):
        bin_num = '0' + bin_num
    tmp = bin_num
    c2 = c.copy()
    for j in range(H):
        if bin_num[j] == '1':
            c2[j, :] = 'r'
    for j in range(H, H+W):
        if bin_num[j] == '1':
            c2[:, j-H] = 'r'
    if np.count_nonzero(c2 == '#') == K:
        count += 1
    num += 1
        
print(count)

Submission status: Accepted

Solution code:
import itertools

h,w,k=[int(x) for x in input().rstrip().split()]
l=[]
bl=0
yoko=[]
tate=[]
ans=0
for i in range(h):
  W=[x for x in input()]
  l.append(W)
  bl=0
  for s in W:
    if s=="#":
      bl+=1
  yoko.append(bl)

for i in range(w):
  bl=0
  for j in range(h):
    if l[j][i]=="#":
      bl+=1
  tate.append(bl)

ans=0
if sum(tate)==k:
  ans=1
else:
  ans=0
Y=[]
y_l=[i for i in range(len(yoko))]
for i in range(1,len(yoko)+1):
  for ii in itertools.combinations(y_l,i):
    a=0
    for s in ii:
      a+=yoko[s]

    if sum(tate)-a==k:
      ans+=1
    Y.append(ii)
t_l=[i for i in range(len(tate))]
X=[]
for i in range(1,len(tate)+1):
  for ii in itertools.combinations(t_l,i):
    a=0
    for s in ii:
      a+=tate[s]
    if sum(tate)-a==k:
      ans+=1
    X.append(ii)

now=0
for i in X:#tate
  for j in Y:#yoko    
    for ii in i:
      now+=tate[ii]
    for jj in j:
      now+=yoko[jj]
    for jj in j:
      for ii in i:
        if l[jj][ii]=="#":
          now-=1
    if sum(tate)-now==k:
      ans+=1
    now=0
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

kuro = []

for i in range(h):
    tmp = input()
    a = []
    for j in tmp:
        if j == '#':
            a.append(True)
        else:
            a.append(False)
        
    kuro.append(a)

ans=0
for i in range(h+1):
  for j in range(w+1):
    for n in itertools.combinations(list(range(h)),i):
      for m in itertools.combinations(list(range(w)),j):
        count = 0
        for a in n:
          for b in m:
            if(kuro[a][b]):count+=1
        if(count == k):
          ans += 1
print(ans)

Submission status: Accepted

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

c = []
count = 0
for i in range(h):
    cl = list(input())
    c.append(cl)
    count += cl.count("#")

hc = 2 ** h
wc = 2 ** w
result = 0

for i in range(hc):
    for j in range(wc):
        mc = 0
        hc2 = i
        hclis = []
        if i == 0:
            hclis = [0]
        while hc2 != 0:
            hclis.append(hc2 % 2)
            hc2 = hc2 // 2
        wc2 = j
        wclis = []
        if j == 0:
            wclis = [0]
        while wc2 != 0:
            wclis.append(wc2 % 2)
            wc2 = wc2 // 2
        for k1 in range(len(hclis)):
            if hclis[k1] == 1:
                mc += c[k1].count("#")
        for k2 in range(len(wclis)):
            if wclis[k2] == 1:
                for l in range(h):
                    if c[l][k2] == "#":
                        mc += 1
        for k1 in range(len(hclis)):
            for k2 in range(len(wclis)):
                if hclis[k1] == 1 and wclis[k2] == 1 and c[k1][k2] == "#":
                    mc -= 1

        if count - mc == k:
            result += 1

print(result)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import itertools
input = lambda: sys.stdin.readline().rstrip()

def main():
    h, w, k = map(int, input().split())
    ans = 0
    grid = []
    index = [i for i in range(h + w)]
    for _ in range(h):
        grid.append(list(input()))
    grid = np.array(grid)
    if np.count_nonzero(grid == '#') == k:
        ans += 1
    for i in range(1, h+w+1):
        for combs in itertools.combinations(index, i):
            tmp = grid.copy()
            row, col = [], []
            for comb in combs:
                if comb >= w:
                    row.append(comb - w)
                else:
                    col.append(comb)
            tmp = np.delete(tmp, row, 0)
            tmp = np.delete(tmp, col, 1)
            if np.count_nonzero(tmp == '#') == k:
                ans += 1
    print(ans)                
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    ans = 0
    H,W,K = map(int, input().split())
    l = []
    for _ in range(H):
        l.append(list(input().rstrip('\n')))
    for i in range(2**H):
        for j in range(2**W):
            b = 0
            for h in range(H):
                for w in range(W):
                    if i>>h & 1 and j>>w & 1 and l[h][w] == '#':
                        b += 1
            if b == K:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# from pprint import pprint
# import math
# import collections
import numpy as np
import itertools
import copy

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

white = '.'
black = '#'

c = []
c2 = [[0] * w for h in range(h)]
for i in range(h):
    c.append(list(input()))

for i in range(h):
    for j in range(w):
        c2[i][j] = 1 if c[i][j] == black else 0

# bit全探索
pattern = []
cnt = 0
for _h in list(itertools.product([0, 1], repeat=h)):
    for _w in list(itertools.product([0, 1], repeat=w)):
        pattern.append((_h, _w))

cnt = 0
for p in pattern:
    # print(p)
    test_c = copy.deepcopy(c2)
    for i, ih in enumerate(p[0]):
        for j, jw in enumerate(p[1]):
            if ih == 0 or jw == 0:
                test_c[i][j] = 0
    sum = np.array(test_c).sum()
    # print(sum)

    if sum == k:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys, copy
input = sys.stdin.readline
def main():
    h, w , k = map(int, input().split())
    ls = []
    for _ in range(h):
        ms = []
        t=str(input().rstrip())
        for i in range(len(t)):
            if t[i] =='.':
                ms.append(0)
            else:
                ms.append(1)
        ls.append(ms)

    def num(x, y):
        lt = copy.deepcopy(ls)
        x2 = format(x, 'b').rjust(h, '0')
        y2 = format(y, 'b').rjust(w, '0')
        for i in range(len(x2)):
            if x2[i]=='0':
                lt[i]= [0]*len(y2)
        for j in range(len(y2)):
            if y2[j]=='0':
                for t in range(len(x2)):
                    lt[t][j]= 0
        re = 0
        for i in lt:
            re += sum(i)

        return re

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w, k=map(int,input().split())
masu =[input() for _ in range(h)]
ans=0
for x in range(2**h):
    for y in range(2**w):
        cnt=0
        for i in range(h):
            for j in range(w):
                if x>>i&1 and y>>j&1 and masu[i][j]=="#":
                    cnt+=1
        if cnt == k:
            ans += 1
print(ans)####

Submission status: Accepted

Solution code:
import numpy as np

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

c = [[1 if s=="#" else 0 for s in input()] for _ in range(H)]
#print(c)
def func(mats, ans, h, hmax, w, wmax):
  buf = []
  if h<hmax:
    for mat in mats:
      m = mat.copy()
      m[h,:] = 0
      s = m.sum()
      if s>K:
        buf.append(m)
      if s==K:
        ans.append(m)
        buf.append(m)
      buf.append(mat)
    func(buf, ans, h+1, hmax, w, wmax)
  elif w < wmax:
    for mat in mats:
      m = mat.copy()
      m[:,w] = 0
      s = m.sum()
      if s>K:
        buf.append(m)
      if s==K:
        ans.append(m)
        buf.append(m)
      buf.append(mat)
    func(buf, ans, h, hmax, w+1, wmax)
  else:
    return

ans = []
if np.array(c).sum()==K:
  ans.append(np.array(c))
func([np.array(c)], ans, 0, H, 0, W)
print(len(ans))

Submission status: Accepted

Solution code:
# from pprint import pprint
# import math
# import collections
import numpy as np
import itertools

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

white = '.'
black = '#'

c = []
c2 = [[0] * w for h in range(h)]
for i in range(h):
    c.append(list(input()))

for i in range(h):
    for j in range(w):
        c2[i][j] = 1 if c[i][j] == black else 0

nc = np.array(c2)

black_total = np.sum(c2)

h_blacks = list(np.sum(c2, axis=1))
w_blacks = list(np.sum(c2, axis=0))

# print(h_blacks)
# print(w_blacks)

import copy

# bit全探索
pattern = []
cnt = 0
for _h in list(itertools.product([0, 1], repeat=h)):
    for _w in list(itertools.product([0, 1], repeat=w)):
        pattern.append((_h, _w))

cnt = 0
for p in pattern:
    # print(p)
    test_c = copy.deepcopy(c2)
    for i, ih in enumerate(p[0]):
        for j, jw in enumerate(p[1]):
            if ih == 0 or jw == 0:
                test_c[i][j] = 0
    sum = np.array(test_c).sum()
    # print(sum)

    if sum == k:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
c=[list(input()) for i in range(H)]
count=0
for bit_h in range(1<<H):
    for bit_w in range(1<<W):
        black=0
        for h in range(H):
            for w in range(W):
                if c[h][w]=="#" and (bit_h>>h)&1 and (bit_w>>w)&1:
                    black+=1
        if black==K:
            count+=1
print(count)

Submission status: Accepted

Solution code:
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前
sort()
sorted(reverse=true)
配列の初期化
配列名=[a]*n+[b]*m
Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions
import sys
d = stdin.readline().rstrip().split()
H = int(d[0])
W = int(d[1])
K = int(d[2])

data = []
bCount = 0
result = 0
for el1 in range(H):
    tmp = stdin.readline().rstrip().split()
    d = []
    for el in tmp:
        for el3 in el:
            if el3 == '#':
                bCount += 1
            d.append(el3)
    data.append(d)
datas = copy.deepcopy(data)
counter = 0
for el in range(H+W):
    counter += 2**el
for el in range(counter+1):
    bin_str = ''.join(list(reversed(str(bin(el))[2:])))
    poss = []
    count = 0
    for el2 in bin_str:
        if el2 == '1':
            poss.append(count)
        count += 1
    res = 0
    for el2 in poss:
        if el2 >= H:
            el2 -= H
            for el3 in datas:
                el3[el2] = 'o'
        else:
            datas[el2] = ['o']*W
    for el2 in datas:
        res += el2.count('#')
    if res == K:
        result += 1
    datas = copy.deepcopy(data)
print(result)

Submission status: Accepted

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

masu = []
for h in range(H):
    tmp = [1 if i == "#" else 0 for i in input()]
    masu.append(tmp)

ans = 0

h_product = list(itertools.product([0, 1], repeat=H))
w_product = list(itertools.product([0, 1], repeat=W))

for h_pro in h_product:
    for w_pro in w_product:
        tmp = 0
        for h in range(len(h_pro)):
            for w in range(len(w_pro)):
                tmp += h_pro[h] * w_pro[w] * masu[h][w]
        if tmp == K:
            ans += 1
                
       
print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
C=[list(input().strip()) for _ in range(h)]
ans=0
for i in range(1<<h):
    for j in range(1<<w):
        cnt=0
        for x in range(h):
            if (i>>x)&1==1:
                continue
            for y in range(w):
                if (j>>y)&1==1:
                    continue
                cnt+=int(C[x][y]=='#')
        if cnt==k:
            ans+=1
print(ans)

Submission status: Accepted

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

ret = 0

for i in range(1 << h):
    for j in range(1 << w):
        cnt = 0
        for x in range(h):
            for y in range(w):
                if c[x][y] == '#' and (i >> x) & 1 and (j >> y) & 1:
                    cnt += 1
        if cnt == k:
            ret += 1

print(ret)

Submission status: Accepted

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

grid = []
ans = 0
for _ in range(H):
    grid.append(list(input()))

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 grid[x][y] == "#":
                        now += 1
        if now == K:
            ans += 1
print(ans)

Submission status: Accepted

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

c = []
nb = 0
for _ in range(h):
   tmp = [x for x in input()]
   nb += tmp.count('#')
   c.append(tmp)

d = []
for i in range(w):
   tmp = []
   for j in range(h):
      tmp.append(c[j][i])
   d.append(tmp)

x = [0] * h
for i in range(h):
   x[i] = c[i].count('#')

ans = 0
for i in range(2**h):
   y = [0] * w
   for j in range(w):
      y[j] = d[j].count('#')

   cnt1 = 0
   for ik in range(h):
      if ((i >> ik) & 1):
         cnt1 += x[ik]
         for j in range(w):
            if c[ik][j] == '#':
               y[j] -= 1

   for j in range(2**w):
      cnt2 = 0
      for jk in range(w):
         if ((j >> jk) & 1):
            cnt2 += y[jk]

      if(nb - (cnt1 + cnt2)) == k:
         ans += 1

print(ans)

Submission status: Accepted

Solution code:
h, w, k=map(int,input().split())
masu =[input() for _ in range(h)]
ans=0
for x in range(2**h):
    for y in range(2**w):
        cnt=0
        for i in range(h):
            for j in range(w):
                if x>>i&1 and y>>j&1 and masu[i][j]=="#":
                    cnt+=1
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

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

MasuMoji=[input() for i in range(H)]  

###
def countAllmasu(masu,H,W):
  total=0
  for h in range(H):
    for w in range(W):
      total+=masu[h][w]
  return(total)
###

masu=[]
for h in range(H):
  masu.append([])
  for w in range(W):
    if MasuMoji[h][w]==".":
    	masu[h].append(0)
    else:
        masu[h].append(1)
  

H_OI=[]
for i in range(2 ** H):
    OI=[]
    #print("pattern {}: ".format(i), end="")
    for j in range(H):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            OI.append(1)  # フラグが立っていたら bag に果物を詰める
        else:
            OI.append(0)
            
    H_OI.append(OI)

  
W_OI=[]
for i in range(2 ** W):
    OI=[]
    #print("pattern {}: ".format(i), end="")
    for j in range(W):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            OI.append(1)  # フラグが立っていたら bag に果物を詰める
        else:
            OI.append(0)
            
    W_OI.append(OI)

patterns=0


for h in H_OI:
  for w in W_OI:
      
    tempmasu= copy.deepcopy(masu)

    for h2 in range(H):
      for w2 in range(W):
        if h[h2]==1 or w[w2]==1:
          tempmasu[h2][w2]=0


    #print(countAllmasu(tempmasu,H,W))
    if countAllmasu(tempmasu,H,W)==K:
      patterns+=1
      
print(patterns)

Submission status: Accepted

Solution code:
from itertools import combinations
from copy import deepcopy
numCount = 0
h, w, k = map(int, input().split())
cList = []
for i in range(h):
    toAdd = list(input())
    cList.append(toAdd)
for i in range(h + 1):
    hCom = list(combinations(list(range(h)), i))
    hComKai = []
    for l in hCom:
        hComKai.append(list(l))
    for j in range(w + 1):
        for u in hComKai:  # [[0,1],[0,2],[1,2]]
            cListKai = deepcopy(cList)
            for o in sorted(u, reverse=True):
                cListKai.pop(o)
            kCom = list(combinations(list(range(w)), j))
            kComKai = []
            for p in kCom:
                kComKai.append(list(p))
            for y in kComKai:
                cListKaiKai = deepcopy(cListKai)
                for t in sorted(y, reverse=True):
                    for r in cListKaiKai:
                        r[t] = '.'
                bkCount = 0
                for q in cListKaiKai:
                    for a in q:
                        if a == '#':
                            bkCount += 1
                if bkCount == k:
                    numCount += 1

print(numCount)

Submission status: Accepted

Solution code:
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy

H, W, K = map(int, input().split())
dump(H, W, K)
c = []
for i in range(H):
    c.append(input())
dump(c)
ans = 0
for rows, columns in it.product(it.product({True, False}, repeat=H), it.product({True, False}, repeat=W)):
    rIdx = {i for i, ri in enumerate(rows) if ri}
    cIdx = {j for j, cj in enumerate(columns) if cj}
    dump(rIdx, cIdx)
    cnt = 0
    for i in range(H):
        for j in range(W):
            if (i not in rIdx) and (j not in cIdx) and (c[i][j] == '#'):
                cnt += 1
    dump(cnt)
    if cnt == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np 
h,w,k=map(int,input().split())
c=[None]*h
for i in range(h):
  c[i]=list(map(int,input().replace(".","0 ").replace("#","1 ").split()))
#sum_c=sum(c)
d=np.array(c)
c=np.copy(d)
e=np.copy(c)
r=0
#h+=-1
#w+=-1
for j in range(2**h):
  j_b=bin(j)[:1:-1]
  e=np.copy(c)
  #print(j)
  for i_j,d_j in enumerate(j_b):
    #print(d_j)
    if d_j=="1":
      #print(d[i_j])
      e[i_j]=0
      #print(d)
    #else:
    #  e[i_j]=c[i_j]
  for m in range(2**w):
    d=np.copy(e)
      #print(m)
    m_b=bin(m)[:1:-1]
      #print(j_b)
      #print(m_b)
    for i_m,d_m in enumerate(m_b):
      if d_m=="1":
        d[:,i_m]=0
        #else:
          #print(m_b)
        #  d[:,i_m]=c[:,i_m]
      #print(d)
    if np.sum(d)==k:
      r+=1
        #print(m_b)
        #print(j_b)
        #print(d)
      #d=np.copy(e)
    #d=np.copy(c)
print(r)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

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

C = []
base = 0
for i in range(H):
	string = input()
	string = string.replace('.', '0')
	string = string.replace('#', '1')
	lst = list(string)
	lst = [int(c) for c in lst]
	C.append(lst)
	base += sum(lst)

C = np.array(C)
orig = C.copy()
count = 0

for i in range(H+1):
	for j in range(W+1):
		for c in combinations(range(H), i):
			for d in combinations(range(W), j):
				for row in c:
					C[row] = [0] * W
				for col in d:
					C[:, col] = [0] * H
				if np.sum(C) == K:
					count += 1
				C = orig.copy()

print(count)

Submission status: Accepted

Solution code:
import itertools
import copy

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

p_list = list(itertools.product(range(0, 2), repeat = (h + w)))

for i in range(len(p_list)):
    damy = copy.deepcopy(c_list)
    for j in range(h):
        if p_list[i][j] == 1:
            damy[j] = ["."] * w
    for j in range(w):
        if p_list[i][h + j] == 1:
            for l in range(h):
                damy[l][j] = "."
    count = 0
    for j in range(h):
        count += damy[j].count('#')
    if count == k:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy
H,W,K= map(int,input().split())
List=[list(input()) for i in range(H)]
nums=[]
total=0
for i in range(1,H+W+1):
    nums.append(i)
for q in range(0,H+W+1):
    hoge=[]
    for balls in itertools.combinations(nums, q):
        hoge.append(balls)
    for p in range(0,len(hoge)):
        Listo=copy.deepcopy(List)
        for i in range(1,H+1):
            if i in hoge[p]:
                for j in range(0,W):
                    Listo[i-1][j]="x"
        for i in range(H+1,H+W+1):
            if i in hoge[p]:
                for j in range(0,H):
                    Listo[j][i-H-1]="x"
        s=0
        for i in range(0,H):
            for j in range(0,W):
                if Listo[i][j]=="#":
                    s+=1
        if s== K:
            total+=1
print(total)

Submission status: Accepted

Solution code:
import numpy as np
import sys

def combinationlist(n):
    p_sets = []
    for i in range(2 ** n):
        lst = [x + 1 for x in range(i) if 2 **x & i]
        if lst != []:
            p_sets.append(lst)
    p_sets = sorted(p_sets, key=lambda x: len(x))
    return p_sets


def main():
    data = input().split()
    h = int(data[0])
    w = int(data[1])
    k = int(data[2])
    c = np.empty((h,w),dtype=str)
    for i in range(h):
        s = input()
        c[i,:] = np.array([c for c in s])
    rowset = []
    colset = []
    all_black = 0
    for i in range(h):
        data = c[i,:]
        count = len(data[data == '#'])
        all_black += count
        rowset.append([count, data])
    for j in range(w):
        data = c[:,j]
        count = len(data[data=='#'])
        colset.append([count,data])
    ans = 0
    if k == all_black:
        ans += 1
    rowList = combinationlist(h)
    colList = combinationlist(w)
    for comb in rowList:
        if w*len(comb) > h*w - k:
            continue
        count = 0
        for i in  comb:
            count += rowset[i-1][0]
        if count == all_black - k:
            ans += 1
        if count <= all_black - k:
            for comb_2 in colList:
                comb_count = count
                for j in comb_2:
                    comb_count += colset[j-1][0]
                    for s in comb:
                        if '#' == colset[j-1][1][s-1]:
                            comb_count = comb_count -1
                if comb_count == all_black - k:
                    ans += 1
    for comb in colList:
        if h*len(comb) > h*w - k:
            continue
        count = 0
        for i in  comb:
            count += colset[i-1][0]
        if count == all_black - k:
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
h, w, k = map(int, input().split())
_map = np.zeros((h, w), dtype = int)
ans = 0
for i in range(h):
  _str = list(input())
  for j in range(w):
    if (_str[j] == "#"):
      _map[i, j] = 1
      
for i in range(2**(h + w)):
  _array = np.copy(_map)
  for j in range(h + w):
    if ((i >> j) & 1):
      if j < h:
        _array[j, :] = 0
      else:
        _array[:, j - h] = 0
  if np.sum(_array) == k:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
h,w,k = map(int,input().split())
c = []
row = list(itertools.product(range(2),repeat=h))#塗る行の組み合わせ
col = list(itertools.product(range(2),repeat=w))#塗る列の組み合わせ
for i in range(h):
    c.append(input())

ans = 0

for arr_row in row:
    for arr_col in col:
        val = 0
        for i in range(h):
            for j in range(w):
                if c[i][j] == "#" and arr_row[i] == 1 and arr_col[j] == 1:
                    val +=1
        if val == k:
            ans +=1
print(ans)

Submission status: Accepted

Solution code:
import itertools

h, w, k = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for x, y in itertools.product(range(2 ** h), range(2 ** w)):
    cnt = 0
    for i, j in itertools.product(range(h), range(w)):
        if x >> i & 1 or y >> j & 1: continue
        if c[i][j] == '#': cnt += 1
    if cnt == k:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


H, W, K = ints()

import numpy as np
C = np.array(read_map_as(H))
ans = 0
for rows in product(range(2), repeat=H):
    C_r = C.copy()
    for i, tf in enu(rows):
        if tf:
            C_r[i, :] = 0
    for cols in product(range(2), repeat=W):
        C_rc = C_r.copy()
        for j, tf in enu(cols):
            if tf:
                C_rc[:, j] = 0
        ans += (C_rc.sum() == K)
print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=["" for i in range(h)]
checkw="."*w
gyou=[]
retu=[]
black=[]
alww=[]
alwh=[]
pat1=[]
pat2=[]
ans=0
for i in range(h):
    c[i]=input()
    for j in range(w):
        if (c[i][j]=="#"):
            black.append(len(black))
            gyou.append(i)
            retu.append(j)
            

for i in range(2**h):
    tmp1 = [False] * (h)
    for j in range(h):
        if i >> j & 1:
            tmp1[j] = True
    pat2.append(tmp1)
    
for i in range(2**w):
    tmp2 = [False] * (w)
    for j in range(w):
        if i >> j & 1:
            tmp2[j] = True
    pat1.append(tmp2)


for i in range(len(pat1)):
    for j in range(len(pat2)):
        g=[]
        for x in range(w):
            if (pat1[i][x]==True):
                for l in range(len(black)):
                    if (retu[l]==x):
                        g.append(l)
        for y in range(h):
            if (pat2[j][y]==True):
                for l in range(len(black)):
                    if (gyou[l]==y):
                        g.append(l)
        #print(g)
        #print(gyou)
        #print(retu)
        #print(pat1)
        #print(pat2)
        #print(g)
        #print(len(set(g)))
        if (k==len(black)-len(set(g))):
            #print(pat1[i])
            #print(pat2[i])
            ans+=1
            
print(ans)