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:
H,W,K=map(int,input().split())
S=[input() for _ in range(H)]

ans=0
for h in range(2**H): 
    for w in range(2**W):
        cnt=0
        for i in range(H):
            for j in range(W):
                if (h>>i&1): continue
                if (w>>j&1): continue
                if S[i][j]=="#": cnt+=1
        if cnt==K:ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
H,W,K=map(int,input().split())
C=[input() for i in range(H)]
ans=0
for paint_H in itertools.product([0,1], repeat=H):
  for paint_W in itertools.product([0,1], repeat=W):
    cnt=0
    for i in range(H):
      for j in range(W):
        if paint_H[i]==0 and paint_W[j]==0 and C[i][j]=="#":
          cnt+=1
    if cnt==K:
      ans+=1
print(ans)

Submission status: Accepted

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

box, ans = [], 0

for i in range(h):
    box.append(input())


for i in range(1 << h):
    for j in range(1 << w):
        count = 0
    
        for H in range(h):
            if i >> H & 1:
                continue
            
            for W in range(w):
                if j >> W & 1:
                    continue
                
                if box[H][W] == '#':
                    count += 1
            
        if count == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
H,W,K=map(int,input().split())
C=[input() for i in range(H)]
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(C[a][b]=="#"):count+=1
        if(count == K):
          ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools as it
n,m,k=list(map(int,input().split()))
S=[list(str(input())) for h in range(n)]
ans=0
for i in it.product([0,1],repeat=n):
  for j in it.product(range(2),repeat=m):
    count=0
    for h in range(n):
      for c in range(m):
        if S[h][c]=="#" and i[h]+j[c]==0:
          count+=1
    if count==k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
input=sys.stdin.readline
##import numpy as np
#sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo
##
##for _ in range(inin()):
r,c,k=cin()
dc=dd(int)
dr=dd(int)
mat=[]
for i in range(r):
    s=sin().strip()
    dr[i]=s.count('#')
    mat.append(list(s))
total=sum(list(dr.values()))
for i in range(c):
    co=0
    for j in range(r):
        if(mat[j][i]=='#'):
            co+=1
    dc[i]=co
ans=0
lr=lr=[o for o in range(r)]
lc=[o for o in range(c)]
for i in range(0,r+1):
    sur=0
    
##    print("LR==",lr)
    rowp=list(itertools.combinations(lr,i))
##    print("ROWPER==",rowp)
##    print(len(rowp))
    for perrow in rowp:
        sur=0
        for indexr in perrow:
            sur+=dr[indexr]
        for j in range(0,c+1):
            suc=0
            colp=list(itertools.combinations(lc,j))
            for percol in colp:
                suc=0
                for indexc in percol:
                    co=0
                    for ro in range(r):
                        if(mat[ro][indexc]=='#' and (ro not in perrow)):
                            co+=1
                    suc+=co
                if(total-sur-suc==k):
##                    print("No of ro=",i,"SUMR",sur,"ROWPERM=",perrow,"   ","NO OF COL",j,"SUMC",suc,"COLPERM",percol)
                    ans+=1
                        
                    
print(ans)
    
        
    

        


    


    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
        
        
    
    
    
    


    





##
        
    
    
    
    
    
    
        
        
    
    
    
    


    





##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far

Submission status: Accepted

Solution code:

from itertools import combinations

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

for i in range(H):
	C.append(input())#C[i-1][j-1]でi行j列指定できる。

count = 0
Count = 0


#行、列いずれも1~H-1,W-1個選ぶ。
for k in range(1,H):
	for l in range(1,W):
		for i in combinations(list(range(1,H+1)),k):
			for j in combinations(list(range(1,W+1)),l):		
				count = 0
				for m in range(1,H+1):
					for n in range(1,W+1):
						if not(m in i) and not(n in j) and C[m-1][n-1] == '#':
							count += 1
				if K == count:
					Count += 1

#行のみ選ぶ、
for k in range(1,H):
	for i in combinations(list(range(1,H+1)),k):
		count =0
		for m in range(1,H+1):
			for n in range(1,W+1):
				if not(m in i) and C[m-1][n-1] == '#':
					count += 1
		if K == count:
			Count += 1

