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())
#Ci,jを表す配列を作成する
c = []
for i in range(H):
    c.append(input())

ans = 0

# 各行のYes or Noに関して列のYes or Noの全通りを試す
# bit演算を行うことで全通りを簡単に試すことができる
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) == 0 and ((w >> j) & 1) == 0 and c[i][j] == '#':
                    black += 1
        if black == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
a,b,c=map(eval,input().split())
lar=[[]for i in range(a)]
for j in range(a):
    start=input()
    for q in range(len(start)):
        lar[j]+=[start[q]]
kok=0
for i in range(a):
    for j in range(b):
        if lar[i][j]=="#":
            kok+=1
w=0
num2=(2**a)*(2**b)
for i in range(num2):
    pop=[[0 for i in range(b+5)]for j in range(a+5)]
    num=0
    p=bin(i)[2:]
    e=p[::-1]
    for q in range(len(e)):
        if q-a<=-1 and e[q]=="1":
            for m in range(b):
                pop[q][m]=1
        if q-a>-1 and e[q]=="1":
            for j in range(a):
                pop[j][q-a]=1
    for i in range(a):
        for j in range(b):
            if lar[i][j]=="#" and pop[i][j]==0:
                num+=1
    if num==c:
        w+=1
print(w)

Submission status: Accepted

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

ans = 0
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 table[i][j] == '#': 
                    black = black + 1
        if black == k: 
            ans = ans + 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
H,W,K=map(int,input().split())
 
C=[]
 
for i in range(H):
  C.append(input())
 
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 sys
import math
h,w,k=map(int,input().split())
A =[input() for _ in range(h)]
ans=0

for iss in range(1<<h):
    for js in range(1<<w):
        cnt=0
        for i in range(h):
            for j in range(w):
                if iss>>i & 1: continue
                if js>>j & 1: continue
                if A[i][j]=='#': cnt+=1
        if cnt==k:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

h,w,k=map(int,input().split())
C = [input() for i in range(h)]
for biti in range(2**h):
  for bitj in range(2**w):
    count = 0
    for i in range(h):
      for j in range(w):
        if C[i][j] == "." or (biti >> i &1) or (bitj >> j & 1):count += 1
    if h*w-count == k:
      ans += 1
    # print(count)
print(ans)

Submission status: Accepted

Solution code:
from pprint import pprint
# pprint(C)
import sys
from collections import Counter
from itertools import product, combinations

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

C = []
for _ in range(H):
    C.append(input())

counter = Counter()
for row in C:
    counter.update(row)
n_blacks = counter['#']

if n_blacks < K:
    print(0)
    sys.exit()

ans = 0
# mask_row, mask_col の場合
for mask_row in range(1<<H):
    for mask_col in range(1<<W):
        black = 0
        # ボード (i, j) がマスク対象でなく、かつ黒かどうかみたい
        # きちんとした行(列)マスクの作成とかは諦めて、ボードのマスを総当りする
        for i in range(H):
            for j in range(W):
                # (i, j) のボード状態は元のCを使った方がらく
                if (mask_row >> i & 1) == 0 and (mask_col >> j & 1) == 0 and (C[i][j] == '#'):
                    black += 1
        # print('{:b} {:b} {}'.format(mask_row, mask_col, black))
        if black == K:
            ans += 1
        # b = '{:b}'.format(masked_board)

print(ans)

Submission status: Accepted

Solution code:
def main():
    h,w,k=map(int, input().split())
    grid = []
    l = [[0]*w for _ in range(h)]
    ten_g = [0]*(h)
    ten_r = [0]*(w)
    for i in range(h):
        s = list(input().rstrip())
        grid.append(s)
    res = 0
    for bi in range(2**(h+w)):
        tmp = 0
        for i in range(h):
            for j in range(w):
                if(bi & 1<<i and bi&(1<<h+j)):
                    if(grid[i][j]=="#"):
                        tmp+=1
        if(tmp == k):
            res+=1


    print(res)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!


#ord(s)
import copy

H, W, K = list(map(int, input().split()))
c = ["" for i in range(H)]
for i in range(H):
    c[i] = input()
