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 itertools

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

def c2i(c):
    if c == '.':
        return 0
    elif c == '#':
        return 1

m = []
lines = []
rows = [0] * W
total = 0

for idx in range(H):
    c = input()
    m.append([*c])

    black_num = c.count('#')
    total += black_num
    lines.append(black_num)
    rows = [row + c2i(c[i]) for i, row in enumerate(rows)]

patterns = []
count = 0

for yy in itertools.product([0, 1], repeat=(H)):
    for xx in itertools.product([0, 1], repeat=(W)):
        sub = 0
        r = 0
        l = 0
        for idx_l, line in enumerate(yy):
            if line == 1:
                l += lines[idx_l]

        for idx_r, row in enumerate(xx):
            if row == 1:
                r += rows[idx_r]

        for idx_l, line in enumerate(yy):
            for idx_r, row in enumerate(xx):
                if not line or not row:
                    continue
                if m[idx_l][idx_r] == '#':
                    sub += 1
        black_num = total - (l + r) + sub
        if black_num == K:
            patterns.append([xx, yy])
            count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools
h,w,k = map(int,input().split())
s = ["" for _ in range(h)]
for i in range(h):
  si = str(input())
  s[i] = si
lh = [i for i in range(h)]
lw = [j for j in range(w)]
sh = [0 for _ in range(h)]
sw = [0 for _ in range(w)]
for i in range(h):
  for j in range(w):
    if s[i][j] == "#":
      sh[i] += 1
      sw[j] += 1  
g = sum(sh) - k
c = 0
for i in range(h+1):
  for vh in itertools.combinations(lh,i):
    for j in range(w+1):
      for vw in itertools.combinations(lw,j):
        t = 0
        for hx in vh:
          t += sh[hx] 
        for hy in vw:
          t += sw[hy]
        for hx in vh:
          for hy in vw:
            if s[hx][hy] == "#":
              t -= 1
        if t == g:
          c += 1
print(c)

Submission status: Accepted

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

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

def sw(temp,n,b):
    if n == w:
        count = 0
        for c in temp:
            count += c.count("#")
        if count == k:
            return 1
        else:
            return 0
    else:
        temp1 = copy.deepcopy(temp)
        temp2 = copy.deepcopy(temp)
        if b == True:
            for i in range(h):
                temp1[i][n] = "2"
                temp2[i][n] = "2"

        return(sw(temp1,n+1,True)+sw(temp2,n+1,False))

def sh(temp,n,b):
    if n == h:
        temp1 = copy.deepcopy(temp)
        temp2 = copy.deepcopy(temp)
        return(sw(temp1,0,True)+sw(temp2,0,False))
    else:
        temp1 = copy.deepcopy(temp)
        temp2 = copy.deepcopy(temp)
        if b == True:
            temp1[n] = ["2"]*w
            temp2[n] = ["2"]*w
        return(sh(temp1,n+1,True)+sh(temp2,n+1,False))

print(int((sh(C,0,True) + sh(C,0,False))/4))

Submission status: Accepted

Solution code:
import copy

def blackCount(x):
  cc=0
  pp=len(x)
  for l in range(pp):
    cc+=x[l].count('#')
  return cc

def rowChange(x,row):
  ss=list(x[row])
  for l in range(w):
    ss[l]='.'
  x[row]="".join(ss)
  
def colChange(x,col):
  for l in range(h):
    ss=list(x[l])
    ss[col]='.'
    x[l]="".join(ss)

h,w,k=map(int,input().split())
c=[]
count=0
for i in range(h):
  c.append(input())
  
for i in range(2**h):
  for j in range(2**w):
    c2=copy.deepcopy(c)
    for a in range(h):
      if (i>>a)%2==1:
        rowChange(c2,a)
        
    for b in range(w):
      if (j>>b)%2==1:
        colChange(c2,b)
    
    if blackCount(c2)==k:
      count+=1
      
print(count)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

h,w, k = [int(n) for n in input().split()]