#列のみ選ぶ。
for l in range(1,W):
	for j in combinations(list(range(1,W+1)),l):
		count = 0
		for m in range(1,H+1):
			for n in range(1,W+1):
				if not(n in j) and C[m-1][n-1] == '#':
					count += 1
		if K == count:
			Count += 1


#一つも選ばない
count = 0 
for m in range(1,H+1):
	for n in range(1,W+1):
		if C[m-1][n-1] == '#':
			count += 1
if K == count:
	Count += 1





print(Count)

Submission status: Accepted

Solution code:
def main():
    h,w,k = map(int,input().split())
    maze = [['.' for j in range(6)] for i in range(6)]


    for i in range(h):
        line = list(input())
        for j in range(w):
            maze[i][j] = line[j]
    
    # print(maze)

    ver = [0 for i in range(6)]
    hor = [0 for i in range(6)]
    horver = [[0 for i in range(6)] for j in range(6)]
    total = 0
    for i in range(6):
        for j in range(6):
            if maze[i][j] == '#':
                ver[j] += 1
                hor[i] += 1
                horver[i][j] = 1
                total += 1
    # print(ver,hor,horver)

    ans = 0
    for bit in range(2**(h+w)):
        tmp = total
        valid_hor = []
        for i in range(h):
            if (bit >> i & 1) == 1:
                valid_hor.append(i)
                tmp -= hor[i] 
        
        for j in range(h,h+w):
            if (bit >> j & 1) == 1:
                tmp -= ver[j-h]
                for i in valid_hor:
                    tmp += horver[i][j-h]
    
        if tmp == k:
            ans += 1

    print(ans)
    return 

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0

for row_bit in product(range(2), repeat=h):
    for col_bit in product(range(2), repeat=w):
        cnt = 0
        for row in range(h):
            for col in range(w):
                if c[row][col] == "#" and (row_bit[row] and col_bit[col]):
                    cnt += 1
        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(list(input()))

counter_pattern = 0
for i in range(2 ** H):# 000~111
    for j in range(2 ** W):# 000~111
        counter_black = 0
        for h in range(H):
            for w in range(W):
                if L[h][w] == "#" and ((i >> h) & 1) == 0 and ((j >> w) & 1) == 0:
                    counter_black += 1
        if counter_black == K:
            counter_pattern += 1

print(counter_pattern)

Submission status: Accepted

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

for i in range(1<<h+w):
  x=0
  for j in range(h):
    for l in range(w):
      if i>>j & 1 and i>>l+h & 1:
        if c[j][l]=="#":
          x+=1
  if x==k:
    a+=1
print(a)

Submission status: Accepted

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

ans = 0

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

print(ans)

Submission status: Accepted

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

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

for paint_h in range(2**H):
	for paint_w in range(2**W):
		cnt=0
		for i in range(H):
			for j in range(W):
				if (paint_h>>i)&1==0 and (paint_w>>j)&1==0:
					if arr[i][j]=="#":
						cnt+=1

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

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[input() for i in range(h)]
ans=0
for a in range(1<<h):
    for b in range(1<<w):
        cnt=0
        for i in range(h):
            if a>>i&1:
                continue
            for j in range(w):
                if b>>j&1:
                    continue
                cnt+=c[i][j]=='#'
        ans+=cnt==k
print(ans)

Submission status: Accepted

Solution code:
h,w,p=map(int,input().split())
A=[]
ans=0

for i in range(h):
    A.append(list(input()))

for i in range(2**h):
    hs=[False]*h
    for j in range(h):
        if ((i>>j)&1):
            hs[j]=True
    for k in range(2**w):
        ws=[False]*w
        for l in range(w):
            if ((k>>l)&1):
                ws[l]=True
        cnt=0
        for a in range(h):
            if hs[a]==True:
                for b in range(w):
                    if ws[b]==True:
                        if A[a][b]=='#':
                            cnt+=1
        if cnt==p:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools as it

H,W,N = [int(i) for i in input().split()]
dat = np.array([list(input()) for i in range(H)], dtype=str)


emp_r = ["." for i in range(W)]
emp_c = ["." for i in range(H)]


def plot(dat, dict):
    for y in dict["row"]:
        dat[y,:] = emp_r
    for x in dict["col"]:
        dat[:,x] = emp_c
    return dat