ans = 0
for i in range(2**(H+W)):
    d = copy.deepcopy(c)
    
    for j in range(H):
        if (i >> j ) & 1 == 1:
            d[j] = "." * W
    for j in range(W):
        if (i >> (j + H) ) & 1 == 1:
            for k in range(H):
                
                d[k] = d[k][0:j] + "." + d[k][j+1:W] 
    count = 0
    for j in range(H):
        for k in range(W):
            if d[j][k] == "#":
                count += 1
                
    if count == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from pprint import pprint
# pprint(C)
import sys
from collections import Counter
from itertools import product, combinations

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

C = []
for _ in range(H):
    C.append(input())

counter = Counter()
for row in C:
    counter.update(row)
n_blacks = counter['#']

if n_blacks < K:
    print(0)
    sys.exit()


board = ''
for row in C:
    board += row

bitboard = 0b0
for cell_index in range(len(board)):
    digit = len(board) - cell_index - 1
    if board[cell_index] == '#':
        bitboard |= 0b1 << digit
    else:
        bitboard |= 0b0 << digit

# print(board)
# 2 3 2
# ..#
# ###
# >>> ..####
# print('{:b}'.format(bitboard))
# 2 3 2
# ..#
# ###
# >>> 1111

def get_row_base_mask(n_col):
    ret = 0b0
    for c in range(n_col):
        ret |= 0b1 << c
    return ret

col_base_mask = get_row_base_mask(W)
# print('{:b}'.format(col_base_mask))
# sys.exit()

def get_col_base_maak(n_row):
    ret = 0b0


ans = 0
for mask_row in range(1<<H):
    for mask_col in range(1<<W):
        # mask_row, mask_col の場合
        black = 0
        for i in range(H):
            for j in range(W):
                # (i, j) が黒かどうかみたい
                if (mask_row >> i & 1) == 0 and (mask_col >> j & 1) == 0 and (C[i][j] == '#'):
                    black += 1
        # print('{:b} {:b} {}'.format(mask_row, mask_col, black))
        if black == K:
            ans += 1
        # b = '{:b}'.format(masked_board)

print(ans)

Submission status: Accepted

Solution code:
def LI(): return map(int,input().split())
def I() :return int(input())

h,w,k=LI()
lst=[]
cnt=0
for i in range(h):
    lst+=[list(input())]
    for j in range(w):
        if lst[i][j]=="#":
            cnt+=1
black=0
ans=0
for rows in range(1<<h):
    for cols in range(1<<w):
        black=0
        for i in range(h):
            if (rows>>i)&1:continue
            for j in range(w):
                if (cols>>j)&1:continue
                elif lst[i][j]=="#":
                    black +=1
                    # print(i,j)

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

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
chw = [input() for _ in range(h)]
  
answer = 0
for col in range(2**h):
  for row in range(2**w):
    black = 0
    for i in range(h):
      for j in range(w):
        if ((col >> i) & 1) and ((row >> j) & 1) and (chw[i][j] == "#"):
          black = black +1

    if black == k:
      answer += 1

print(answer)

Submission status: Accepted

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

rows = []
cols = []
for i in range(H):
    temp = 0
    for j in range(W):
        if M[i][j] == '#':
            temp += 1
    rows += [temp]

for j in range(W):
    temp = 0
    for i in range(H):
        if M[i][j] == '#':
            temp += 1
    cols += [temp]
#print(rows,cols)
total = sum(rows)
ans = 0
for i in range(2**H):
    s1 = "0"*(H-len(bin(i)[2:]))+bin(i)[2:]    
    for j in range(2**W):
        s2 = "0"*(W-len(bin(j)[2:]))+bin(j)[2:]
        delete = 0
        for p in range(H):
            if s1[p] == "1":
                    delete += rows[p]
        for q in range(W):
            if s2[q] == '1':
                delete += cols[q]
        
        for p in range(H):
            for q in range(W):
                if s1[p] == "1" and s2[q] == "1":
                    if M[p][q] == "#":
                        delete -= 1
        if total - delete == K:
            #print(s1,s2,delete,total)
            ans += 1
print(ans)

Submission status: Accepted

Solution code:

def convert(i,n):
    arr = []
    for k in range(n):
        arr = [i%2]+arr
        i = int(i/2)
    return arr

def copy(a,n,m):
    arr = [[0 for i in range(m)] for j in range(n)]
    for i in range(n):
       for j in range(m):
           arr[i][j] = a[i][j]
    return arr