temp2 = []
for i in range(h):
  temp= []
  for s in input():
    if s == '.':
      temp.append(0)
    else:
      temp.append(1)
  temp2.append(temp)
matrix = np.array(temp2)

comb_h = []
for i in range(h+1):
  for c in combinations(list(range(h)), i):
    comb_h.append(c)
comb_w = []
for i in range(w+1):
  for c in combinations(list(range(w)), i):
    comb_w.append(c)

cnt = 0
for h_seq in comb_h:
  for w_seq in comb_w:
    total = 0
    for h_item in h_seq:
      total += np.sum(matrix[h_item, w_seq])
    if total == k:
      cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
h,w,k = list(map(int,input().split()))
mr_list = [input() for i in range(h)]
output = 0
import copy
for i in range(2**(h+w)):
  row = []
  m_list = copy.copy(mr_list)
  for j in range(h+w):
    if ((i >> j) & 1):
      row.append(j)
  for r in row:
    if r < h:
      m_list[r] = "r"*w
    else:
      for i,m in enumerate(m_list):
        m_list[i] = m[:r-h] + 'r' + m[r-h+1:]
  out =0
  for m in m_list:
    out += m.count("#")
  if out == k:
    output += 1
print(output)

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):
    D = copy.deepcopy(C)
    for ii in range(H):
        if ((i >> ii) & 1):
            # フラグが立った行を塗りつぶす
            for l in range(W):
                D[ii][l] = "."
    for j in range(1 << W):
        E = copy.deepcopy(D)
        for jj in range(W):
            if ((j >> jj) & 1):
                # フラグが立った列を塗りつぶす
                for k in range(H):
                    E[k][jj] = "."
        if K == sum(E,[]).count("#"):
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from itertools import product

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

s = 0

def num_to_bit_boolean(n):
    return [ bool(n & b) for b in [ 1, 2, 4, 8, 16, 32 ] ]

def del_row_col(rows_num, cols_num, board):
    global s

    for bit, row in zip(num_to_bit_boolean(rows_num), range(h)):
        if bit:
            board[row] = [ '.' ] * w

    for row in board:
        for bit, col in zip(num_to_bit_boolean(cols_num), range(w)):
            if bit:
                row[col] = '.'

    if count_black(board) == k:
        # print('row', num_to_bit_boolean(rows_num)[:h])
        # print('col', num_to_bit_boolean(cols_num)[:w])

        s += 1

    return board

def count_black(board):
    return sum( row.count('#') for row in board )

for row, col in product(range(2 ** h), range(2 ** w)):
    del_row_col(row, col, deepcopy(board))

print(s)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

bw_map = []
row_list = []
for _ in range(H):
    tmp = list(input())
    bw_map.append(tmp)

bw_map = np.array(bw_map)
score = np.sum(bw_map=="#")


result = 0
"""
if score==K:
    hs = []
    for h in range(H):
        tmph = np.sum(bw_map[h, :]==".")
        if tmph == W:
            hs.append(h)
    ws = []
    for w in range(W):
        tmpw = np.sum(bw_map[w, :]==".")
        if tmpw == H:
            ws.append(w)
    print(1)
"""
if score==K:
    result+=1
if score<K:
    print(0)
else:
    score = 100000
    for h in range(H):
        for w in range(W):
            if h==0 and w==0:
                continue
            h_args = list(itertools.combinations(list(range(H)), h))
            w_args = list(itertools.combinations(list(range(W)), w))
            for hs in h_args:
                for ws in w_args:
                    tmphs=hs
                    tmpws=ws
                    hs = list(hs)
                    ws = list(ws)
                    hs = list(set(list(range(H)))-set(hs))
                    ws = list(set(list(range(W)))-set(ws))
                    if len(hs)==0:
                        score = np.sum(bw_map[:, ws]=="#")
                    elif len(ws)==0:
                        score = np.sum(bw_map[hs, :]=="#")
                    else:
                        tmp = bw_map[hs]
                        tmp = tmp[:, ws]
                        score = np.sum(tmp=="#")

                    if score == K:
                        result+=1
    print(result)