def is_sat(dat):
    count = 0
    for y in range(W):
        for x in range(H):
            if dat[x, y] == "#":
                count += 1

    if count == N:
        return True
    else:
        return False

# def get_one_idx(bi, digit_num):
#     tmp = []
#     for j in range(digit_num):
#         if (bi >> j) == 1:
#             tmp.append()



# plot(dat, dict={"row": [], "col":[0, 1]})
combs = it.product([bin(i) for i in range(2**H-1)], [bin(i) for i in range(2**W-1)])
count = 0
for comb in combs:
    rows = comb[0]
    cols = comb[1]
    rc_dict = {"row": [], "col": []}
    for j in range(H):
        if (int(rows, 0) >> j) & 1 == 1:
            rc_dict["row"].append(j)

    for j in range(W):
        if (int(cols, 0) >> j) & 1 == 1:
            rc_dict["col"].append(j)

    dat_c = plot(dat.copy(), rc_dict)
    if is_sat(dat_c):
        count += 1

print(count)

Submission status: Accepted

Solution code:

H, W, K = map(int, input().split(' '))
ls, rst = [], 0
for i in range(H):
    ls.append(input())
for i in range(1 << H):
    for j in range(1 << W):
        cnt = 0
        for s in range(H):
            if i >> s & 1:
                continue
            for t in range(W):
                if j >> t & 1:
                    continue
                if ls[s][t] == '#':
                    cnt += 1
        if cnt == K:
            rst += 1
print(rst)

Submission status: Accepted

Solution code:
import numpy as np

H,W,K = list(map(int, input().split()))
t=[]
for i in range(H):
    t.append([int(i) for i in input().replace(".","0").replace("#","1")])

cnt = 0
for i in range(2**H):
    for j in range(2**W):
        d = np.array(t)
        i_2 = [int(k) for k in bin(i)[2:].rjust(H,"0")]
        j_2 = [ int(k) for k in bin(j)[2:].rjust(W,"0")]
        #print(i_2)
        #print(j_2)
        
        d= ((d.T)*i_2).T
        d= d*j_2
        
        num = d.sum()
        if num == K:
            cnt +=1
            
print(cnt)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split(' '))
ls, result = [], 0
for i in range(H):
    ls.append(input())

for i in range(1 << H):
    for j in range(1 << W):
        cnt = 0
        for s in range(H):
            if i >> s & 1:
                continue
            for t in range(W):
                if j >> t & 1:
                    continue
                if ls[s][t] == '#':
                    cnt += 1
        if cnt == K:
            result += 1
print(result)

Submission status: Accepted

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

for h_p in range(2 ** H):
    for w_p in range(2 ** W):
        count = 0
        for h in range(H):
            for w in range(W):
                if (h_p >> h) & 1 == 0 and (w_p >> w) & 1 == 0:
                    if (L[h][w] == '#'):
                        count += 1
        if count == K:
            ans += 1

print(ans)

Submission status: Accepted

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

def main():
    H,W,K = list(map(int, sys.stdin.readline().split()))
    C_list = [list( sys.stdin.readline().rstrip() ) for _ in range(H)]

    bit_H = 1 << H
    bit_W = 1 << W
    cnt_K = 0

    for b_H in range(bit_H):
        for b_W in range(bit_W):
            cnt_black = 0

            for row in range(H):
                for col in range(W):
                    if (C_list[row][col] == "#") and ( b_H & (1 << row) ) and ( b_W & (1 << col) ):
                        cnt_black += 1
            
            if cnt_black == K:
                cnt_K += 1
    
    print(cnt_K)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
lis = []
for _ in range(H):
    A = list(input())
    lis.append(A)
    
