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:
# abc173_c.py
H,W,K = map(int,input().split())
glid = [[] for i in range(H)]
for i in range(H):
    glid[i]=list(input())
import itertools
status = [(0, 1) for _ in range(H)]
h_state = list(itertools.product(*status))
status = [(0, 1) for _ in range(W)]
w_state = list(itertools.product(*status))
ans = 0
for h_case in h_state:
    for w_case in w_state:
        nglid = [[False]*W for _ in range(H)]
        for hidx,h in enumerate(h_case):
            for widx,w in enumerate(w_case):
                if h!=1:
                    nglid[hidx][widx] = True
                if w!=1:
                    nglid[hidx][widx] = True
        black = 0

        cnt=0
        for i in range(H):
            for j in range(W):
                if glid[i][j]=="#" and not nglid[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())
grid = ""
for i in range(H):
    grid += input()

grid2 = []
for i in grid:
    if i == ".":
        grid2.append(1)
    else:
        grid2.append(0)
    
ans = 0
for i in range(2 ** (H+W)):
    X = np.array(grid2)
    X = X.reshape(H,W)
    pattern = []
    for j in range(H+W):
        if ((i >> j) & 1):
            pattern.append(j)
    
    h = []
    w = []
    
    for k in pattern:
        if k <= (H-1):
            h.append(k)
        else:
            k -= H
            w.append(k)
    X[h,:]=1
    X[:,w]=1
    if X.reshape(1,-1).tolist()[0].count(0) == K:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:

h,w,K = map(int, input().split())
G = [list(input()) for _ in range(h)]
count = 0
for i in range(2**h):
    for j in range(2**w):
        tmp = 0
        for k in range(h):
            for m in range(w):
                if (not i>>k&1) and (not j>>m&1) and G[k][m] == '#':
                    tmp +=1
        if tmp == K:
            count += 1
print(count)

Submission status: Accepted

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

newc = [[ 1 if ee == '#' else 0 for ee in e ] for e in c] #黒を1
#print(newc)
newc_t = list(map(list, zip(*newc)))

blackcnt = sum( [sum(i) for i in newc] )
need_del = blackcnt - k
#print(need_del)
cnt = 0

for hh in range(2 ** h):
  #print(list(format(hh,'0{}b'.format(h)) ))
  hh_del = list( map( int, list(format(hh,'0{}b'.format(h)) ) ))
  for ww in range(2 ** w):
    ww_del = list( map( int, list(format(ww,'0{}b'.format(w)) ) ))
    
    row_del_cnt = sum( [sum(row) for row,check in zip(newc,   hh_del) if check ==1] )
    col_del_cnt = sum( [sum(col) for col,check in zip(newc_t, ww_del) if check ==1] )
    
    #diagonal
    d_cnt = 0
    for ri,rc in enumerate(hh_del):
      for ci,cc in enumerate(ww_del):
        d_cnt += newc[ri][ci] * rc * cc
    
    if need_del == row_del_cnt + col_del_cnt - d_cnt:
      cnt += 1
      #print(hh,hh_del,ww, ww_del)
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:07:34 2020