Submission status: Accepted

Solution code:
def resolve():
    from copy import deepcopy
    h, w, K = list(map(int, input().split()))

    white = 0
    black = 1
    red = 0
    matrix = []
    for i in range(h):
        chars = input()
        line = []
        for char in chars:
            if char == '.':
                line.append(white)
            elif char == '#':
                line.append(black)
        matrix.append(line)

    count = 0
    for i in range(1 << (h + w)):
        m = deepcopy(matrix)
        for j in range(h):
            if (i >> j) & 1 == 1:
                m[j] = [red for _ in range(w)]

        for j in range(w):
            if (i >> (j + h)) & 1 == 1:
                for k in range(h):
                    m[k][j] = red

        black_count = 0
        for j in range(h):
            for k in range(w):
                if m[j][k] == black:
                    black_count += 1

        if black_count == K:
            count += 1

    print(count)


if 'unittest' not in globals():
    resolve()

Submission status: Accepted

Solution code:
from math import gcd, sqrt, cos, radians, pi, floor, ceil
from collections import defaultdict as d
from itertools import combinations as c
from string import ascii_lowercase as a

h, w, k = map(int, input().split())
t = []
total = 0
for i in range(h):
	t+=[input()]
	total += t[-1].count('#')
count = 0
for i in range(h):
	for j in range(w):
		for u in c(list(range(h)), i):
			for v in c(list(range(w)), j):
				cnt = 0
				for x in u:
					cnt += t[x].count('#')
				for x in v:
					for y in range(h):
						if t[y][x] == '#' and y not in u:cnt += 1
				if total - cnt == k:
					count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
import itertools
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
#def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
h,w,k1=reads()
c=[]
for i in range(h):
  c.append(input())
res=0
for i in range(2**h):
  for j in range(2**w):
    selrows,selcolumn=[],[]
    k=0
    s=i
    while(True):  
      if s==0:
        break
      if s%2==1:
        selrows.append(k)  
      s//=2
      k+=1
    k=0
    t=j
    while(True):  
      if t==0:
        break
      if t%2==1:
        selcolumn.append(k)     
      t//=2
      k+=1
    blacknumber=0
    for k in range(h):
      for l in range(w):
        if c[k][l]==".":
          continue
        elif k in selrows or l in selcolumn:
          continue
        else:
          blacknumber+=1

    if blacknumber==k1:
      res+=1
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import itertools as it
import numpy as np

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    f = lambda x: 0 if x=='.' else 1
    H, W, K = list(map(int, input().split()))

    mat = np.zeros((H, W))
    for i in range(H):
        row = [c for c  in input()]
        for j in range(W):
            mat[i,j] = f(row[j])

    
    # Failed to predict input format
    H_res = [0] * (H*W +1)
    W_res = [0] * (H*W+1)

    combs = list(range(H+W))
    count= 0
    for L in range(0, H+W+1):
        for subset in it.combinations(combs, L):
            subset = list(subset)
            row_idxs = [x for x in subset if x < H]
            col_idxs = [x-H for x in subset if x >= H]
            # if row_idxs == []:
            #     s = np.sum(mat[:,col_idxs])
            # elif col_idxs == []:
            #     s = np.sum(mat[row_idxs])
            # else:
            new_mat = mat[row_idxs][: , col_idxs]
            s = np.sum(new_mat)  
            if s == K:
                count += 1
    # count = 0
    # H_combs = list(range(H))
    # for L in range(0, len(H_combs)+1):
    #     for subset in it.combinations(H_combs, L):
    #         yokonutta = mat.copy()
    #         yokonutta[list(subset)] = 0
            
    #         _, idxs = np.where(yokonutta.sum(axis=0, keepdims=True)!=0)

    #         W_combs = idxs
    #         for L in range(0, len(W_combs)+1):
    #             for subset2 in it.combinations(W_combs, L):
    #                 tatenutta = yokonutta.copy()
    #                 tatenutta[:, list(subset2)] = 0

    #                 if tatenutta.sum() == K:
    #                     count+= 1

    # r = range(36)
    # count = 0
    # for i,j in it.product(r,r):
    #     if i+j==K:
    #         count += H_res[i] + W_res[j]

    print(count)
    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def countSharp(s, h):
    tmp = s
    for i in range(len(s)):
        if ((h >> i) & 1) == 0:
            tmp = tmp[:i] + '.' + tmp[min(i+1, len(s)):]
    return len(tmp.replace('.', ''))