ans = 0
for paint_h in range(2**H):
    for paint_w in range(2**W):
       cnt=0
       for i in range(H):
           for j in range(W):
               if (paint_h >> i)&1 ==0 and (paint_w >> j)&1 ==0:
                   if lis[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 = list(list(input()) for i in range(h))
c = np.array(c)
ans = 0
for i in range(2**h):
    for j in range(2**w):
        x = i
        y = j
        s = np.copy(c)
        n = 0
        while x > 0:
            if x % 2 == 1:
                for l in range(w):
                    s[n][l] = '0'
            x = x // 2
            n += 1
        m = 0
        while y > 0:
            if y % 2 == 1:
                for l in range(h):
                    s[l][m] = '0'
            y = y // 2
            m += 1
        p = np.count_nonzero(s == '#')
        if p == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
C=[input() for _ in range(H)]
ans=0
for i in range(2**H):
  for j in range(2**W):
    c=0
    for ii in range(H):
      for jj in range(W):
        if 1&(i>>ii)&(j>>jj):
          if C[ii][jj]=='#':
            c+=1
    if c==K:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
C=[input() for _ in range(H)]
ans=0
for i in range(2**H):
  for j in range(2**W):
    c=0
    for ii in range(H):
      for jj in range(W):
        if (i>>ii)&(j>>jj)&1:
          if C[ii][jj]=='#':
            c+=1
    if c==K:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
C=[input() for _ in range(H)]
ans=0
for i in range(2**H):
  for j in range(2**W):
    c=0
    for ii in range(H):
      for jj in range(W):
        if i>>ii&1 and j>>jj&1:
          if C[ii][jj]=='#':
            c+=1
    if c==K:
      ans+=1
print(ans)

Submission status: Accepted

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

for bh in range(1 << h):
    for bw in range(1 << w):
        B = 0
        for H in range(h):
            for W in range(w):
                if ((bh >> H) & 1) == 0 and ((bw >> W) & 1) == 0 and m[H][W] == "#":
                    B += 1
        if B == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
C = [[(c=="#") for c in input()] for _ in range(H)]
cnt0 = sum(sum(c) for c in C)
ans = 0
for sy in range(1<<H):
    for sx in range(1<<W):
        D = [c.copy() for c in C]
        cnt = cnt0
        for y in range(H):
            for x in range(W):
                if sy>>y&1 | sx>>x&1:
                    cnt -= D[y][x]
                    D[y][x] = False
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split(' '))
ls,result = [], 0

for i in range(H):
    ls.append(input())

for i in range(1 << H):
    for j in range(1 << W):
        cnt = 0
        for s in range(H):
            if i >> s & 1:
                continue
            for t in range(W):
                if j >> t & 1:
                    continue
                if ls[s][t] == '#':
                    cnt += 1
        if cnt == K:
            result += 1
print(result)

Submission status: Accepted

Solution code:
import itertools

# -*- coding: utf-8 -*-
# 整数の入力
H, W, K = map(int, input().split())
# 文字列の入力
masu_list = []
for i in range(H):
    str = input()
    masu_list.append(list(str))
ans = 0

for H_bit in range(1 << H):
    for W_bit in range(1 << W):
        break_i = 0
        cnt = 0
        for i in range(H):
            if break_i == 1:
                break
            for j in range(W):
                if (H_bit >> i) & 1 and (W_bit >> j) & 1:
                    if masu_list[i][j] == "#":
                        cnt += 1
                        if cnt > K:
                            break_i = 1
                            break
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product, chain

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

sum_num = 0

for y in range(1<<H):
    for x in range(1<<W):
        s = [list(c) for c in C]
        for k in range(H):
            if (y>>k)%2:
                s[k] = ["X"]*W
        for k in range(W):
            if (x>>k)%2:
                for l in range(H):
                    s[l][k] = "X"
        black = sum(c=="#" for c in chain(*s))
        if black == K:
            sum_num += 1

print(sum_num)

Submission status: Accepted

Solution code:
from copy import deepcopy

HEIGHT, WIDTH, K = map(int, input().split())
CELLS = [list(input()) for i in range(HEIGHT)]

ans = 0

for maskY in range(1<<HEIGHT):
  for maskX in range(1<<WIDTH):
    black=0
    for y in range(HEIGHT):
      for x in range(WIDTH):
        if (maskY >> y & 1) == 0 and (maskX >> x & 1) == 0 and CELLS[y][x] == '#':
          black+=1
    if K == black:
      ans+=1


print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[0]*h
for i in range(h):
  c[i]=list(str(input()))
l=h+w
ans=0
M = 2#bit探査をしたい時はM=2
def dfs(A):
    global ans
    # 終端条件 --- l 重ループまで回したら処理して打ち切り
    if len(A) == l:
        b=0
        for i in range(h):
          if A[i]==0:
            continue
          else:
            for j in range(w):
              if A[h:l][j]==1 and c[i][j]=='#':
                b+=1
        if b==k:
          ans+=1
        return
    for v in range(M):
        A.append(v)
        dfs(A)
        A.pop() # これが結構ポイント
