Problem:


Score : 300 points

Problem Statement

We have a grid of H rows and W columns of squares. The color of the square at the i-th row from the top and the j-th column from the left (1 \leq i \leq H, 1 \leq j \leq W) is given to you as a character c_{i,j}: the square is white if c_{i,j} is ., and black if c_{i,j} is #.

Consider doing the following operation:

Choose some number of rows (possibly zero), and some number of columns (possibly zero). Then, paint red all squares in the chosen rows and all squares in the chosen columns.

You are given a positive integer K. How many choices of rows and columns result in exactly K black squares remaining after the operation? Here, we consider two choices different when there is a row or column chosen in only one of those choices.

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

H W K
c_{1,1}c_{1,2}...c_{1,W}
c_{2,1}c_{2,2}...c_{2,W}
:
c_{H,1}c_{H,2}...c_{H,W}

Output

Print an integer representing the number of choices of rows and columns satisfying the condition.

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

One choice, which is choosing nothing, satisfies the condition.

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

6 6 8
..##..
.#..#.
#....#
######
#....#
#....#

Sample Output 4

208



Sample input:
2 3 2
..#
###


Sample output:
5

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import product
def main():
    h, w, k = map(int,input().split())
    C = [input() for _ in range(h)]
    comb_list = list(product([False, True], repeat = h + w))
    ans = 0
    for comb in comb_list:
        cunt = 0
        for i in range(h):
            if not comb[i]:
                continue
            for j in range(w):
                if not comb[h+j]:
                    continue
                if C[i][j] == '#':
                    cunt += 1
        if cunt == k:
            ans += 1
    print(ans)



if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep  6 01:25:38 2020