def countRes(AR, w, h):
    res = 0
    for i, s in enumerate(AR):
        if ((w >> i) & 1) == 0:
            continue
        res += countSharp(s, h)
    return res

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

for i in range(2**H):
    for j in range(2**W):
        if(countRes(C, i, j) == K):
            res += 1
print(res)

Submission status: Accepted

Solution code:
import numpy as np
H, W, K = map(int, input().split())
zu = np.zeros((H, W), dtype=int)

for h in range(H):
    zu[h, :] = (np.array(list(input())) == '#')

MAXX = 2**(H+W)
ans = 0
if np.sum(zu) == K:
    ans += 1

for c in range(1, MAXX):
    zu1 = np.copy(zu)
    for h in range(H):
        if (c & (1<<h)) > 0:
            zu1[h] = 0
    for w in range(W):
        if (c & (1<<(H+w))) > 0:
            zu1[:, w] = 0
    if np.sum(zu1) == K:
        ans += 1

print(ans)

Submission status: Accepted

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

kazu = 0

for i in range(2 ** w):
    for s in range(2 ** h):
        count = 0
        for j in range(w):
            if ((i >> j) & 1):
                for t in range(h):
                    if ((s >> t) & 1):
                        if c[t][j] == '#':
                            count += 1
            
        if count == k:
            kazu += 1

print(kazu)

Submission status: Accepted

Solution code:
import copy
import itertools
import numpy as np

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

list_H = []
for i in range(1, H+1):
    list_H.append(i)
list_W = []
for i in range(1, W+1):
    list_W.append(i)

for i in range(H+1):
    for v in itertools.combinations(list_H, i):
        tmp_masu = []
        for j in list(v):
            tmp_masu.append(c[j-1])
        tmp_masu = np.array(tmp_masu)
        for j in range(W+1):
            for x in itertools.combinations(list_W, j):
                try:
                    tmp_masu_ = copy.deepcopy(tmp_masu)
                    count = 0
                    for k in list(x):
                        tmp_masu_ = np.delete(tmp_masu_, k-1-count, 1)
                        count += 1
                    tmp = tmp_masu_.tolist()
                    count_ = 0
                    for k in range(len(tmp)):
                        count_ += tmp[k].count('#')
                    if count_ == K:
                        ans += 1
                except IndexError:
                    pass
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

result = 0

n_c = np.array(c)

for y in itertools.product([0,1], repeat = h):
    for x in itertools.product([0,1], repeat = w):
        # print(y, x)
        n_c2 = np.array(c)
        for i, y2 in enumerate(y):
            if y2 == 1:
                n_c2[i] = 'R'
        for i, x2 in enumerate(x):
            if x2 == 1:
                n_c2[:,i] = 'R'
        # print(n_c2)
        m = np.count_nonzero(n_c2 == '#')
        if k == m:
            result += 1

print(result)

Submission status: Accepted

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

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

# print(cs)

hpatterns = []
for i in range(h + 1):
    hpatterns += list(itertools.combinations(range(h), i))
wpatterns = []
for i in range(w + 1):
    wpatterns += list(itertools.combinations(range(w), i))

# print(hpatterns)
# print(wpatterns)

c = 0
for hpattern in hpatterns:
    for wpattern in wpatterns:
        black = 0
        cs2 = copy.deepcopy(cs)
        for pi in hpattern:
            cs2[pi] = ['' for k in range(w)]

        for pj in wpattern:
            for s in range(len(cs2)):
                # print(pj, s)
                cs2[s][pj] = ''
        # print(wpattern, hpattern, cs2)
        for s in cs2:
            black += s.count('#')

        if black == k:
            c += 1