dfs([])
print(ans)

Submission status: Accepted

Solution code:
import copy

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

ans=0
for i in range(2**h):
  for j in range(2**w):
    c=copy.deepcopy(a)
    for x in range(h):
      if ((i>>x)&1):
        for u in range(w):
          c[x][u]='R'
          
    for y in range(w):
      if ((j>>y)&1):
        for t in range(h):
          c[t][y]='R'
    ch=0
    for z in c:
      ch+=z.count('#')
    if ch==k:
      ans+=1
      
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    H, W, K = map(int, input().split())
    c = [input() for i in range(H)]

    ans = 0
    for maskR in range(2 ** H):
        for maskC in range(2 ** W):
            black = 0
            for i in range(H):
                for j in range(W):
                    if ((maskR >> i) & 1) and ((maskC >> j) & 1) and c[i][j] == '#':
                        black += 1
                    
            if black == K:
                ans += 1
            
    print(ans) 

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    H, W, K = map(int, input().split())
    c = [input() for i in range(H)]

    ans = 0
    for maskR in range(2 ** H):
        for maskC in range(2 ** W):
            black = 0
            for i in range(H):
                for j in range(W):
                    if 2 ** i & maskR > 0 and 2 ** j & maskC > 0 and c[i][j] == '#':
                        black += 1
                    
            if black == K:
                ans += 1
            
    print(ans) 

main()

Submission status: Accepted

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

ans = 0

for row in range(1 << h): #2^h - 1
  for col in range(1 << w): #2^w -1
    black = 0
    for i in range(h):
      for j in range(w):
        if (row >> i) & 1 == 0 and (col >> j) & 1 == 0 and c[i][j] =='#':
           black += 1
    if black == k:
      ans += 1

print(ans)

Submission status: Accepted

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

ans = 0

for row in range((1 << h) - 1): #2^h - 1
  for col in range((1 << w) - 1): #2^w -1
    black = 0
    for i in range(h):
      for j in range(w):
        if (row >> i) & 1 == 0 and (col >> j) & 1 == 0 and c[i][j] =='#':
           black += 1
    if black == k:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
# H and V
# 高々 2 ** 12 通りなので全探索で良い
import numpy as np
H,W,K = map(int,input().split())
HW = np.repeat('', H*W).reshape(H,W) 
ans = 0
for _ in range(H):
    HW[_] = np.array(list(input()))

for _ in range(1<<(H+W)):
    # print(format(_, 'b').zfill(H+W))
    choices = format(_, 'b').zfill(H+W)
    r = [i for i, v in enumerate(choices[:H]) if v == '1']
    c = [i for i, v in enumerate(choices[H:]) if v == '1']
    ans += [0, 1][np.sum(HW[r,:][:,c] == '#') == K]

print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

temp = []
for _ in range(H):
    C = list(input())
    A = [c.replace('.', '0') for c in C]
    A = [a.replace('#', '1') for a in A]
    A = list(map(lambda x: int(x), A))
    temp.append(A)

C = np.array(temp)

count = 0
l = [0, 1]
wide = itertools.product(l, repeat=W)
for w in wide:
    hight = itertools.product(l, repeat=H)
    for h in hight:
        copy_C = C.copy()
        for num, i in enumerate(w):
            if i == 1:
                copy_C[:, num-1] = 0
            for num2, j in enumerate(h):
                if j == 1:
                    copy_C[num2-1, :] = 0
        if copy_C.sum() == K:
            count += 1

print(count)

Submission status: Accepted

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

res = 0
from itertools import product
for v1 in product([0,1], repeat=h):
    for v2 in product([0,1], repeat=w):
        cnt = 0
        for i in range(h):
            if v1[i] == 0: continue
            for j in range(w):
                if v2[j] == 1 and c[i][j] == '#':
                    cnt += 1
        if cnt == k:
            res += 1
print(res)

Submission status: Accepted

Solution code:
import copy
h,w,k=map(int,input().split())
M=[list(input()) for _ in range(h)]
a=0
for i in range(2**w):
  for j in range(2**h):
    b=0
    for c in range(w):
      for r in range(h):
        if (i>>c)&1==0 and (j>>r)&1==0 and M[r][c]=='#':
          b+=1
    if b==k:
      a+=1