def main():
    h,w,k = map(int,input().split())
    c = [['' for j in range(w)] for i in range(h)]
    for i in range(h):
        s = input()
        for j in range(w):
            c[i][j] = s[j]
    H = 2**h
    W = 2**w

    ans = 0
    for row in range(H):
        for col in range(W):
            t = copy(c,h,w)
            #print(t)
            rowb = convert(row,h)
            colb = convert(col,w)
            #print(rowb)
            #print(colb)
            for i in range(h):
                if rowb[i]==1:
                    for j in range(w):
                        t[i][j] = '_'
            for j in range(w):
                if colb[j]==1:
                    for i in range(h):
                        t[i][j] = '_'
            #print(t)
            black = 0
            for i in range(h):
                black += t[i].count('#')

            if black==k:
                ans += 1

    print(ans)
    return
                    
    
    

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import copy
from itertools import product
h, w, k = map(int, input().split())
C = [list(input()) for _ in range(h)]
C = np.array(C)

cnt = 0
# 行と列を分けて考えるとループが入り組むので
# 行も列も一緒くたにproductで生成してループひとつで済ませる
for p in product([True, False], repeat=(h+w)):
    c = copy.deepcopy(C)
    c = np.array(c)
    for i, v in enumerate(p):
        if i < h and v:
            c[i, :] = "$"
        elif v:
            c[:, i - h] = "$"
    if np.count_nonzero(c == "#") == k:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import copy
import numpy as np

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

result = 0
table = []
for i in range(h):
  table.append(list(input()))

totalBlackCount = 0
for i in range(h):
  for j in range(w):
    if table[i-1][j-1] == '#':
      table[i-1][j-1] = 0
      totalBlackCount += 1
    else:
      table[i-1][j-1] = 1
npTable = np.asarray(table)

rowPattern = []
columnPattern = []
rowCount = 0
columnCount = 0
for i in range(2**h):
  rowPattern.append(list(format(rowCount, str('0')+str(h)+'b')))
  rowCount += 1
for i in range(2**w):
  columnPattern.append(list(format(columnCount, str('0')+str(w)+'b')))
  columnCount += 1

rowRed = []
rowBlack = []
columnRed = []
columnBlack = []
for i in range(h):
  columnRed.append(1)
  columnBlack.append(0)
for i in range(w):
  rowRed.append(1)
  rowBlack.append(0)

for i in range(2**h):
  npCalcTable = copy.deepcopy(npTable)
  rowBit = rowPattern[i-1]
  rowColorTable = []
  for j in range(h):
    if rowBit[j] == '0':
      rowColorTable.append(rowBlack)
    else:
      rowColorTable.append(rowRed)
  npRowColorTable = np.asarray(rowColorTable)
  for j in range(2**w):
    columnBit = columnPattern[j-1]
    columnColorTable = []    
    for k in range(w):
      if columnBit[k-1] == '0':
        columnColorTable.append(columnBlack)
      else:
        columnColorTable.append(columnRed)
    npColumnColorTable = np.asarray(columnColorTable).T
    npColorTable = npRowColorTable | npColumnColorTable
    npDiffTable = npColorTable | npCalcTable

    if np.sum(npDiffTable) == int(redK):
      result += 1
print(result)

Submission status: Accepted

Solution code:
h,w,K=map(int,input().split())
s=[list(input())for i in range(h)]
import numpy as np
s=np.array(s)
l=[]
for i in range(h):
    l.append(len(s[i][s[i]=="#"]))
for i in range(w):
    l.append(len(s[:,i][s[:,i]=="#"]))
ss=sum(l)//2
n=h+w
ans=0
for i in range(1<<n):
    tmp=ss
    for j in range(h):
        if i>>j&1:
            tmp-=l[j]
    for j in range(h,n):
        if i>>j&1:
            tmp-=l[j]
            for idx,k in enumerate(s[:,j-h]):
                if k=="#":
                    if i>>idx&1:
                        tmp+=1
    if tmp==K:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
A = [input() for _ in range(h)]
ans = 0
for gyou in range(2**h):
  for retsu in range(2**w):
    black = 0
    for x in range(h):
      for y in range(w):
        if ((gyou >> x) & 1) == 0 and ((retsu >> y) & 1) == 0 and A[x][y] == "#":
          black = black + 1
    if black == k:
      ans = ans + 1
print(ans)

Submission status: Accepted

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

import itertools
import copy

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