print(c)

Submission status: Accepted

Solution code:
#これは173_c
import sys
import itertools
input = sys.stdin.readline

H,W,K = list(map(int,input().split()))
lis_H = []
lis_W = []

for i in range(H):
    Hi = list(itertools.combinations(range(0,H),i+1))
    lis_H.append(Hi)
lis_H.append([(99,)])
for i in range(W):
    Wi = list(itertools.combinations(range(0,W),i+1))
    lis_W.append(Wi)
lis_W.append([(99,)])
C = []
for i in range(H):
    ci = input().rstrip()
    C.append(ci)
ans = 0
for hi in range(len(lis_H)):
    for hj in range(len(lis_H[hi])):
        for wi in range(len(lis_W)):
            for wj in range(len(lis_W[wi])):
                counter = 0
                for hk in range(H):
                    for wk in range(W):
                        if C[hk][wk] == '#' and ((hk not in lis_H[hi][hj]) and (wk not in lis_W[wi][wj])):
                            counter +=1
                if counter == K:
                    ans += 1


print(ans)

Submission status: Accepted

Solution code:
import itertools
H, W, K = map(int, input().split())
C = []
for _ in range(H):
    C.append(input())
r = 0
for i in range(1, H+1):
    for ii in itertools.combinations(range(H), i):
        for j in range(1, W+1):
            for jj in itertools.combinations(range(W), j):
                l = 0
                for x in [C[iii] for iii in ii]:
                    xx = [x[jjj] for jjj in jj]
                    l += len([xxx for xxx in xx if xxx == '#'])
                if l == K:
                    r += 1
print(r)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
l=[]
v=['']*w
h_n=[0]*h
v_n=[0]*w
n=0
ans=0
for i in range(h):
    s=input()
    scnt=s.count('#')
    n+=scnt
    h_n[i]+=scnt
    l.append(s)
    for j in range(w):
        v[j]+=s[j]
for i in range(w):
    v_n[i]+=v[i].count('#')


for i in range(2**h):
    for j in range(2**w):
        i_bin=bin(i)[2:]
        i_bin='0'*(h-len(i_bin))+i_bin
        j_bin=bin(j)[2:]
        j_bin='0'*(w-len(j_bin))+j_bin
        h_ind=[]
        w_ind=[]
        for ii in range(len(i_bin)):
            if i_bin[ii]=='1':
                h_ind.append(ii)
        for jj in range(len(j_bin)):
            if j_bin[jj]=='1':
                w_ind.append(jj)
        nn=0
        for kk in h_ind:
            nn+=h_n[kk]
            for ll in w_ind:
                if l[kk][ll]=='#':
                    nn-=1
        for ll in w_ind:
            nn+=v_n[ll]
        if n-nn==k:
            ans+=1
print(ans)

Submission status: Accepted

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

c = [[] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if C[i][j] == ".":
            c[i].append(0)
        elif C[i][j] == "#":
            c[i].append(1)


sw = []
for i in range(H):
    sw.append(sum(c[i]))

sh = []
for i in range(W):
    s = 0
    for j in range(H):
        s += c[j][i]
    sh.append(s)

S = sum(sw)
ans = 0

for i in range(2 ** H):
    Y = []
    ds = 0
    for h in range(H):
        if (i >> h) & 1:
            ds += sw[h]
            Y.append(h)

    for j in range(2 ** W):
        s = S - ds
        X = []
        for w in range(W):
            if (j >> w) & 1:
                s -= sh[w]
                X.append(w)
        
        for y in Y:
            for x in X:
                s += c[y][x]
        
        if s == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(H, W, K, Cxx):
    ans = 0
    for i in range(2 ** H):
        for j in range(2 ** W):
            cnt = 0
            for h in range(H):
                if i >> h & 1 == 1:
                    continue
                for w in range(W):
                    if j >> w & 1 == 1:
                        continue
                    if Cxx[h][w] == '#':
                        cnt += 1
            if cnt == K:
                ans += 1
    print(ans)



if __name__ == '__main__':
    # S = input()
    # N = int(input())
    H, W, K = map(int, input().split())
    Cxx = [input() for _ in range(H)]
    # As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]
    solve(H, W, K, Cxx)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W, K = map(int, readline().split())
C = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W]