print(a)

Submission status: Accepted

Solution code:
from itertools import product
import copy
H,W,K = map(int,input().split())
C_ary = [[_ for _ in input()] for j in range(H)]
patrn_h = []
patrn_w = []
cntup = 0
for i in product([0,1], repeat = H):
    patrn_h.append(i)
for i in product([0,1], repeat = W):
    patrn_w.append(i)
for i in patrn_h:
    for j in patrn_w:
        cnt = 0
        test_ary = copy.deepcopy(C_ary)
        for h in range(H):
            for w in range(W):
                if i[h] == 0 or j[w] == 0:
                    test_ary[h][w] = "."
            cnt += test_ary[h].count("#")
        if cnt == K:
            cntup += 1
print(cntup)

Submission status: Accepted

Solution code:
from itertools import product
import copy
H,W,K = map(int,input().split())
C_ary = [[_ for _ in input()] for j in range(H)]
patrn_h = []
patrn_w = []
cntup = 0
for i in product([0,1], repeat = H):
    patrn_h.append(i)
for i in product([0,1], repeat = W):
    patrn_w.append(i)
for i in patrn_h:
    for j in patrn_w:
        fnl_cnt = 0
        test_ary = copy.deepcopy(C_ary)
        for h in range(H):
            cnt = 0
            for w in range(W):
                if i[h] == 0 or j[w] == 0:
                    test_ary[h][w] = "."
            cnt = test_ary[h].count("#")
            fnl_cnt += cnt
        if fnl_cnt == K:
            cntup += 1
print(cntup)

Submission status: Accepted

Solution code:
from itertools import product


def abc173c_h_and_v():
    h, w, k = map(int, input().split())
    c = [input() for _ in range(h)]
    cnt = 0
    for hp in product(range(2), repeat=h):
        for wp in product(range(2), repeat=w):
            a = [c[i][j] for j in range(w) if wp[j] == 1 for i in range(h) if hp[i] == 1]
            if k == a.count('#'):
                cnt += 1
    print(cnt)

abc173c_h_and_v()

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
fi = []
for _ in range(h):
  s = input()
  fi.append(s)
a = 1 << h
b = 1 << w
ans = 0
for i in range(a * b):
  lh = [0 for _ in range(h)]
  lw = [0 for _ in range(w)]
  for j in range(h):
    if i & (1 << j):
      lh[j] += 1
  for j in range(w):
    if i & (1 << (j + h)):
      lw[j] += 1
  cnt = 0
  for j in range(h):
    for l in range(w):
      if lh[j] == 1:
        continue
      if lw[l] == 1:
        continue
      if fi[j][l] == '#':
        cnt += 1
  if cnt == k:
    ans += 1
print(ans)

Submission status: Accepted

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

for maskH in range(1<<H):
    for maskW in range(1<<W):
        black = 0
        for i in range(H):
            for j in range(W):
                #両方のmaskが0の時だけ、'#'ならblack++する
                if maskH&(1<<i) and maskW&(1<<j) and C[i][j]=='#':
                    black += 1
        if black == K:
            ans += 1

print(ans)

Submission status: Accepted

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

blacks = [[None] * W for _ in range(H)]
black_sums = [[0] * W for _ in range(H)]
black_col_sums = [[0] * W for _ in range(H)]

for i in range(H):
    for j, item in enumerate(input()):
        if item == "#":
            blacks[i][j] = 1
        else:
            blacks[i][j] = 0


ok_count = 0
for i in range(1<<H):
    for j in range(1<<W):
        # print(f"{i:b}, {j:b}")

        black_count = 0
        for m in range(H):
            for n in range(W):
                if (1 & i >> m and 1 & j >> n) == False:
                    continue
                black_count += blacks[m][n]
        if black_count == K:
            ok_count += 1

print(ok_count)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    h, w, k = nm()
    g = [ns() for _ in range(h)]
    ans = 0
    for bih in range(1 << h):
        for biw in range(1 << w):
            cnt = 0
            for i in range(h):
                for j in range(w):
                    if bih & (1 << i) and biw & (1 << j) and g[i][j] == '#':
                        cnt += 1
            if cnt == k:
                ans += 1
    print(ans)
    return

solve()