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())
c = []
for i in range(h):
    c.append(tuple(input()))
res = 0
for maskh in range(1<<h):
    for maskw in range(1<<w):
        brack = 0
        for i in range(h):
            for j in range(w):
                if (maskh >> i) & 1 and (maskw >> j) & 1:
                    if c[i][j] == '#': brack += 1
        if brack == k:
            res += 1
print(res)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
hbit, wbit = 1 << H, 1 << W
cnt = 0
for i in range(hbit):
  for j in range(wbit):
    ccnt = 0
    for k in range(H):
      for l in range(W):
        if not (((i>>k)&1) + ((j>>l)&1)):
          ccnt += (S[k][l] == '#')
    cnt += (ccnt == K)
print(cnt)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
##複数行の文字列を一文字ずつリストの要素として格納
board = [list(input()) for _ in range(h)]

ans = 0
for paint_h in range(2 ** h): #すべての行の塗りつぶし方を2進数で列挙する
 for paint_w in range(2 ** w): #すべての列の塗りつぶし方を2進数で列挙する
   cnt=0
   for i in range(h): #すべてのi行目j列目の要素についてみる
     for j in range(w):
       if (paint_h >> i) & 1 == 0 and (paint_w >> j) & 1 == 0: #各行のi番目のビットと各列のj番目のビットがともに0であればそのマスは塗りつぶされない
         if board[i][j] == '#': #塗りつぶされないマスが黒マスであれば個数を+1する
           cnt += 1
   if cnt == k: #塗りつぶされない黒マスの個数がKに等しければ答えを+1する
     ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy


def main():
    height, width, leave_black = [int(x) for x in input().split()]
    table = [list(input()) for _ in range(height)]
    ans = 0
    for num_h in range(2 ** height):
        for num_w in range(2 ** width):
            tmp = copy.deepcopy(table)
            for bit_h in range(height):
                if num_h >> bit_h & 1:
                    tmp[bit_h] = ['r'] * width
            for bit_w in range(width):
                if num_w >> bit_w & 1:
                    for row in tmp:
                        row[bit_w] = 'r'
            # print(num_h, num_w, tmp)
            if sum(c == '#' for row in tmp for c in row) == leave_black:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    height, width, leave_black = [int(x) for x in input().split()]
    table = [input() for _ in range(height)]

    def bit_patterns(height, width):
        for num_h in range(2 ** height):
            for num_w in range(2 ** width):
                yield num_h, num_w

    def count_black(height, width, num_h, num_w):
        for bit_h in range(height):
            for bit_w in range(width):
                if num_h >> bit_h & 1 or num_w >> bit_w & 1:
                    continue
                yield table[bit_h][bit_w] == '#'

    def black_matched(height, width):
        for ii, jj in bit_patterns(height, width):
            yield sum(count_black(height, width, ii, jj)) == leave_black

    print(sum(black_matched(height, width)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:

def main():
    height, width, leave_black = [int(x) for x in input().split()]
    table = [input() for _ in range(height)]

    ans = 0
    for num_h in range(2 ** height):
        for num_w in range(2 ** width):
            black_count = 0
            for bit_h in range(height):
                for bit_w in range(width):
                    if num_h >> bit_h & 1 or num_w >> bit_w & 1:
                        continue
                    black_count += table[bit_h][bit_w] == '#'
            ans += black_count == leave_black

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
listc = []
listc = [list(input()) for i in range(H)]
#print(listc)
ans = 0
for j in range(2**H):
    for k in range(2**W):
        count = 0
        for l in range(H):
            for m in range(W):
                if j >> l & 1 == 0 and k >> m & 1 == 0:
                    if listc[l][m] == "#":
                        count += 1
        if count == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
ans=0
for paint_h in range(2**h): #すべての行の塗りつぶし方を2進数で列挙する
 for paint_w in range(2**w): #すべての列の塗りつぶし方を2進数で列挙する
   cnt=0
   for i in range(h): #すべてのi行目j列目の要素についてみる
     for j in range(w):
       if (paint_h>>i)&1==0 and (paint_w>>j)&1==0: #各行のi番目のビットと各列のj番目のビットがともに0であればそのマスは塗りつぶされない
         if board[i][j]=='#': #塗りつぶされないマスが黒マスであれば個数を+1する
           cnt+=1
   if cnt==k: #塗りつぶされない黒マスの個数がKに等しければ答えを+1する
     ans+=1
print(ans)

Submission status: Accepted

Solution code:
H,W,K=list(map(int,input().split()))
board = [list(input()) for i 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 board[i][j]=='#':
            cnt+=1
    if cnt==K:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import time
import math
st = time.perf_counter()
def inpl():
    return list(map(int, input().split()))
# ------------------------------

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

ans = 0
for h in range(2**H):
	for w in range(2**W):
		kuro = 0
		for i in range(H):
			if (2 ** i) & h == 0: continue
			for j in range(W):
				if (2 ** j) & w == 0: continue
				if c[i][j] == '#':
					kuro += 1
		if kuro == K:
			ans += 1

print(ans)


# ------------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Accepted

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7



def paint(i, j, copied):

    for I in range(h):
        if((i>>I)&1):
            for J in range(w):
                copied[I][J] = "$"

    for J in range(w):
        if((j>>J)&1):
            for I in range(h):
                copied[I][J] = "$"

def check(grid1):
    toret = 0
    for i in range(h):
        for j in range(w):
            if(grid1[i][j]=='#'):
                toret+=1
    return (toret==k)

h,w,k = MAP()

grid = []

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


ans = 0

for row in range(1<<h):
    for col in range(1<<w):
        copied = [x[:] for x in grid]
        paint(row, col, copied)

        ans+=check(copied)
        # print(copied, grid, ans, row, col)
print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int,input().split())
grid = [[] for x in range(h)]
for i in range(h):
    grid[i] = input()
cnt = 0
for i in range(1<<h):
    for j in range(1<<w):
        black = 0
        for p in range(h):
            for q in range(w):
                if 1&(i>>p) == 0 and 1&(j>>q) == 0 and grid[p][q] == '#':
                    black += 1
        if black == k:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
H = 0
W = 0
K = 0
m = []
 
try:
  line = input().split(' ')
  H = int(line[0])
  W = int(line[1])
  K = int(line[2])
  for i in range(H):
      m.append(input())      
except:
  pass

nPatterns = 0
for h in range(1 << H):
    for w in range(1 << W):
        nBlacks = 0
        for h2 in range(H) :
            for w2 in range(W):
                if (h & (1 << h2)) == 0 and (w & (1 << w2)) == 0:
                    if m[h2][w2] == '#':
                        nBlacks += 1
        if nBlacks == K:
            nPatterns += 1
            
print(nPatterns)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
c = [input() for i in range(h)]
ans = 0  # 何通りあるか
for row in range(1 << h):  # h行の選び方は2のh乗通り
    for col in range(1 << w):  # w行の選び方は2のw乗通り
        cnt = 0  # 黒いマスの数
        for i in range(h):
            for j in range(w):
                if row >> i & 1:
                    # h行目を選ぶ場合、該当行は黒ではないのでスキップ
                    continue
                if col >> j & 1:
                    # i列目を選ぶ場合、該当列は黒ではないのでスキップ
                    continue
                if c[i][j] == "#":
                    # 黒の数を数える
                    cnt += 1
        ans += cnt == k  # 黒の数がk個残る選び方が何通りあるか数える
        # if cnt == k:
        #     # 黒の数がk個残る選び方が何通りあるか数える
        #     ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K, *C = open(0).read().split()
C = sum([list(c) for c in C], [])
H = int(H)
W = int(W)
K = int(K)
ans = 0

# bits: h1 h2 w1 w2 w3
for row in range(1 << H):
    for col in range(1 << W):
        cnt = 0
        for h in range(H):
            for w in range(W):
                if (row >> h) & 1 and (col >> w) & 1 and C[h*W+w] == "#":
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

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

import copy

# 全パターン試す
ans = 0
for f in range(2**(H+W)):
    
    # フィルタ処理
    B = copy.deepcopy(C)
    for bit in range(H+W):
        if f & (1<<bit):
            if bit < W:
                # 列フィルタ
                for i in range(H):
                    B[i][bit] = '.'
            else:
                # 行フィルタ
                bit -= W
                for i in range(W):
                    B[bit][i] = "."
    
    
    # 残った白マスを数える
    rem = 0
    for line in B:
        rem += ''.join(line).count('#')
    
    if rem == K:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
a = input().rstrip().split(" ")
 
H = int(a[0])   #行
W = int(a[1])   #列
K = int(a[2])   #操作後に残る黒いマスの数
 
m = []
for i in range(H):
    n = list(input())
    m.append(n)
 
#print(m)
ans = 0
 
#2進数のyes/no(赤く塗るか否か)列を作る
for maskR in range(1 << H):
    for maskC in range(1 << W):
        black = 0
        
        for i in range(H):
            for j in range(W):
                if (maskR >> i & 1) == 0 and (maskC >> j & 1) == 0 and m[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(input())
ans = 0
for i in range(2**h):
    for j in range(2**w):
        counter = 0
        for m in range(h):
            for n in range(w):
                    if (i>>m)&1 == 0 and (j>>n)&1 == 0 and C[m][n] == '#':
                        counter += 1
                    else:
                        continue
                        
        if counter == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,q=map(int,input().split())
c2=[input() for _ in range(h) ]
ans=0
for i in range(1<<w):#縦
  for j in range(1<<h):#横
    b=0
    for x in range(w):#ビット
      for y in range(h):
        if (i>>x &1)==0 and (j>>y &1)==0 and c2[y-1][x-1]=="#":
          b+=1   
    if b==q:
      ans+=1
print(ans)

Submission status: Accepted

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

for bit_h in range(1 << h):
  i_list = []
  for i in range(h):
    if bit_h & 1:
      i_list.append(i)
    bit_h >>= 1
  for bit_w in range(1 << w):
    count = 0
    j_list = []
    for j in range(w):
      if bit_w & 1:
        j_list.append(j)
      bit_w >>= 1
    for i in i_list:
      for j in j_list:
        if mark[i][j] == '#':
          count += 1
    if count == k:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

# input
H, W, K = map(int,input().split())  #Hは縦軸, Wは横軸
init_map = []
for i in range(H):
    row = list(input())  #行を入力
    init_map.append(row) #inital_mapに1行ずつ追加
ans = 0

for paint_h in range(2**H):  #2^n
    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 init_map[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 _ in range(h)]
bh=1<<h
bw=1<<w
ans=0
for i in range(bh):
    for j in range(bw):
        cnt=0
        for x in range(h):
            for y in range(w):
                if (1&(i>>x)) or (1&(j>>y)) or c[x][y]==".":
                    continue
                cnt+=1
        if cnt==k:
            ans+=1
                
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
grid = [input() for _ in range(H)]
ans = 0
for mh in range(1<<H):
    for mw in range(1<<W):
        count = 0
        for h in range(H):
            for w in range(W):
                if (mh>>h & 1) == 0 and (mw>>w & 1)==0 and grid[h][w]=='#':
                    count+=1
        if count==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 R in range(2**H):
    for C in range(2**W):
        black = 0
        for i in range(H):
            for j in range(W):
                if (not (R >> i) & 1) and (not (C >> j) & 1) and (c[i][j] == '#'):
                    black += 1
        if black == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import copy
h,w,k=map(int, input().split())
c=[list(input())  for i in  range(h)]
c=np.array(c)
def makeBag(n):
  bagl=[]
  for i in range(2**n):
      bag=[0]*n
      
      for j in range(n):
          if ((i>>j) & 1):
              bag[j]=1
      bagl.append(bag)
  return bagl
bagh=makeBag(h)
bagw=makeBag(w)

ans=0
for i in bagh:
  co=copy.deepcopy(c)
  #行を塗りつぶす
  for ii in range(h):
    if i[ii]==1:
      co[ii][:]=["r"]*len(co[ii][:])
  
  co=co.T
  co2=copy.deepcopy(co)
  for j in bagw:
    co=copy.deepcopy(co2)
    #転置して列を塗りつぶす
    for jj in range(w):
      if j[jj]==1:
        co[jj][:]=["r"]*len(co[jj][:])
  
    #黒の数を数える
    if np.sum(co=="#")==k:
      ans+=1
      
print(ans)

Submission status: Accepted

Solution code:
import copy
h,w,k=map(int,input().split())
c=[list(map(lambda x:x=="#", input())) for _ in range(h)]
ans=0
for p in range(2**h):
	for q in range(2**w):
		d=copy.deepcopy(c)
		for i in range(h):
			for j in range(w):
				if (p>>i)%2==1 or (q>>j)%2==1:
					d[i][j]=False
		x=0
		for i in range(h):
			for j in range(w):
				if d[i][j]:
					x+=1
		if x==k:
			ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools

# input
H, W, K = map(int,input().split())
init_map = []
for i in range(H):
    row = list(input())
    init_map.append(row)
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 init_map[i][j] == "#":
                        cnt += 1
        if cnt==K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
h, w, k = map(int, input().split())
grid = []
for i in range(h):
    grid.append(input())
# bit 全探索
ans = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        cnt = 0  # 黒ます"#"の個数
        for r in range(h):
            for c in range(w):
                if grid[r][c] == "#" and (not i >> r & 1) and (not j >> c & 1):
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
C=[]
for _ in range(H):
    C.append(list(input()))
# シフト演算と&を使うと早い.
ans = 0
for i in range(1<<H): # 要するに2**Hのこと
    for j in range(1<<W): # 要するに2**Wのこと
        count = 0
        for i2 in range(H):
            for j2 in range(W):
                bit_i = i>>i2 & 1
                bit_j = j>>j2 & 1
                if bit_i == 1 or bit_j == 1:
                    continue
                if C[i2][j2] == '#':
                    count += 1
        if count == K:
            ans += 1

print(ans)

Submission status: Accepted

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

ans =0

for s in range(2**h):
    b_h = '{:06b}'.format(s)
    for t in range(2**w):
        b_w = '{:06b}'.format(t)
        black = 0
        for i in range(h):
            for j in range(w):
                if C[i][j]=='#' and b_h[-(i+1)] == '0' and b_w[-(j+1)]=='0':
                    black += 1
        if black==k:
            ans +=1
print(ans)

Submission status: Accepted

Solution code:
import copy


def q3():
    H, W, K = [int(i) for i in input().split(" ")]
    C = []
    for _ in range(H):
        C.append([i for i in input()])

    def helper(li):
        count = 0
        for i in range(len(li)):
            for j in range(len(li[i])):
                if li[i][j] == "#":
                    count += 1
        return count

    def get_all_selection(num):
        li = []
        if num == 0:
            return []
        if num == 1:
            return [[False], [True]]
        for l in get_all_selection(num - 1):
            li.append([False] + l)
            li.append([True] + l)
        return li

    answer = 0

    for sh in get_all_selection(H):
        for sw in get_all_selection(W):
            c = copy.deepcopy(C)
            for i in range(H):
                if not sh[i]:
                    c[i] = ["-"] * W
            for i in range(W):
                if not sw[i]:
                    for l in c:
                        l[i] = "-"

            black_count = helper(c)
            if black_count == K:
                answer += 1
                # print(sh, sw, c)

    print(answer)


q3()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import combinations

H, W, K = [int(x) for x in input().split()]

field = []

for i in range(H):
    width = []
    for j, x in enumerate(input()):
        if x == '.':
            width.append(0)
        else:
            width.append(1)
    field.append(width)

result = 0

for h in range(2**H):
    for w in range(2**W):
        count = 0
        for y in range(H):
            for x in range(W):
                if ((h >> y) & 1):
                    if ((w >> x) & 1):
                        count += field[y][x]
        if count == K:
            result += 1
        #print("{} -> count : {}".format((h, w), count))

print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def mi(): return map(int, sys.stdin.readline().split())

H, W, K = mi()
C = [input() for i in range(H)]

B_i = 2 ** H
B_j = 2 ** W

ans = 0
for x in range(B_i):
    for y in range(B_j):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if (x & (1 << i)) or y & (1 << j):
                    continue
                if C[i][j] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1
                
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
m = []
A = 0
for _ in range(H):
  m.append([v for v in input()])
for h in range(2**H):
  for w in range(2**W):
    ans = 0
    for h2 in range(H):
      for w2 in range(W):
        if h>>h2&1 and w>>w2&1 and m[h2][w2]=='#':
          ans += 1
    #print(h,w,ans)
    if ans == K:
      A += 1
print(A)

Submission status: Accepted

Solution code:
from itertools import product
import copy

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

ans = 0
for x in product([0,1], repeat=W):
    for y in product([0,1], repeat=H):
        c_cp = copy.deepcopy(C)
        #print(c_cp)
        #print(x)
        #print(y)
        for idx, i in enumerate(x):
            if i == 1:
                for n in range(H):
                    c_cp[n][idx] = "r"
        for idx, j in enumerate(y):
            if j == 1:
                for n in range(W):
                    #print(idx, n)
                    c_cp[idx][n] = "r"
        cnt = 0
        #print(c_cp)
        for s in c_cp:
            for t in s:
                if t == "#":
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(input()))
res=0
for i in range(2**n-1):
    for j in range(2**m-1):
        b=0
        for x in range(n):
            for y in range(m):
                c=2**x
                d=2**y
                if i&c==0 and j&d==0 and l[x][y]=="#":
                    b+=1
        if b==k:
            res+=1
print(res)

Submission status: Accepted

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

ans = 0
for h in range(1<<H):
  for w in range(1<<W):
    curr = 0
    for i in range(H):
      for j in range(W):
        if not (h & 1<<i) and not (w & 1<<j) and C[i][j] == '#':
          curr += 1
    if K == curr:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
h,w,k = map(int, input().split())
hw = [[0 for j in range(w)] for i in range(h)]
total = 0
htotal = [0 for i in range(h)]
wtotal = [0 for i in range(w)]

for i in range(h):
	line = [s for s in input()]
	for j in range(len(line)):
		if line[j]=='#':
			hw[i][j]=1
	htotal[i]=sum(hw[i])
for i in range(w):
	res=0
	for j in range(h):
		if hw[j][i]:
			res+=1
	wtotal[i]=res
total = sum(htotal)
#print(hw)
#print(total,htotal, wtotal)
ans = 0
for bit in product(range(2),repeat=w+h):
	wbit=bit[:w]
	hbit=bit[w:]
	res=0
	for i,v in enumerate(wbit):
		if v:res-=wtotal[i]
	for i,v in enumerate(hbit):
		if v:res-=htotal[i]
	#print(res)
	for i,hv in enumerate(hbit):
		if hv:
			for j,wv in enumerate(wbit):
				if wv:
					if hw[i][j]:
						res+=1
	#print('---', total,res,k)
	if total+res==k:
		ans+=1
		#print('bit', bit)
print(ans)

Submission status: Accepted

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


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

print(res)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[input() for _ in range(h)]
count=0
for H in range(1<<h):
  for W in range(1<<w):
    b=0
    for i in range(h):
      for j in range(w):
        if (H >> i) & 1 == 0 and (W >> j) & 1 == 0 and c[i][j] == "#":
          b+=1
    if b==k:
      count+=1
print(count)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
for i in range(2**H):
    for j in range(2**W):
        tmp = 0
        for ii in range(H):
            for jj in range(W):
                if C[ii][jj] == '#' and (i >> ii) & 1 == 0 and (j >> jj) & 1 == 0:
                    tmp += 1
        if tmp == K:
            ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy
def row(c, i, H, W):
  for j in range(W):
    c[i][j] = 0
    
def column(c, j, H, W):
  for i in range(H):
    c[i][j] = 0

def blacks(c, H, W):
  black = 0
  for row in c:
    black += sum(row)
  return black

H, W, K = map(int, input().split())
c = []
for i in range(H):
  c.append([])
  string = input()
  for color in string:
    if color == '#':
      c[-1].append(1)
    else:
      c[-1].append(0)
height = list(itertools.product([0, 1], repeat=H))
weight = list(itertools.product([0, 1], repeat=W))
answer = 0
for tate in height:
  for yoko in weight:
    cc = copy.deepcopy(c)
    for i in range(len(tate)):
      if tate[i]:
        row(cc, i, H, W)
    for j in range(len(yoko)):
      if yoko[j]:
        column(cc, j, H, W)
    if blacks(cc, H, W) == K:
      answer += 1
print(answer)

Submission status: Accepted

Solution code:
import copy
h,w,k=map(int,input().split())
c=[list(input()) for i in range(h)]
ans=0
for bit1 in range(1<<h):
    for bit2 in range(1<<w):
        count=0
        map=copy.deepcopy(c)
        for i in range(h):
            if bit1 & (1<<i):
                for j in range(w):
                    if map[i][j]=="." or map[i][j]=="#":
                        map[i][j]="!"
        for i in range(w):
            if bit2 & (1 << i):
                for j in range(h):
                    if map[j][i] == "." or map[j][i] == "#":
                        map[j][i] = "!"

        for i in range(h):
            for j in range(w):
                if map[i][j]=="#":
                    count+=1
        if count==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
a = input().rstrip().split(" ")

H = int(a[0])   #行
W = int(a[1])   #列
K = int(a[2])   #操作後に残る黒いマスの数

m = []
for i in range(H):
    n = list(input())
    m.append(n)

#print(m)
ans = 0

#2進数のyes/no(赤く塗るか否か)列を作る
for maskR in range(1 << H):
    for maskC in range(1 << W):
        black = 0
        
        for i in range(H):
            for j in range(W):
                if (maskR >> i & 1) == 0 and (maskC >> j & 1) == 0 and m[i][j] == "#":
                    black += 1
    
        if black == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

arr = np.empty((H,W))

count = 0


for i in range(H):
    str_list = list(input())
    str_list_replaced1 = [s.replace("#","1") for s in str_list]
    str_list_replaced2 = [s.replace(".","0") for s in str_list_replaced1]
    arr[i:] = np.array(str_list_replaced2)


for i in range(2**H):
    for j in range(2**W):
        mask = np.zeros(shape=(H,W))
        mask_i_tmp = [int(k) for k in format(i,"06b")][-H:]
        mask_j_tmp = [int(k) for k in format(j,"06b")][-W:]

        mask_i = mask + np.expand_dims(np.array(mask_i_tmp),-1)
        mask_j = mask + np.expand_dims(np.array(mask_j_tmp),-1).T
        masked_arr = arr.astype(bool) & mask_i.astype(bool) & mask_j.astype(bool)

        
        if np.sum(masked_arr) == K:
            count += 1 

print(count)

Submission status: Accepted

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

ans = 0
for mask_h in range(2**H):
    for mask_w in range(2**W):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if ((mask_h >> i) & 1) == 0 and ((mask_w >> j) & 1) == 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().strip().split(" "))

C = [[0] * W for _ in range(H)]
cnt = 0
for h in range(H):
    tmp = list(input())
    for w in range(W):
        if tmp[w] == "#":
            C[h][w] = 1

for h in range(2**H-1):
    for w in range(2**W-1):
        b = 0
        for i in range(H):
            if (h>>i) & 1 == 1:
                continue
            for j in range(W):
                if (w>>j) & 1 == 1:
                    continue
                b += C[i][j]
        if K == b:
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[]
total=0
for i in range(h):
  tmp=list(input())
  c.append(tmp)
  total+=tmp.count("#")
ans=0
for i in range(1<<h):
  for j in range(1<<w):
    cnt=0
    for l in range(h):
      for m in range(w):
        if i&(1<<l) and j&(1<<m) and c[l][m]=="#":
          cnt+=1
          #print("cnt",cnt)
    if cnt==k:
      ans+=1
print(ans)