C = 1 * (C == b'#')

def f(C, x, y):
    rows = [i for i in range(H) if x & (1<<i)]
    cols = [i for i in range(W) if y & (1<<i)]
    D = C[rows][:,cols]
    return D.sum() == K

ans = 0
for x in range(1 << H):
    for y in range(1 << W):
        ans += f(C, x, y)
print(ans)

Submission status: Accepted

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

import sys
import itertools
from copy import deepcopy

def input():
    return sys.stdin.readline()

def count_black(combi, field, h, w):

    height_list = []
    width_list = []
    for num in combi:
        if num <= h:
            height_list.append(num)
        else:
            width_list.append(num-(h))

    #print(height_list)
    #print(width_list)

    for line in height_list:
        for i in range(w):
            field[line-1][i] = "x"

    for row in width_list:
        for i in range(h):
            field[i][row-1] = "x"

    black_cnt = 0
    for line in field:
        black_cnt += line.count("#")

    return black_cnt





def resolve():
    h, w, k = map(int, input().split())
    field = [list(input().rstrip()) for i in range(h)]
    # field[y][x]

    lst = []

    for i in range(1, h+1):
        lst.append(i)

    lst_length = len(lst)
    for j in range(1, w+1):
        lst.append(lst_length+j)


    # 全列挙
    p = []
    for i in range(len(lst)):
        p.append(itertools.combinations(lst, i+1))

    ans_num = 0

    for v in p:
        for vv in v:
            temp_field = deepcopy(field)
            black_num = count_black(vv, temp_field, h, w)
            if black_num == k:
                ans_num += 1

    # 最後にまったく修正しない場合
    black_cnt = 0
    for line in field:
        black_cnt += line.count("#")

    if black_cnt == k:
        ans_num += 1

    print(ans_num)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from itertools import product
from copy import copy


def count(f):
    ret = 0
    for h in f:
        for w in h:
            if w == '#':
                ret += 1

    return ret


(h, w, k) = [int(s) for s in input().split()]

f = []

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

tmp = [range(2)] * h
bit_h = list(product(*tmp))

tmp = [range(2)] * w
bit_w = list(product(*tmp))

ans = 0

for bh in bit_h:
    for bw in bit_w:
        d = []

        for i, hh in enumerate(bh):
            if hh == 1:
                d.append(['-'] * w)
            else:
                d.append(copy(f[i]))

        for i, ww in enumerate(bw):
            if ww == 1:
                for dd in d:
                    dd[i] = '-'

        if count(d) == k:
            ans += 1


print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

def s2n(s):
    if s=='#':
        return 1
    else:
        return 0

c = []

for i in range(H):
    c.append(list(map(s2n,list(input()))))
    # c.append(list(input()))

# mp = np.array(c)
ans = 0

def fill(mp,num,iscolumn):
    if iscolumn==0:
        mp[num]=0
    else:
        mp[:,num-H]=0
    return mp

for i in range(2**(H+W)):
    mp = np.array(c)
    for j in range(H+W):
        if((i>>j)&1):
            mp = fill(mp,j,j>=H)
    if np.sum(mp)==K:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
 
h, w, k = list(map(int, input().split(' ')))
c = []
for i in range(h):
    c.append(np.array(list(list(input()))))
 
c = np.array(c)
ans = 0
 