wlist = list(itertools.product([0, 1], repeat=W))
hlist = list(itertools.product([0, 1], repeat=H))

ans = 0 
for h in hlist:
    for w in wlist:
        black = 0 
        for i in range(H):
            for j in range(W):
                if h[i] == w[j] == 1 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())
M=[input()for i in range(H)]
ans=0

for i in range(2**(H+W)):
    h=i%(2**H)
    w=i//(2**H)
    count=0
    for x in range(H):
        if (2**x) & h == 0:
            continue
        for y in range(W):
            if (2**y) & w == 0:
                continue
            if M[x][y]=='#':
                count+=1
    if count==K:
        ans+=1
print(ans)

Submission status: Accepted

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

import sys

def main():
    input = sys.stdin.readline
    h, w, k = map(int, input().split())
    C = []
    for _ in range(h):
        C.append(input())
    ans = 0

    for hbit in range(1<<h): # red row bit h = 2なら 00 ~ 11 100(=2^2)　左ビットシフト 1 -> 100
        for wbit in range(1<<w): # red col bit
            c = 0
            for i in range(h):
                for j in range(w):
                    #9 = 0b1001　を 右ビットシフト　9 >> 1 にすると 100
                    #i, jだけそれぞれ右ビットシフトした時に1になっていたらフラグが立っている.
                    #この実装だと 1だと上書きしないパターン
                    if hbit>>i & 1 and wbit>>j & 1:
                        if C[i][j] =='#': c += 1
            if c == k: ans += 1
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
c = [list(input()) for _ in range(h)]
ans = 0
#全探索
for ib in range(1<<h): #縦の部分を調べる
    for jb in range(1<<w): #横の部分を調べる
        black = 0
        for i in range(h):
            if ib&(1<<i):continue #縦のi番目が１かどうか見る
            for j in range(w):
                if jb&(1<<j):continue #横のj番目が１かどうか見る
                black += c[i][j]=="#"
        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)]
cnt = 0

for i in range(2 ** H):
    for j in range(2 ** W):
        black = 0
        for x in range(H):
            for y in range(W):
                if ((i >> x) & 1) and ((j >> y) & 1) and C[x][y] == "#":
                    black += 1
        if black == K:
            cnt += 1
print(cnt)

Submission status: Accepted

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

import itertools
import copy

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

clist = list(itertools.product([0, 1], repeat=H+W))
#print(clist)

ans = 0 
for q in clist:
    black = 0 
    h = q[:H]
    w = q[H:]
    # print('h =', h)
    # print('w =', w)
    # print()

    for i in range(H):
        for j in range(W):
            if h[i] == w[j] == 1 and c[i][j] == '#':
                black += 1
    if black == k:
        ans += 1

print(ans)

Submission status: Accepted

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

c = [None] * H

for i in range(H):
  c[i] = list(input())

res = 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) == 0 and ((w >> j) & 1) == 0 and c[i][j] == '#':
          cnt += 1
    #print(cnt)
    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)]

#print(c)

ans = 0
for R in range(2**H):
  for C in range(2**W):
    n = 0
    for y in range(H):
      for x in range(W):
        if C>>x&1 and R>>y&1:
          if c[y][x]=="#":
            n += 1
    if n==K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

ans=0
for mask_H in product([True,False],repeat=H):
    for mask_w in product([True,False],repeat=W):
        black=0
        for i in range(H):
            for j in range(W):
                if mask_H[i] and mask_w[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())
masu = [list(input()) for _ in range(H)]

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

Submission status: Accepted

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

for ib in range(1<<h):
    for jb in range(1<<w):
        cnt = 0
        for i in range(h):
            for j in range(w):
                if ib>>i&1: continue
                if jb>>j&1: continue
                if s[i][j] == '#':
                    cnt+=1
        if cnt == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

cnt = 0
for rh in range(H):
    for rw in range(W):
        for h in combinations(range(H), rh):
            for w in combinations(range(W), rw):
                T = [c[:] for c in C]
                for hi in h:
                    T[hi] = list("." * W)
                for wj in w:
                    for i in range(H):
                        T[i][wj] = "."
                if K == sum(t.count("#") for t in T):
                    cnt += 1

print(cnt)

Submission status: Accepted

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

ls = []
for i in range(h):
    ls.append(str(input()))