@author: NEC-PCuser
"""
import copy

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

c = []
c_count = 0
for i in range(H):
    c_li = list(input())
    c_count += c_li.count("#")
    c.append(c_li)
N = H + W
ans = 0
for i in range(2 ** N):
    count = c_count
    c_tmp = copy.deepcopy(c)
    for j in range(N):
        if ( j <  W and (i >> j) & 1):
            for k in range(H):
                if (c_tmp[k][j] == "#"):
                    count -= 1
                c_tmp[k][j] = "!"
        elif ((i >> j) & 1):
            for k in range(W):
                if (c_tmp[j - W][k] == "#"):
                    count -= 1
    if count == K:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
h,w,k= map(int,input().split())
mat=[]
for i in range(h):
  mat.append(input())
    
ans = 0    
for i in range(2**(h+w)):
  num = 0
  t = i
  tmat = [list(jj) for jj in mat]
  
  for j in range(h):
    if j>0:
      t = t>>1
    if t&1:
      tmat[j]=list(["9"]*w)
      
  for j in range(w):
    t = t>>1
    if t&1:
      for p in range(h):
        tmat[p][j]="9"
      
  for hh in range(h):
    for ww in range(w):
      if tmat[hh][ww]=="#":
        num+=1
      if num>k:
        break
        
  if num==k:
    ans +=1
    
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import copy
from itertools import product


H, W, K = map(int, input().split())
B = np.array([list(input().rstrip()) for _ in range(H)], str)
ans = 0

for h, w in product(range(2 ** H), range(2 ** W)):
    C = copy.deepcopy(B)
    for i in range(H):
        b = h >> i & 1
        if b:
            C[i, :] = '.'

    for i in range(W):
        b = w >> i & 1
        if b:
            C[:, i] = '.'

    ans += np.sum(C == '#') == K

print(ans)

Submission status: Accepted

Solution code:
import copy
H,W,K=map(int,input().split())
C=[]
for _ in range(H):
    c=list(input())
    C.append(c)
U=copy.deepcopy(C)
a=2**H
b=2**W
ans=0
for i in range (a):
    C=copy.deepcopy(U)
    for j in range(H):
        if ((i>>j)&1):
            C[j]=['a']*W
    E=copy.deepcopy(C)
    for h in range(b):
        C=copy.deepcopy(E)
        for k in range(W):
            if ((h>>k)&1):
                for q in range(H):
                    C[q][k]='a'
        count=0
        for d in range(H):
            for e in range(W):
                if C[d][e]=='#':
                    count+=1
        if count==K:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
def main():
    h, w, k = list(map(int, input().split()))
    C = [list(input()) for _ in range(h)]
    Ch = []
    Cw = []
    for c in C:
        Ch.append(sum(i == '#' for i in c))
    C = [list(x) for x in zip(*C)]
    for c in C:
        Cw.append(sum(i == '#' for i in c))
    C = [list(x) for x in zip(*C)]
    tot = sum(Ch)
    ans = 0
    for i in range(h + 1):
        for j in range(w + 1):
            for ch in combinations(range(h), i):
                for cw in combinations(range(w), j):
                    ci = sum(Ch[ii] for ii in ch)
                    cj = sum(Cw[jj] for jj in cw)
                    dup = sum(C[ii][jj] == '#' for ii in ch for jj in cw)
                    if tot - (ci + cj - dup) == k:
                        ans += 1
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def powerset_generator(provided_set):
  if len(provided_set) > 0:
    for c in powerset_generator(provided_set[1:]):
      yield [provided_set[0]] + c
      yield c
  else:
    yield []

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

hw_list = ['h'+ str(i) for i in range(H)] + ['w'+ str(j) for j in range(W)]

res = 0
for red_list in powerset_generator(hw_list):
    red_h_list = []
    red_w_list = []
    for red in red_list:
        if red.startswith('h'):
            red_h_list.append(int(red[1:]))
        else:
            red_w_list.append(int(red[1:]))
    count = 0
    for i in range(H):
        if i in red_h_list:
            continue
        for j in range(W):
            if j in red_w_list:
                continue
            if masu[i][j] == '#':
                count += 1
    if K == count:
        res += 1

print(res)

Submission status: Accepted

Solution code:
from itertools import product
h,w,k = map(int,input().split())
c = [input() for _ in range(h)]
row = list(product(range(2), repeat=h))
col = list(product(range(2), repeat=w))
g = "#" * k
cl = []
for i in row:
  for j in col:
    s=""
    for k in range(h):
      for l in range(w):
        if i[k] != 0 and j[l] != 0:
          s += c[k][l]
    cl.append(s)

for i in range(len(cl)):
  cl[i] = cl[i].replace(".","")
  
print(cl.count(g))

Submission status: Accepted

Solution code:
h,w,K=map(int,input().split())
c=[input() for i in range(h)]
total=0
for i in range(h):
    for j in range(w):
        if c[i][j]=="#":
            total+=1
#print(total)
ans=0
l=[]
for bit in range(1<<h):
    bh=bin(bit)
    bh="0"*(h-len(bh[2:])) +bh[2:]
    gyo=[]
    for i in range(h):
        if bh[-i-1]=="1":
            gyo.append(i)
    for BIT in range(1<<w):
        bw=bin(BIT)
        bw="0"*(w-len(bw[2:]))+bw[2:]
        #print(bh,bw)
        cl=[]
        for j in range(w):
            if bw[-j-1]=="1":
                cl.append(j)
        #print(gyo,cl,bh,bw)
        #ここからようやく#の数数える
        su=0
        for r in range(h):
            if r in gyo:
                continue
            for k in range(w):
                if k in cl:
                    continue
                if c[r][k]=="#":
                    su+=1
        #print(su,gyo,cl,bh,bw)
        if su==K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations

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

grid = np.zeros([H,W],dtype=int)
for i in range(H):
  row = input().replace('.', '0').replace('#', '1')
  for j in range(W):
  	grid[i,j]=int(row[j])

grid2 = grid.copy()
count = 0
for i in range(-1, H):
  for j in range(-1, W):
    if i != -1 and j != -1:
      for p in combinations(range(H), i+1):
      	for q in combinations(range(W), j+1):
          grid2[p, :] = 0
          grid2[:, q] = 0
          if grid2.sum() == K: 
            count += 1
            #print(p, q)
          grid2 = grid.copy()
    
    elif i == -1 and j != -1:
      for q in combinations(range(W), j+1):
        grid2[:, q] = 0
        if grid2.sum() == K: 
          count += 1
          #print(q)
        grid2 = grid.copy()
    
    elif i != -1 and j == -1:
      for p in combinations(range(H), i+1):
        grid2[p, :] = 0
        if grid2.sum() == K:
          count += 1
          #print(p)
        grid2 = grid.copy()
    
    else:
      if grid2.sum() == K:
        count += 1
        #print(-1)
      grid2 = grid.copy()
          
print(count)

Submission status: Accepted

Solution code:
from copy import deepcopy
def bit_s(bit, n):
    l = []
    for i in range(n):
        if bit & (1 << i):
            l.append(i)
    return l
h, w, k = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = 0
c2 = deepcopy(c)
for bit in range(1 << h):
    l = bit_s(bit, h)
    for i in l[::-1]:
        del c2[i]
    for bit2 in range(1 << w):
        cnt = 0
        l2 = bit_s(bit2, w)
        for i in c2:
            for j in l2:
                if i[j] == "#":
                    cnt += 1
        if cnt == k:
            ans += 1
    c2 = deepcopy(c)
print(ans)

Submission status: Accepted

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

def count(A):
    ret = 0
    for r in A:
        ret += r.count("#")
    return ret
ans = 0

for bit in range(1<<(h+w)):
    tmp = copy.deepcopy(c)
    for j in range(h+w):
        if (bit&(1<<j)):
            # print(j)
            # 行方向
            if j < h:
                for k in range(w):
                    tmp[j][k] = "a"
            # 列方向
            else:
                for k in range(h):
                    tmp[k][j-h] = "a"
    x = count(tmp)
    if count(tmp) == 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 i in range(2**(H+W)):
    list = [[0 for _ in range(W)] for _ in range(H)]
    for j in range(H+W):
        if (i >> j) % 2 == 0:
            if j < H:
                for k in range(W):
                    list[j][k] += 1 #j行目に全部プラス1する
            else:
                for k in range(H):
                    list[k][H-j] += 1 #H-j列目に全部プラス1する
    count_k = 0
    for h in range(H):
        for w in range(W):
            if list[h][w] == 0 and c[h][w] == "#":
                count_k += 1
    if count_k == K:
        ans += 1

print(ans)

Submission status: Accepted

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

def iter_p_adic(p, n):
    '''
    連続して増加するp進数をリストとして返す。nはリストの長さ
    return
    ----------
    所望のp進数リストを次々返してくれるiterator
    '''
    from itertools import product
    tmp = [range(p)] * n
    return product(*tmp)

h_iter = list(iter_p_adic(2, h))
w_iter = list(iter_p_adic(2, w))

count = 0
for h_iter_i in range(len(h_iter)):
    for w_iter_i in range(len(w_iter)):
        count_tmp = 0
        for h_i in range(len(c_list)):
            for w_i in range(len(c_list[h_i])):
#                 if c_list[h_i][w_i] == '#':
                if c_list[h_i][w_i] == '#' and h_iter[h_iter_i][h_i] == 0 and w_iter[w_iter_i][w_i] == 0:
                    count_tmp += 1
        if count_tmp == k:
            count += 1

print(count)

Submission status: Accepted

Solution code:
import numpy as np

h, w, k = map(int, input().split())
c = np.array([list(input()) for _ in range(h)])
ans = 0
for i in range(2 ** (h+w)):
    cnt = 0
    c_ = c.copy()
    #print(bin(i))
    for j in range(h+w):
        if i >> j & 1:
            if j < h:
                c_[j] = 'x'
            else:
                c_.T[j-h] = 'x'
    for y in range(h):
        for x in range(w):
            if c_[y][x] == '#':
                cnt += 1
    if cnt == k:
        ans += 1
print(ans)

Submission status: Accepted

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


# 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():
    H, W, K = map(int, input().split())
    field = []
    row = [0] * H
    column = [0] * W
    total = 0
    for _ in range(H):
        field.append(input())
    
    for r in range(H):
        for c in range(W):
            if field[r][c] == "#":
                row[r] += 1
                column[c] += 1
                total += 1

    count = 0
    for r in range(2 ** H):
        for c in range(2 ** W):
            dub = []
            delete = 0
            overdelete = 0
            for i in range(H):
                if r >> i & 1:
                    dub.append(field[i])
                    delete += row[i]
            for i in range(W):
                if c >> i & 1:
                    delete += column[i]
                    for d in dub:
                        if d[i] == "#":
                            overdelete += 1
            
            if total - delete + overdelete == K:
                #print(r, c, total, delete, overdelete)
                count += 1

    print(count)

    return 

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
H, W, K = map(int, input().split())
c = []
r = [0]* W
S = [input() for _ in range(H)]
for i in range(H):
    c.append(S[i].count('#'))
for i in range(W):
    for j in range(H):
        if S[j][i] == '#': r[i] += 1

nall = sum(c)
ans = 0
for hh in product([0, 1], repeat=H):
    for ww in product([0, 1], repeat=W):
        dl = 0
        for ih, ihh in enumerate(hh):
            dl += c[ih] * ihh
            for iw, iww in enumerate(ww):
                if S[ih][iw] == '#':
                    dl -= ihh * iww
        for iw, iww in enumerate(ww):
            dl += r[iw] * iww
        
        if nall - dl == K: ans += 1
print(ans)

Submission status: Accepted

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

import copy
import itertools
c_copy = copy.deepcopy(c)

tate_options = list(itertools.product([0,1],repeat=W))
yoko_options = list(itertools.product([0,1],repeat=H))

answer = 0
for tate_option in tate_options:
    for yoko_option in yoko_options:
        count = 0
        for i in range(W):
            if tate_option[i] == 1:
                continue
            for j in range(H):
                if yoko_option[j]==1:
                    continue

                if c[j][i] == "#":
                    count += 1
        if count == K:
            answer += 1
print(answer)

Submission status: Accepted

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

from itertools import permutations, product
from copy import deepcopy

res = 0

for u in product([0, 1], repeat=h): # よこ
    for v in product([0, 1], repeat=w): # たて
        tmp = deepcopy(c)
        for i in range(h):
            if u[i] == 0:
                for j in range(w):
                    if tmp[i][j] == '#':
                        tmp[i] = '.' * w
        for i in range(w):
            if v[i] == 0:
                for j in range(h):
                    if tmp[j][i] == '#':
                        tmp[j][i] = '.'
        # count
        cnt = 0
        for j in range(h):
            for i in range(w):
                if tmp[j][i] == '#':
                    cnt += 1
        if cnt == k:
            res += 1

print(res)

Submission status: Accepted

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

# import numpy as np

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


H, W, K = MI()
c = [list(S()) for _ in range(H)]
# c = np.array(sys.stdin.read().split())
# c = sys.stdin.read().split()

ans = 0
for h in range(1 << H):
    for w in range(1 << W):
        count = 0
        for j in range(H):
            for i in range(W):
                if not ((h >> j) & 1) and not ((w >> i) & 1) and c[j][i] == "#":
                    count += 1
        if count == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

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

ans = 0
for i in itertools.product(range(2), repeat=(H+W)):
    G = copy.deepcopy(Graph)
    for j in range(H+W):
        if 0 <= j < H:
            if i[j] == 1:
                G[j] = ["r"]*W
        else:
            if i[j] == 1:
                for h in range(H):
                    G[h][j-H-1] = "r"
                    
    cnt = 0
    for h in range(H):
        for w in range(W):
            if G[h][w] == "#":
                cnt += 1
                
    if cnt == K:
        ans += 1 

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

import itertools

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

field = [list(f) for f in field]

black_h = {}
black_w = {}
black_i = {}

tot = 0

for ih in range(h):
    for iw in range(w):
        black_h[ih] = 0
        black_w[iw] = 0
        black_i[(ih,iw)] = 0

for ih in range(h):
    for iw in range(w):
        if field[ih][iw] == '#':
            black_h[ih] += 1
            black_w[iw] += 1
            black_i[(ih,iw)] += 1
            tot += 1
            
#print(black_h)
#print(black_w)
#print(black_i)
#print(tot)

ans = 0

for n_comb_h in range(h+1):
    for v_h in itertools.combinations([i for i in range(h)],n_comb_h):
        for n_comb_w in range(w+1):
            for v_w in itertools.combinations([i for i in range(w)],n_comb_w):
                tmp = 0
                for i_h in v_h:
                    tmp += black_h[i_h]
                for i_w in v_w:
                    tmp += black_w[i_w]
                for i_h in v_h:
                    for i_w in v_w:
                        if black_i[(i_h, i_w)] == 1:
                            tmp -= 1
                if tmp == tot-k:
                    ans += 1
                    
print(ans)

Submission status: Accepted

Solution code:
def change_and_check(arr,rowarr,colarr,k):
	#l=arr[:][:]
	for i in range(len(rowarr)):
		ele=rowarr[i]
		for j in range(len(arr[0])):
			arr[ele][j]="r" 
	for i in range(len(colarr)):
		ele=colarr[i]
		for j in range(len(arr)):
			arr[j][ele]="r" 
	#print(arr)
	return count(arr)==k  
def count(arr):
	c=0 
	for i in range(len(arr)):
		for j in range(len(arr[0])):
			if arr[i][j]=="#":
				c+=1 
	return c
import itertools 
from copy import copy, deepcopy
frow=[] 
fcol=[] 
h,w,k=map(int,input().split()) 
a=[] 
f=list(range(h))
g=list(range(w))
for i in range(h):
	n=input()
	a.append(list(n))
for kk in range(h+1):
	l=list(map(list,itertools.combinations(f,kk)))
	frow+=l
for kk in range(w+1):
	l=list(map(list,itertools.combinations(g,kk)))
	fcol+=l 
#print(frow,fcol)
arr=deepcopy(a)
#print(arr)
cc=0 
#print(k)
for x in frow:
	for y in fcol:
		#print(a)
		if change_and_check(a,x,y,k):
			cc+=1 
		a=deepcopy(arr)
print(cc)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from itertools import product
import copy

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

def count(S):
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                ans += 1
    return ans

A = list(product([True,False],repeat=H))
B = list(product([True,False],repeat=W))

num = 0
for a in A:
    for b in B:
        S = copy.deepcopy(c)
        for i in range(H):
            if a[i]:
                for j in range(W):
                    S[i][j] = '?'
        for j in range(W):
            if b[j]:
                for i in range(H):
                    S[i][j] = '?'
        co = count(S)
        if co == K:
            num += 1

print(num)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[[0]*w for i in range(h)]
d=[[0]*w for i in range(h)]
ans=0
for i in range(h):
    a=input()
    for j in range(w):
        c[i][j]=a[j]
for i in range(2**(h+w)):
    for m in range(h):
        for n in range(w):
            d[m][n]=c[m][n]
    for j in range(h):
        if (i >> j)&1:
            for x in range(w):
                d[j][x]="r"
    for j in range(h,w+h):
        if (i >> j)&1:
            for x in range(h):
                d[x][j-h]="r"
    f=0
    for q in range(h):
        for s in range(w):
            if d[q][s]=="#":
                f+=1
            
        
    if f==k:
        ans+=1
print(ans)

Submission status: Accepted

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

def red():
    res = 0
    for i in range(h):
        for j in range(w):
            if field[i][j] == '#':
                res += 1
    return res

cnt = 0
for s in range(2 ** h):
    for t in range(2 ** w):

        for i in range(h):
            for j in range(w):
                if ((s >> i) & 1):
                    for x in range(w):
                        if field[i][x] == '#':
                            field[i][x] = 'r'
                if ((t >> j) & 1):
                    for x in range(h):
                        if field[x][j] == '#':
                            field[x][j] = 'r'
        if red() == k:
            cnt += 1
        for x in range(h):
            for y in range(w):
                if field[x][y] == 'r':
                    field[x][y] = '#'

print(cnt)

Submission status: Accepted

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


def black(G):
    tmp = 0
    for hh in range(h):
        for ww in range(w):
            if G[hh][ww] == "#":
                tmp += 1
    return tmp


def main():
    ans = 0
    for i in range(2**h):
        tmp = i
        T = deepcopy(C)
        for hh in range(h):
            if tmp % 2 == 1:
                tmp = tmp // 2
                continue
            tmp = tmp // 2
            for ww in range(w):
                T[hh][ww] = "r"
        for j in range(2**w):
            U = deepcopy(T)
            tmp2 = j
            for ww in range(w):
                if tmp2 % 2 == 1:
                    tmp2 = tmp2 // 2
                    continue
                tmp2 = tmp2 // 2
                for hh in range(h):
                    U[hh][ww] = "r"
            if black(U) == k:
                ans += 1
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
H,W,K=map(int,input().split())
c=[]
ANS=0
for i in range(H):
    c.append(list(input()))
for i in range(2**H):
    for j in range(2**W):
        C=copy.copy(c)
        ans=0
        for k in range(H):
            if (i>>k)&1==1:
                C[k]=['.' for i in range(W)]
        for l in range(W):
            if (j>>l)&1==1:
                C=list(zip(*C))
                C[l]=['.' for i in range(H)]
                C=list(zip(*C))
        for s in C:
            for a in s:
                if a=='#':
                    ans+=1
        if ans==K:
            ANS+=1
print(ANS)

Submission status: Accepted

Solution code:
import copy

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

C=list()
Cd=list()
for h in range(H):
    S = input()
    C.append(S)

    r=list()
    for w in range(W):
        if S[w] == '.':
            d=0
        else:
            d=1
        r.append(d)
    Cd.append(list(r))

ans=0

def check_bits(i,width):
    c = list()
    for w in range(width):
        c.append(1 & (i>>w))
    return c

ans=0
for h in range(2**H):
    check = copy.deepcopy(Cd)

    hsel = check_bits(h,H)
    # print(h, hsel)

    for i in range(H):
        if hsel[i]==1:
            check[i]=[0] * W

    # print("h=",h,"check=",check)
    for w in range(2**W):
        check_w = copy.deepcopy(check)

        wsel = check_bits(w,W)
        # print(w, wsel)

        for j in range(W):
            if wsel[j] == 1:
                for i in range(H):
                    check_w[i][j] = 0
        
        calc = 0
        for i in range(H):
            calc += sum(check_w[i])
        # print(hsel, wsel, calc)
        if calc == K:
            ans += 1
print(ans)

Submission status: Accepted

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

hw = []
for i in range(H):
    w = list(input())
    hw.append(w)


def check(h_ok, w_ok):
    sum = 0
    for h in range(H):
        for w in range(W):
            if h_ok[h] == 0 and w_ok[w] == 0 and hw[h][w] == "#":
                sum+=1
    return sum == K


result = 0

for h1 in [0, 1]:
    for h2 in [0, 1]:
        for h3 in [0, 1]:
            for h4 in [0, 1]:
                for h5 in [0, 1]:
                    for h6 in [0, 1]:
                        for w1 in [0, 1]:
                            for w2 in [0, 1]:
                                for w3 in [0, 1]:
                                    for w4 in [0, 1]:
                                        for w5 in [0, 1]:
                                            for w6 in [0, 1]:
                                                h_ok = {}
                                                w_ok = {}
                                                h_ok[0] = h1
                                                h_ok[1] = h2
                                                h_ok[2] = h3
                                                h_ok[3] = h4
                                                h_ok[4] = h5
                                                h_ok[5] = h6
                                                w_ok[0] = w1
                                                w_ok[1] = w2
                                                w_ok[2] = w3
                                                w_ok[3] = w4
                                                w_ok[4] = w5
                                                w_ok[5] = w6
                                                if check(h_ok, w_ok):
                                                    result+=1
for h in range(6-H+6-W):
    result /= 2

print(int(result))

Submission status: Accepted

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

h1 = [list(f"{i:0{h}b}") for i in range(2**h)]
w1 = [list(f"{i:0{w}b}") for i in range(2**w)]

cnt = 0
for hh in h1:
    for ww in w1:
        black = 0
        x = [i for i in range(h) if hh[i]=='1']
        y = [i for i in range(w) if ww[i]=='1']
        for i in x:
            for j in y:
                if c[i][j] == '#':
                    black += 1
        if black == k:
            cnt += 1
            #print(x, y)

print(cnt)

Submission status: Accepted

Solution code:
from itertools import combinations
from copy import deepcopy
H, W, K = map(int, input().split())
field = [[c for c in input()] for i in range(H)]

def hmblack(field):
    count = 0
    for l in field:
        for c in l:
            if c == '#':
                count += 1
    return count

result = 0

for i in range(H+1):
    dline = combinations(range(H), i)
    for cl in dline:
        for j in range(W+1):
            draw = combinations(range(W), j)
            for cr in draw:
                cpf = deepcopy(field)
                for y in range(H):
                    for x in range(W):
                        if y in cl or x in cr:
                            cpf[y][x] = 'r'
                if hmblack(cpf) == K:
                    result += 1
print(result)