h_comb = [[]]
for i in range(h):
    h_comb.append([i])
    for j in range(i+1, h):
        h_comb.append([i, j])
        for l in range(j+1, h):
            h_comb.append([i, j, l])
            for m in range(l+1, h):
                h_comb.append([i, j, l, m])
                for n in range(m+1, h):
                    h_comb.append([i, j, l, m, n])
                    for o in range(n+1, h):
                        h_comb.append([i, j, l, m, n, o])
 
w_comb = [[]]
for i in range(w):
    w_comb.append([i])
    for j in range(i+1, w):
        w_comb.append([i, j])
        for l in range(j+1, w):
            w_comb.append([i, j, l])
            for m in range(l+1, w):
                w_comb.append([i, j, l, m])
                for n in range(m+1, w):
                    w_comb.append([i, j, l, m, n])
                    for o in range(n+1, w):
                        w_comb.append([i, j, l, m, n, o])
 
 
for h_indice in h_comb:
    for w_indice in w_comb:
        a = c.copy()
        if len(h_indice) != 0:
            for i in h_indice:
                a[i, :] = 'x'
        if len(w_indice) != 0:
            for i in w_indice:
                a[:, i] = 'x'
        cnt = np.count_nonzero(a=='#')
        if cnt == k:
            ans += 1
 
print(ans)

Submission status: Accepted

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

for i in range(h):
    l.append([x for x in input()])

ans=0
for i in range(2**h):
    row=bin(i)[2:]
    while len(row)<h:row='0'+row
    for j in range(2**w):
        col=bin(j)[2:]
        while len(col) < w: col = '0' + col

        s=0
        for x in range(h):
            for y in range(w):
                if l[x][y]=='#' and row[x]=='0' and col[y]=='0':
                    s+=1

        if s==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
from itertools import permutations
import numpy as np

h,w,k = map(int,input().split())
li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]

point = 0
c = np.array(li)

for i in range(2**h):
    for j in range(2**w):
        d = c.copy()
        count = 0
        for ii in range(h):
            if (i >> ii)&1:
                for iii in range(w):
                    d[ii][iii] = 0
        for jj in range(w):
            if (j >> jj)&1:
                for jjj in range(h):
                    d[jjj][jj] = 0
        d = d.flatten()
        if np.count_nonzero(d=="#") == k:
            point += 1

print(point)

Submission status: Accepted

Solution code:
import itertools
import copy
h, w, k = map(int, input().split())
ans = 0
yoko = []
for _ in range(h):
    c = input()
    yoko.append(c)
y = [int(i) for i in range(h)]
y_kouho = []
t = [int(i) for i in range(w)]
t_kouho = []
for i in range(h+1):
    yy = itertools.combinations(y, i)
    y_kouho.append(list(yy))
for i in range(w+1):
    tt = itertools.combinations(t, i)
    t_kouho.append(list(tt))
    
for y_k in y_kouho:
    if len(y_k) > 0:
        for yy_k in y_k:
            y_test = copy.copy(yoko)
            yy_k = list(yy_k)
            if len(yy_k) > 0:
                for yyy_k in yy_k:
                    y_test[yyy_k] = list('-'*w)

            tate = []
            for i in range(w):
                c = [s[i] for s in y_test]
                tate.append(c)


            for t_k in t_kouho:
                if len(t_k) > 0:
                    for tt_k in t_k:
                        t_test = copy.copy(tate)
                        sm = 0
                        tt_k = list(tt_k)
                        if len(tt_k) > 0:
                            for ttt_k in tt_k:
                                t_test[ttt_k] = list('-' * h)


                        for i in range(w):
                            sm += t_test[i].count('#')
                        if sm == k:
                            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools


def conv(l, n):
    a = [True]*n
    for i in l:
        a[i] = False
    return a

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

path = 0
H_array = range(H)
W_array = range(W)
for n_i in range(H+1):
    for n_j in range(W):
        for comb_i in itertools.combinations(H_array, n_i):
            for comb_j in itertools.combinations(W_array, n_j):
                black = np.count_nonzero(c[conv(comb_i, H)][:, conv(comb_j, W)] == '#')
                if black == K:
                    path += 1

print(path)