ns = np.zeros((h,w),dtype = int)
for i in range(h):
    for j in range(w):
        if ls[i][j] == "#":
            ns[i][j] = 1

ans = 0
for i in range(2** h):
    for j in range(2 ** w):
        black = 0
        for x in range(h):
            for y in range(w):
                if (i >> x) & 1 == 0 and (j >> y) & 1 == 0:
                    if ns[x][y] == 1:
                        black += 1
        if black == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
h,w,k = map(int, input().split())
g = []
for _ in range(h):
  g.append(input())
ans = 0
for i in list(itertools.product([0,1], repeat=h)):
  for j in list(itertools.product([0,1], repeat=w)):
    e = 0
    for x in range(h):
      for y in range(w):
        if i[x] == 1 and j[y] == 1 and g[x][y]=='#':
          e+=1
    if e==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 x in range(h):
      for y in range(w):
        if i>>x&1:continue
        if j>>y&1:continue
        if c[x][y]=="#":cnt+=1
    if cnt==k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy
h,w,K=map(int,input().split())
maze=[]
for i in range(h):
    line=list(input())
    maze.append(line)
ans=0
for i in range(2**(w+h)):
    g=[]
    r=[]
    for j in range(w+h):
        if i&(1<<j) and j<h:
            g.append(j)
        if i&(1<<j) and j>=h:
            r.append(j-h)
    tmp=copy.deepcopy(maze)
    cnt=0
    for k in range(h):
        for l in range(w):
            if k in g or l in r:
                continue
            if tmp[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 _ in range(H)]

lit = []
for i in range(2 ** H):
    for j in range(2 ** W):
        row = str(bin(i))[2:].zfill(H)
        col = str(bin(j))[2:].zfill(W)
        lit.append([row, col])
# print(len(lit))
# print(lit)

black = sum([c.count('#') for c in C])
# print(black)

# 000011 000111 4 6 8 NG
res = 0
for row, col in lit:
# for row, col in [['000011', '000111']]:
    ans = black
    black_row = 0
    black_col = 0
    for i, r in enumerate(row):
        if r == '1':
            ans -= C[i].count('#')
            black_row += C[i].count('#')
        # print(ans)

    for j, c in enumerate(col):
        if c == '1':
            for k in range(H):
                if row[k] == '1':
                    continue
                if C[k][j] == '#':
                    ans -= 1
                    black_col += 1
    # print(row, col, black_row, black_col, ans)
    if ans == K:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import math
import sys
from itertools import combinations 
import itertools

def main():
    h, w, n = list(map(int, input().split()))
    c = [input() for _ in range(h)]
    ans = 0
    black = 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:
                        if c[k][l] == "#":
                            black += 1
            if black == n:
                ans += 1
    print(ans)
    
main()

Submission status: Accepted

Solution code:
from itertools import product
h,w,k=map(int,input().split())
f=0
c=[]
for i in range(h):
  tmp=list(input())
  c.append(tmp)
  f+=tmp.count("#")
ans=0
for i in product([0,1],repeat=h):
  for j in product([0,1],repeat=w):
    cnt=0
    for x in range(h):
      for y in range(w):
        if i[x]==1 or j[y]==1:
          if c[x][y]=="#":cnt+=1
    if f-cnt==k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W, K = map(int, rl().split())
    c = [list(rl().rstrip()) for _ in range(H)]
    
    ans = 0
    for sh in range(1 << H):
        for sw in range(1 << W):
            cc = deepcopy(c)
            for y in range(H):
                if sh >> y & 1:
                    for x in range(W):
                        cc[y][x] = '.'
            for x in range(W):
                if sw >> x & 1:
                    for y in range(H):
                        cc[y][x] = '.'
            cnt = 0
            for y in range(H):
                for x in range(W):
                    cnt += cc[y][x] == '#'
            ans += cnt == K
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    h, w, k = geta(int)
    c = []
    for _ in range(h):
        c.append(gete())

    ans = 0
    for bi in range(1 << h):
        for bj in range(1 << w):

            rem = 0
            for i in range(h):
                if bi >> i & 1 == 1:
                    continue
                for j in range(w):
                    if bj >> j & 1 == 1:
                        continue
                    if c[i][j] == "#":
                        rem += 1

            if rem == k:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
bk = 0
pt1 = []
pt2 = []