@author: liang
"""

from itertools import combinations

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

C = [input() for _ in range(H)]
            
ans = 0
for comb_H in [list(combinations(range(H),a)) for a in range(H+1)]:
    for comb_W in [list(combinations(range(W),a)) for a in range(W+1)]:
        for tuple_H in comb_H:
            for tuple_W in comb_W:
                tmp = 0
                for i in range(H):
                    for j in range(W):
                        if i not in tuple_H and j not in tuple_W and C[i][j] == "#":
                            tmp += 1
                #print(tuple_H)
                #print(tuple_W)
                #print(tmp)
                if tmp == K:
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
Square=[0]*H
for i in range(H):
    C=input()
    Square[i]=C
ans=0
nowH=[0]*H
nowW=[0]*W
for j in range(2**H):
    for p in range(H):
        nowH[p]=j%2
        j//=2
    for k in range(2**W):
        kouho=0#この縦・横の選び方で残る黒の数
        for q in range(W):
            nowW[q]=k%2
            k//=2
        for s in range(H):
            for t in range(W):
                if nowH[s]==0 and nowW[t]==0 and Square[s][t]=="#":
                    kouho+=1
        if kouho==K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

h,w,k=map(int,input().split())
G=[]
for _ in range(h):
  s=input()
  S=[]
  for i in range(w):
    S.append(s[i])
  G.append(S)
ans=0

HH=[]
for i in range(1<<h):
  H=[]
  for j in range(h):
    if (i>>j)&1:
      H.append(j)
  HH.append(H)

WW=[]
for i in range(1<<w):
  W=[]
  for j in range(w):
    if (i>>j)&1:
      W.append(j)
  WW.append(W)

for i in range(1<<h):
  for j in range(1<<w):
    cnt=0
    hl=HH[i]
    wl=WW[j]
    for m in range(h):
      for n in range(w):
        if m in hl:
          continue
        if n in wl:
          continue
        if G[m][n]=='#':
          cnt+=1
    if cnt==k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
def make_bit(n):
    bit = []
    for i in range(2**n):
        bit.append(bin(i)[2::])
    i = 0
    while i < len(bit):
        while len(bit[i]) < len(bin(2**n-1)[2::]):
            bit[i] = "0" + bit[i]
        i += 1

    return bit

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

c = [list(input()) for _ in range(h)]

h_pats = make_bit(h)
w_pats = make_bit(w)
ans = 0
for h_pat in h_pats:
    for w_pat in w_pats:
        cnt = 0
        for i in range(h):
            for j in range(w):
                if h_pat[i] == "1" or w_pat[j] == "1":
                    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(' '))
c = [input() for x in range(h)]
cnt = 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) == 0
                    and ((maskC >> j) &1) == 0 and c[i][j] == '#'):
                    black += 1
        if black == k:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split(' '))
c = [input() for x in range(h)]
cnt = 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) == 0
                    and ((maskC >> j) &1) == 0 and c[i][j] == '#'):
                    black += 1
        if black == k:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def resolve():
    H, W, K = map(int, input().split())
    C = [input() for _ in range(H)]
    cnt = 0
    for h in range(1 << H):
        for w in range(1 << W):
            black = 0
            for i in range(H):
                for j in range(W):
                    if h >> i & 1 or w >> j & 1:
                        continue
                    if C[i][j] == "#":
                        black += 1
            if black == K:
                cnt += 1

    print(cnt)
resolve()

Submission status: Accepted

Solution code:
from itertools import product

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

# print(C)
ans = 0 

for row_bit in product(range(2), repeat=H):
    # print(row_bit) 
    # print(row_bit[0])
    # print(row_bit[1])
    for col_bit in product(range(2), repeat=W):
        # print(col_bit)
        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(' '))
c = [input() for x in range(h)]
cnt = 0
for m in range(2**(h+w)):
    cc = c.copy()
    for ij in range(h+w):
        if ((m >> ij) & 1):
            if ij in range(h):
                cc[ij] = '.'*w
            if ij in range(h,h+w):
                for t in range(h):
                    cc[t] = cc[t][:ij-h]+'.'+cc[t][ij+1-h:]
    num = sum(cc[s].count('#') for s in range(h))
    if num == k:
        cnt += 1
print(cnt)

Submission status: Accepted

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

cnt = 0
for h in range(1 << H):
    for w in range(1 << W):
        black = 0
        for i in range(H):
            if (h >> i & 1) == 1:
                continue
            for j in range(W):
                if (w >> j & 1) == 1:
                    continue
                if C[i][j] == "#":
                    black += 1
        if black == K:
            cnt += 1
print(cnt)

Submission status: Accepted

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

for i in range(1 << h):
    for j in range(1 << w):
        cnt = 0
        for ii in range(h):
            for jj in range(w):
                if (i >> ii & 1):
                    continue
                if (j >> jj & 1):
                    continue
                if c[ii][jj] == "#":
                    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=np.zeros((H,W))

for i in range(H):
    c=input()
    for j in range(len(c)):
        if c[j]=="#":
            C[i][j]=1
CH=[]
CW=[]

for i in range(2**H):
    cl=[]
    for j in range(H):
        if bin(i)[-j-1]=="1":
            cl.append(j)
        elif bin(i)[-j-1]=="b":
            break
    CH.append(cl)

for i in range(2**W):
    cl=[]
    for j in range(W):
        if bin(i)[-j-1]=="1":
            cl.append(j)
        elif bin(i)[-j-1]=="b":
            break
    CW.append(cl)

ans=0
for i in range(len(CH)):
    for j in range(len(CW)):
        count=0
        for k in range(len(CH[i])):
            for l in range(len(CW[j])):
                count+=C[CH[i][k]][CW[j][l]]
        if count==K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
from itertools import product
def input(): return sys.stdin.readline().rstrip()

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

    ans = 0
    for row in product([0, 1], repeat=h):
        for col in product([0, 1], repeat=w):
            cnt = 0
            for i in range(h):
                for j in range(w):
                    if row[i] and col[j] and c[i][j] == '#':
                        cnt += 1
            if cnt == k:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def trans(l):
    return [list(x) for x in list(zip(*l))]

from itertools import product
import copy

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

A = [i for i in product([1,0], repeat=h)]
B = [i for i in product([1,0], repeat=w)]

ans = 0
for a in A:
    temp1 = copy.copy(c)
    for i, x in enumerate(a):
        if x == 1:
            temp1[i] = ["."] * w 
    for b in B:
        temp2 = trans(temp1)
        for i, x in enumerate(b):
            if x == 1:
                temp2[i] = ["."] * h
        
        cnt = 0
        for t in temp2:
            cnt += t.count("#")
        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)]
ans = 0

from itertools import product
for row_bit in product(range(2), repeat=h):
  for col_bit in product(range(2), repeat=w):
    black_cnt = 0
    for i in range(h):
      for j in range(w):
        # bitに0が立っているときは塗らない
        if c[i][j] == '#' and (row_bit[i]==0 and col_bit[j]==0):
          black_cnt += 1
    if black_cnt == k:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int,input().split())
grid = [list(input()) for i in range(H)]
total = 0
for mask1 in range(1<<H):
    for mask2 in range(1<<W):
        ct = 0
        for i in range(H):
            for j in range(W):
                if grid[i][j]=='#' and not (1<<i)&mask1 and not (1<<j)&mask2:
                    ct += 1
        if ct==K:
            total += 1
print(total)

Submission status: Accepted

Solution code:
H, W, K, = list(map(int, input().split()))
C = [0] * H
for i in range(H):
  C[i] = input()
  C[i] = [1 if(C[i][j] == "#") else 0 for j in range(W)]
h = 2 ** H
w = 2 ** W
ans = 0
cnt = 0
for i in range(2 ** H):
  w = 2 ** W
  for j in range(2 ** W):
    cnt = 0
    for k in range(H):
      for l in range(W):
        if(bin(h)[k + 3] == "0" and bin(w)[l + 3] == "0"):
          cnt += C[k][l]
    ans += (cnt == K)
    w += 1
  h += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
H, W, K, = list(map(int, input().split()))
C = [0] * H
for i in range(H):
  C[i] = input()
  C[i] = [1 if(C[i][j] == "#") else 0 for j in range(W)]
h = 2 ** H
w = 2 ** W
ans = 0
for i in range(2 ** H):
  w = 2 ** W
  for j in range(2 ** W):
    D = copy.deepcopy(C)
    for k in range(H):
      for l in range(W):
        if(bin(h)[k + 3] == "1" or bin(w)[l + 3] == "1"):
          D[k][l] = 0
    ans += (sum(map(sum, D)) == K)
    w += 1
  h += 1
print(ans)

Submission status: Accepted

Solution code:

def main():
    H, W, K = map(int, input().split(" "))
    c = [[c for c in input()] for _ in range(H)]
    cnt = 0
    ans = 0
    for i in range(1 << H):
        for j in range(1 << W):
            cnt = 0
            for ii in range(H):
                for jj in range(W):
                    if(i >> ii & 1):
                        continue
                    if(j >> jj & 1):
                        continue
                    if(c[ii][jj] == '#'):
                        cnt += 1
            if cnt == K :
                ans += 1
    print(ans)
    
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    H, W, K = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    combs = []
    total_blacks = 0
    ans = 0
    for a in A:
        for a_ in a:
            if a_ == "#":
                total_blacks += 1

    for i in range(2**(H+W)):
        tmp_combs = []
        for j in range(H+W):
            if (i >> j) & 1:
                tmp_combs.append(1)
            else:
                tmp_combs.append(0)
        combs.append(tmp_combs)
    
    for c in combs:
        num_black = total_blacks
        for i in range(H):
            for j in range(W):
                h, w = c[i], c[H+j]
                if (h == 1 or w == 1) and A[i][j] == "#":
                    num_black -= 1

        if num_black == K:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# ビット全探索で全パターンをチェック
# n個のものからいくつか選ぶ組み合わせの数は 2**n 
# 例えば、3個の場合は 2**3 = 8通り
# 0: 0b000
# 1: 0b001
# 2: 0b010
# 3: 0b011
# 4: 0b100
# 5: 0b101
# 6: 0b110
# 7: 0b111
# バイナリの 0 は選ばれている、1 は選ばれていない
# https://drken1215.hatenablog.com/entry/2019/12/14/171657
ans = 0
for i in range(2**h):
    for j in range(2**w):
        ct = 0
        for ii in range(h):
            for jj in range(w):
                # 塗りつぶされない黒をカウントする
                # カウントした結果が残った数と同じであれば、回答に+1
                if (i>>ii)&1 == 0 and (j>>jj)&1 == 0:
                    if tbl[ii][jj] == '#':
                        ct += 1
        if ct == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

h,w,k = map(int, input().split())
c = [list(input()) for i 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:
from copy import deepcopy
from sys import stdin
input = stdin.readline
H,W,K = map(int, input().split())
mat = [list(input()) for _ in range(H)]
ans = 0
for b_i in range(2**H):
    mat_1 = deepcopy(mat)
    for i in range(H):
        if b_i >> i & 1:
            for col in range(W):
                mat_1[i][col] = '.'
        
    for b_j in range(2**W):
        mat_2 = deepcopy(mat_1)
        for j in range(W):
            if b_j >> j & 1:
                for row in range(H):
                    mat_2[row][j] = '.'

        cnt = 0
        for row in mat_2:
            cnt += row.count('#')
        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(input())
#こういうinputをすると，c_ij = c[i][j] (C[i]という文字列のj文字目)という構造になってくれて，とても嬉しい。
#print(c)

ans = 0

#bit全探索
for rows in range(1 << H):
    #bit演算子。1 << H は二進数で1000...という風に，1の後ろに0がH個並ぶ。
    #例えば rows = 110010 のときには，(2 ** 5ケタ目の1は無視して）（0-indexで）1行目と4行目を赤で塗る状態を指す。
    for cols in range(1 << W):
        black_count = 0

        for i in range(H):
            if (rows >> i) % 2 == 1:continue #i行目が赤で塗られていたならば，何もせずiを一歩進める。

            for j in range(W):
                if (cols >> j) % 2 ==1:continue #j列目が赤で塗られていたならば，何もせずjを一歩進める。
                if c[i][j] == "#":
                    black_count += 1

        if black_count == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

H, W, K = map(int, input().split())
S = [input() for i in range(H)]
ans = 0
for si in itertools.product([0, 1], repeat=H):
    for sj in itertools.product([0, 1], repeat=W):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if si[i] or sj[j]:
                    continue
                if S[i][j] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

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

count1 = 0
for i in range(1<<h):
    for j in range(1<<w):
        count = 0
        for ia in range(h):
            if i&(1<<ia):continue
            for ib in range(w):
                if j&(1<<ib):continue
                if list1[ia][ib] == '#':
                    count += 1
        if count == k:
            count1 += 1


print(count1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy

def bit_list(x: int, n: int) -> list:
    '''
    xのn乗のbit配列を返す
    '''
    ans = []
    for i in range(x ** n):
        num = i
        j = 0
        table = [0 for _ in range(n)]
        while num:
            table[j] = num % x
            num = num // x
            j += 1

        ans.append(table)

    return ans

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

ans = 0
bits = bit_list(2, H + W)

for bit in bits:
    tmp_M = copy.deepcopy(M)
    for i in range(H + W):
        if i < H and bit[i] == 1:
            for j in range(W):
                 tmp_M[i][j] = "R"
        if i >= H and bit[i] == 1:
            for j in range(H):
                 tmp_M[j][i - H] = "R"

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

    if count == 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
cnt = 0

for i in range(2 ** H):
    for j in range(2 ** W):
        cnt = 0
        for k in range(H):
            for l in range(W):
                if ((i >> k) & 1) and ((j >> l) & 1):
                    if C[k][l] == '#':
                        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
cnt = 0

for i in range(2 ** H):
    for j in range(2 ** W):
        cnt = 0
        for k in range(H):
            for l in range(W):
                if ((i >> k) & 1) and ((j >> l) & 1):
                    if C[k][l] == '#':
                        cnt += 1
                
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**h):
    for j in range(2**w):
        cnt = 0
        for ii in range(h):
            for jj in range(w):
                if (i>>ii)&1 == 1 and (j>>jj)&1 == 1:
                    if c[ii][jj] == '#':
                        cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
ans = 0
def get(sta):
    ret = set()
    for i in range(6):
        if sta & 1:
            ret.add(i)
        sta //= 2
    return ret
grd=[input() for i in range(h)]
for i in range(2**h):
    hs=get(i)
    for j in range(2**w):
        ws=get(j)
        chk = 0
        for a in range(h):
            for b in range(w):
                if a in hs or b in ws or grd[a][b]==".":continue
                chk += 1
        if chk == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import Counter
# 全探索なら、 2**6 * 2**6 （4000）
#            > 4000 * (6**2)
# bit全探索でOK
# ------------------------------------------
h, w, num = map(int, input().split())
data = []
for _ in range(h):
    # 一文字ずつListへ格納
    temp = list(input())
    data.append(temp)
#data = [input() for _ in range(h)]
# print(data)

'''
count = Counter(data)
most = count.most_common()
print(most)
'''
ans = 0

# 縦の全Loop
for i in range(2 ** h):
    for j in range(2 ** w):
        #print(i, j)
        *temp, = data
        temp = np.array(temp)
        for k in range(h):
            if (i >> k & 1):
                temp[k, :] = 'aa'

        for l in range(w):
            if (j >> l & 1):
                temp[:, l] = 'aa'

        count = np.where(temp == '#')[0]
        #print(count, len(count))
        if (len(count) == num):
            # print('add')
            ans += 1
        else:
            pass


print(ans)

Submission status: Accepted

Solution code:
'''
Created on 2020/08/30

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  H,W,K=map(int,pin().split())
  C=[pin()[:-1] for _ in [0]*H]
  ans=0
  for i in range(2**H):
    for j in range(2**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==K:
        ans+=1
  print(ans)
  return
main()
#解説AC

Submission status: Accepted

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

c = 0
for x in range(2**h):
  for y in range(2**w):
    e =  [['t' for _ in range(w)] for _ in range(h)]
    for i in range(h):
      if ((x >> (h-1-i)) & 1) == 1:
        for l in range(w):
          e[i][l] = 'R'
    
    for j in range(w):
      if ((y >> (w-1-j)) & 1) == 1:
        for m in range(h):
          e[m][j] = 'R'
    
    s = 0     
    for p in range(h):
      for q in range(w):
        if d[p][q] == '#' and e[p][q] != 'R':
          s += 1
    
    if s == k:
      c += 1
            
print(c)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
c=[]
for i in range(H):c.append(list(input()))
cnt,ans=0,0
for h in range(2**H):
  cnt=0
  for w in range(2**W):
    cnt=0
    for i in range(H):
      for j in range(W):
        if ((h>>i)&1) and ((w>>j)&1):
          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())
mass = []
black_count = 0
ans = 0
for _ in range(h):
    row = list(input())
    mass.append(row)
    black_count += row.count("#")

goal = black_count - k    

for i in range(2**h):
    row_tmp = str(bin(i)).split("0b")[1]
    row_tmp = '0'*(h - len(row_tmp))+row_tmp
    for j in range(2**w):
        col_tmp = str(bin(j)).split("0b")[1]
        col_tmp = '0'*(w - len(col_tmp))+col_tmp
        
        row_count = 0
        col_count = 0
        for k in range(h):
            row_count += (mass[k] * int(row_tmp[k])).count("#")
        for k in range(h):
            for l in range(w):
                col_count += (mass[k][l] * (int(col_tmp[l]) * (1-int(row_tmp[k])))).count("#")
        if goal == row_count+ col_count:
            ans += 1
print(ans)

Submission status: Accepted

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

def get_conbination(i,length):
    return format(i, '#0'+str(length+2)+'b')[2:]
sheet=[]
for i in range(h):
    sheet.append(input())

ans=0
for i in range(2**h):
    for j in range(2**w):
        total=0
        gyou_select=get_conbination(i,h)
        retu_select = get_conbination(j, w)
        for gyou in range(h):
            for retu in range(w):
                if gyou_select[gyou]=="0" and retu_select[retu]=="0":
                    if sheet[gyou][retu]=="#":
                        total+=1
        if total==k:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
grid = [input() for _ in range(H)]
N = H+W
ans = 0
start = 0
for i in grid:
    start += i.count('#')

for i in range(2**N):
    tmp = start
    painted = []
    for j in range(H):
        if (i>>j)&1:
            tmp -= grid[j].count('#')
            painted.append(j)
    for j in range(W):
        if (i>>j+H)&1:
            for k in range(H):
                if '#' == grid[k][j]:
                    if k in painted:
                        continue
                    else:
                        tmp -= 1
    if tmp == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
C = [input() for _ in range(H)]
 
# 2次元のbit全探索
# 各探索ごとに、塗られていない黒いマスの個数を数え、K個なら ans+=1
ans = 0
for h in range(2**H):
  for w in range(2**W):
    black = 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] == '#': black += 1
    
    if black == 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 h in range(2**H):
  for w in range(2**W):
    black = 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] == '#': black += 1
    
    if black == K:
      ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**h):
    for j in range(2**w):
        cnt = 0
        for ii in range(h):
            for jj in range(w):
                if (i>>ii)&1 == 1 and (j>>jj)&1 == 1:
                    if c[ii][jj] == '#':
                        cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
array = [ list(input()) for t in range(H) ]
ans = 0
for bit_row in range( 2 ** H ):
  for bit_line in range( 2 ** W ):
    count = 0
    for i in range(H):
      for j in range(W):
        if ( bit_row >> i ) & 1 == 0 and ( bit_line >> j ) & 1 == 0:
          if array[i][j] == '#':
            count += 1
    if count == K:
      ans += 1
print(ans)

Submission status: Accepted

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

#bit演算
for i in range(2 ** H):
  for j in range(2 ** W):
    b = 0
    for k in range(H):
      for l in range(W):
        #縦も横も塗らない色が黒のマスを数える
        if i >> k & 1 and j >> l & 1 and c[k][l] == "#": b += 1
    if b == K: ans += 1

print(ans)

Submission status: Accepted

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

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

#bit演算
for i in range(2 ** H):
  for j in range(2 ** W):
    b = 0
    for k in range(H):
      for l in range(W):
        #縦も横も塗らない色が黒のマスを数える
        if i >> k & 1 and j >> l & 1 and c[k][l] == "#": b += 1
    if b == 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 point_h in range(2**h):
    for point_w in range(2**w):
        cnt=0
        for i in range(h):
            for j in range(w):
                if (point_h>>i)&1==0 and (point_w>>j)&1==0:
                    if board[i][j]=="#":
                        cnt+=1
        if k==cnt:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
import math
import sys
import os
from operator import mul
import collections
import itertools
import numpy as np
import copy

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

H,W,K = LI()
grid = [list(_S()) for i in range(H)]
ans = 0

for x in range(1<<H):
    for y in range(1<<W):
        count = 0
        for i in range(H):
            for j in range(W):
                # 塗りつぶされない
                if (x >> i) & 1 == 0 and (y >> j) &1 ==0:
                    if grid[i][j] == '#':
                        count += 1
        if count == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
 
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())
def rec(h, w): return [[0] * w for i in range(h)] 

h, w, k = I()
board = []

for _ in range(h):
  s = S()
  board.append([1 if x == '#' else 0 for x in s])

ans = 0
for i in range(2 ** (h + w)):
  b = bin(i)[2:].zfill(h+w)
  s = np.sum([int(b[x // w]) * int(b[h + (x % w)]) * board[x // w][x % w] for x in range(h*w)])
  if s == k:
    ans += 1
  
print(ans)