for i in range(2 ** h):
    tmp1 = [False] * (h)
    for j in range(h):
        if i >> j & 1:
            tmp1[j] = True
    pt1.append(tmp1)

for i in range(2 ** w):
    tmp2 = [False] * (w)
    for j in range(w):
        if i >> j & 1:
            tmp2[j] = True
    pt2.append(tmp2)

for i in range(len(pt1)):
    for j in range(len(pt2)):
        for x in range(h):
            if (pt1[i][x]==True):
                bk = bk + s[x][0].count('#')
        
        for y in range(w):
            if (pt2[j][y]==True):
                for z in range(h):
                    if (pt1[i][z]==True and s[z][0][y]=='#'):
                        bk == bk
            else:
                for z in range(h):
                    if (pt1[i][z]==True and s[z][0][y]=='#'):
                        bk -= 1

        if bk == k:
            ans += 1
        #print(pt1[i],pt2[j],bk)
        bk = 0

print(ans)

Submission status: Accepted

Solution code:
def main():
    H,W,K = [int(x) for x in input().split()]

    B = 0
    BH = [0]*H
    BW = [0]*W
    BHW = []
    for h in range(H):
        BHW.append([0]*W)
    for i in range(H):
        C = list(input())
        for j in range(W):
            if C[j] == '#':
                B += 1
                BH[i] += 1
                BW[j] += 1
                BHW[i][j] = 1

    cnt = 0
    for ibit in range(0,1<<H):
        for jbit in range(0,1<<W):
            ib = 0
            jb = 0
            ijb = 0
            for i in range(H):
                if (1<<i) & ibit:
                    ib += BH[i]
            for j in range(W):
                if (1<<j) & jbit:
                    jb += BW[j]
            for i in range(H):
                for j in range(W):
                    if (1<<i) & ibit and (1<<j) & jbit:
                        ijb += BHW[i][j]
            b = B - ib - jb + ijb
            if K == b:
                cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == '__main__':
  h,w,k=map(int,input().strip("\n").split())
  s=[]
  for i in range(h):
    s.append(list(input().strip("\n")))
  ans=0
  #print(s)
  # 2 -> 100 rangeだから11まで
  for iS in range(1<<h):
    # 3->1000=2^3=8
    for js in range(1<<w):
      #print(iS,js)
      cnt=0
      for i in range(h):
        for j in range(w):
          # 赤で塗る場合
          # ex)iS=01,i=0->i+1桁目が1か
          if iS>>i&1: continue
          if js>>j&1: continue
          if s[i][j]=='#': cnt+=1
      if cnt==k: ans+=1

  print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
G = [list(input()) for _ in range(H)]
ans = 0
for rows in range(2**H):
    for cols in range(2**W):
        black = 0
        for i in range(H):
            if rows >> i & 1:
                continue
            for j in range(W):
                if cols >> j & 1:
                    continue
                if G[i][j] == '#':
                    black += 1
        if black == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import sys
read = sys.stdin.read
def main():
    h, w, k = map(int, input().split())
    c = []
    for _ in range(h):
        row = [c == '#' for c in list(input())]
        c.append(row)
    r = 0
    p1 = tuple(product((0, 1), repeat=w))
    p2 = tuple(product((0, 1), repeat=h))
    pat = tuple(product(p1, p2))
    for pe in pat:
        t = 0
        for x, col in enumerate(pe[0]):
            for y, row in enumerate(pe[1]):
                t += col * row * c[y][x]
        if t == k:
            r += 1
    print(r)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

C = []
for i in range(H):
    C.append(input())

ans = 0

for h_ in range(2 ** H):
    h_b = format(h_, '0' + str(H) + 'b')
    for w_ in range(2 ** W):
        w_b = format(w_, '0' + str(W) + 'b')
        
        b_count = 0
        for h in range(H):
            for w in range(W):
                if h_b[h] == "0" and w_b[w] == "0" and C[h][w] == "#":
                    b_count += 1
        if b_count == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

h,w,k = (int(x) for x in input().split())
c = np.array([list(input()) for x in range(h)])
answer = 0


for x,y in itertools.product(range(2**h), range(2**w)):
    count = 0
    for i,j in itertools.product(range(h), range(w)):
        if x>>i &1 or y>>j&1:continue
        if c[i,j]=="#":
            count+=1
    if count == k:
        answer += 1
        
print(answer)