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

for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            Array[i][j] = 1
LH = range(H)
LW = range(W)
CH = []
CW = []
Ans = 0
for i in range(H+1):
    for combi in itertools.combinations(LH, i):
        CH.append(list(combi))
for i in range(W+1):
    for combi in itertools.combinations(LW, i):
        CW.append(list(combi))
for ch in CH:
    for cw in CW:
        Sum = 0
        for i in range(H):
            for j in range(W):
                if not (i in ch or j in cw):
                    Sum += Array[i][j]
        if Sum == K:
            Ans += 1
print(Ans)

Submission status: Accepted

Solution code:
import copy
from itertools import combinations
h, w, k = map(int, input().split())
c =[input() for i in range(h)]
ans = 0
y = []
for i in range(h):
    y.append(i)
x = []
for i in range(w):
    x.append(i)
for i in range(h+1):
    ty = list(combinations(y, i))
    for j in range(w+1):
        tx = list(combinations(x, j))
        for l in ty:
            for m in tx:
                cnt = 0
                for p in l:
                    for q in m:
                        if c[p][q] == '#':
                            cnt += 1
                if cnt == k:
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

H,W,K = map(int,input().split())
Map = []
for i in range(H):
  c = list(input())
  tmp = []
  for j in range(W):
    if(c[j] == '.'): tmp.append(0)
    else: tmp.append(1) 
  Map.append(tmp)
  
# 全探索
# i番目の列または行を選ぶ
A = list(itertools.product([0,1],repeat=H))
B = list(itertools.product([0,1],repeat=W))

ans = 0
for a_l in A:
  for b_l in B:
    tmp_Map = copy.deepcopy(Map)
    
    for a in range(len(a_l)):
      if(a_l[a] == 1):
        # a行目を0にする
        for j in range(W):
         tmp_Map[a][j] = 0
        
    for b in range(len(b_l)):
      if(b_l[b] == 1):
        # b列目を0にする
        for i in range(H):
         tmp_Map[i][b] = 0
        
    # 残っている1がK個のときans+1
    tmp = 0
    for i in range(H):
      tmp += sum(tmp_Map[i])
      
    if(tmp == K):
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
lists = [input() for i in range(H)]
black, ans = 0, 0
tate, yoko = [0 for i in range(H)],  [0 for i in range(W)]
listskai = [[0 for j in range(W)]for i in range(H)]

for i in range(W):
    for j in range(H):
        if lists[j][i] == '#':
            black += 1
            tate[j] += 1
            yoko[i] += 1
            listskai[j][i] = 1

def tmp(times, num, max, lista, numa):
    if times == 0:
        return lista + [num]

    for tmpi in range(numa + 1, max):
        if tmpi not in num:
            lista = tmp(times - 1, num + [tmpi], max, lista, tmpi)
    return lista

kurono = black

for looph in range(H):
    for j in tmp(looph, [], H, [], -1):
        for loopw in range(W):
            for i in tmp(loopw, [], W, [], -1):
                kurono = black
                for k in i:
                    kurono -= yoko[k]
                    for d in j:
                        kurono += listskai[d][k]

                for d in j:
                    kurono -= tate[d]

                if kurono == K:
                    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy

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

    ans = 0

    for bitH in range(2**(H) - 1):
        for bitW in range(2**(W) - 1):
            Ctmp = copy.deepcopy(C)
            for i in range(H):
                if((bitH >> i) & 1):
                    Ctmp[i] = ["x" for _ in range(W)]
            Ctmp_t = [list(x) for x in zip(*Ctmp)]
            
            for j in range(W):
                if((bitW >> j) & 1):
                    Ctmp_t[j] = ["x" for _ in range(H)]
            
            Clast = [list(x) for x in zip(*Ctmp_t)]
            
            cnt = 0
            
            for s in range(H):
                cnt += Clast[s].count("#")
            
            if cnt == K:
                ans += 1
            
            # for i in range(H):

            # #     print(Clast[i])
            # # print(bitH, bitW)
            # # print(cnt)
    print(ans)

solve()

Submission status: Accepted

Solution code:
import itertools
h, w, k = map(int, input().split())
field = []
for i in range(h):
  field.append(list(input()))
  
hb = [0 for i in range(h)]
wb = [0 for j in range(w)]
slist = []
tlist = []
bl = 0
ans = 0

for i in range(h):
  for j in range(w):
    if field[i][j] == "#":
      hb[i] += 1
      wb[j] += 1
      bl += 1

for i in range(h):
  for s in itertools.combinations(range(h), i):
    tmp = 0
    for es in s:
      tmp += hb[es]
    slist.append([list(s), tmp])
    
for j in range(w):
  for t in itertools.combinations(range(w), j):
    tmp = 0
    for et in t:
      tmp += wb[et]
    tlist.append([list(t), tmp])

    
for s in slist:
  for t in tlist:
    tmp = s[1] + t[1]
    if s and t:
      for es in s[0]:
        for et in t[0]:
          if field[es][et] == "#":
            tmp -= 1
    if bl - tmp == k:
      ans += 1
      
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
import numpy as np
H,W,K = map(int,input().split())
C = [list(input()) for h in range(H)]
D = np.zeros((H,W),dtype=np.int)
a = 0

for h in range(H):
  for w in range(W):
    if C[h][w]=="#":
      D[h][w]=1

T = np.sum(D)

for h in range(1+H):
  for I in combinations(range(H),h):
    for w in range(1+W):
      for J in combinations(range(W),w):
        S = 0
        
        for i in I:
          for w in range(W):
            S+=D[i][w]
        for j in J:
          for h in range(H):
            S+=D[h][j]
        for i in I:
          for j in J:
            S-=D[i][j]
        
        if K==T-S:
          a+=1

print(a)

Submission status: Accepted

Solution code:
import numpy as np
H, W, K = map(int, input().split())
c = []
for i in range(H):
  s = str(input())
  l = [0 if t=='.' else 1 for t in s]
  c.append(l)
c = np.array(c)

ans = 0
tmp = c
for i in range(2**H-1):
  for j in range(H):
    if i >> j & 1:
      tmp[j] = 0
  tm = tmp
  for a in range(2**W-1):
    for b in range(W):
      if a >> b & 1:
        tmp[:, b] = 0
    t = np.sum(tmp)
    if t == K:
      ans += 1
    tmp = np.array(tm)
  tmp = np.array(c)
print(ans)

Submission status: Accepted

Solution code:
import itertools

H, W, K = map(int, input().split())
c = [['.' for j in range(6)] for i in range(6)]
for i in range(H):
    tmp = str(input())
    for j in range(len(tmp)):
        c[i][j] = tmp[j]
    
hp = list(itertools.product([0,1], repeat=H))
wp = list(itertools.product([0,1], repeat=W))

hl = []
for elem in hp:
    hl.append([i for i, x in enumerate(list(elem)) if x == 1])
wl = []
for elem in wp:
    wl.append([i for i, x in enumerate(list(elem)) if x == 1])

# print(hl)
# print(wl)


def func(hli, wli, c):
    tmp = 0
    for i in range(len(hli)):
        for j in range(len(wli)):
            if c[hli[i]][wli[j]] == '#':
                tmp += 1 
            
    return tmp


ans  = 0
for hli in hl:
    for wli in wl:
        if func(hli, wli, c) == K:
            ans += 1


print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
l = []
total = 0

for _ in range(h):
    c = list(input())
    total += c.count('#')
    l.append(c)
    
ans = 0
for i in range(2**h):
    count1 = 0
    li = []
    for j in range(h):
        if ((i>>j)&1):
            li.append(j)
            count1 += l[j].count('#')
    for a in range(2**w):
        count2 = 0
        for b in range(w):
            if ((a>>b)&1):
                for z in li:
                    if l[z][b] == "#":
                        count2 -= 1
                for c in range(h):
                    if l[c][b] == "#":
                        count2 += 1
        if total - count1 - count2 == k:
          ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
c = [list(input()) for _ in range(H)]
digit = H + W
sum_b = 0
for x in c:
    sum_b += x.count('#')

brack = []
for i in range(H):
    for j in range(W):
        if c[i][j] == '#':
            brack.append(int(str(10**(H+j)+10**i).zfill(digit), 2))

ans = 0
for i in range(2**digit):
    tmp = 0
    for j in brack:
        if i & j != 0: tmp += 1
    if sum_b - tmp == K: ans += 1    
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import Counter
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, W, K = map(int, readline().split())
    C = read().split()
    black = 0
    low = [0]*H
    column = [0]*W
    for h in range(H):
        c = C[h]
        b = c.count('#')
        black += b
        low[h] = b
        for w in range(W):
            if c[w]=='#':
                column[w]+=1
    ans = 0
    for i in range(2**H):
        for j in range(2**W):
            loss = 0
            for h in range(H):
                if ((i>>h)&1)==1:
                    loss += low[h]
                    for w in range(W):
                        if ((j>>w)&1) == 1:
                            if C[h][w]=='#':
                                loss -= 1
            for w in range(W):
                if ((j >> w)&1) == 1:
                    loss += column[w]
            if black-loss == K:
                ans += 1
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

def li():
    return [int(x) for x in input().split()]

H, W, K = li()
c = [list(input()) for x in range(H)]

def checkCount(m):
    cnt = 0
    for l in m:
        cnt += l.count('#')
    return cnt

result = 0
for h in range(H+1):
    comh = list(combinations(range(H),h))
    sm = 0
    for x in comh:
        cr = [c[i] if i not in x else [0]*W for i in range(H)]
        crt = np.array(cr).T.tolist()
        for w in range(W+1):
            comw = list(combinations(range(W),w))
            for y in comw:
                z = [crt[j] for j in range(W) if j not in y]
                if checkCount(z) == K:
                    result += 1

print(result)

Submission status: Accepted

Solution code:
from itertools import combinations
from copy import deepcopy
h,w,d = map(int,input().split())
c = []
kuro = 0
for i in range(h):
    s = list(input())
    kuro += s.count("#")
    c.append(s)
ans = 0
for i in range(h):
    for j in range(w):
        for k in combinations(range(h),r=i):
            for l in combinations(range(w),r=j):
                data = deepcopy(c)
                num = 0
                for m in k:
                    for a in range(w):
                        if data[m][a] == "#":
                            data[m][a] = "."
                            num += 1
                for n in l:
                    for b in range(h):
                        if data[b][n] == "#":
                            num += 1
                if kuro-num == d:
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
row,col,kkk = map(int,input().split())
matrix = []
for i in range(row):
  matrix.append(list(input()))
combination = set()
rowcol=[]
for i in range(row):
  rowcol.append((i,0))
for i in range(col):
  rowcol.append((i,1))
  
def find(index,temp):
    if index==len(rowcol):
      combination.add(tuple(copy.deepcopy(temp)))
      return 
    find(index+1,temp+[rowcol[index]])
    find(index+1,temp)
find(0,[])
new = set()
combination = list(combination)
for i in combination:
  i = list(i)
  i.sort()
  i = tuple(i)
  new.add(i)
ans = 0
for i in new:
  #i is list of row col to be painted red
  tempmatrix = copy.deepcopy(matrix)
  for j in i:
    #j is tuple of row and col to be painter
    temp,flag = j
    if flag == 0:
        for k in range(col):
          tempmatrix[temp][k] = 0
    if flag == 1:    
        for l in range(row):
            tempmatrix[l][temp] = 0
  #now check black counte
  black = 0
  for m in range(row):
    for n in range(col):
      if tempmatrix[m][n] == "#":
        black += 1
  if black == kkk:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
a = list(map(int,input().split()))
b = [input() for l in range(a[0])]
ans = 0
cnt = 0
allcnt = 0
nongyou = []
cnt2 = 0
for i in range(a[0]):
    allcnt += b[i].count('#')

for i in range(2 ** a[0]):
    cnt = allcnt
    nongyou = []
    for j in range(a[0]):
        if ((i >> j) & 1):
            cnt -= b[j].count('#')
            nongyou.append(j)
    for m in range(2 ** a[1]):
        cnt2 = cnt
        for n in range(a[1]):
            if ((m >> n) & 1):
                for k in range(a[0]):
                    if k in nongyou:
                        continue
                    else:
                        cnt2 -= b[k][n].count('#')                  
        if cnt2 == a[2]:
            ans += 1

print(str(ans))

Submission status: Accepted

Solution code:
import sys
import numpy as np
from itertools import combinations
from itertools import product

height, width, black = map(int, sys.stdin.readline().split())
mat = np.array([list(input()) for _ in range(height)])
n_black_remove = np.sum(mat == "#") - black
n_black_row = np.array([np.sum(mat[row, :] == "#") for row in range(height)])
n_black_col = np.array([np.sum(mat[:, col] == "#") for col in range(width)])
result = 0

for n_delete_row in range(height+1):
    for n_delete_col in range(width+1):
        for combi_row in combinations(range(height), n_delete_row):
            for combi_col in combinations(range(width), n_delete_col):
                remove = 0
                if combi_row:
                    remove += np.sum(n_black_row[list(combi_row)])
                if combi_col:
                    remove += np.sum(n_black_col[list(combi_col)])
                for r, c in product(combi_row, combi_col):
                    if mat[r][c] == "#":
                        remove -= 1
                if remove == n_black_remove:
                    result += 1
print(result)

Submission status: Accepted

Solution code:
import itertools
import copy
h,w,k=map(int,input().split())
c = [list(input()) for _ in range(h)]
x = itertools.product(range(2) , repeat=h+w)
ans = [0] * (h+w)

tmp = []
for q in x:
  tmp = copy.deepcopy(c)
  for i in range(h):
    if q[i] == 1:
      tmp[i] = ["r"] * w
    else :
      tmp[i] = copy.deepcopy(c[i])

  for j in range(w):
    if q[h+j] == 1:
      for i in range(h):
        tmp[i][j] = "r"
  tans = 0
  for i in range(h):
    for j in range(w):
      tans += tmp[i][j].count("#")
  ans.append(tans)
cnt = 0

for a in ans:
  if a == k :
    cnt += 1
  
print(cnt)

Submission status: Accepted

Solution code:
def countRowColumn(color):
    blackr = []
    for i in range(row):
        blackr.append(color[i].count('#'))
    blackc = []
    for i in range(col):
        c = 0
        for j in range(row):
            if color[j][i]=='#':
                c+=1
        blackc.append(c)
    
def counting(color):
    t=0
    for c in color:
        t+=c.count('#')
    return t
def func(color,setr,setc,r,c):
    counts = counting(color)
    if counts<k:
        return 0
    if counts==k:
        dp.add((tuple(sorted(setr)),tuple(sorted(setc))))
    #if r==row or c==col:
    #    return 0
    for i in range(r,row):
        temp = []
        for j in range(col):
            temp+=[color[i][j]]
            color[i][j]='R'
        setr.add(i)
        func(color,setr,setc,i+1,c)
        setr.remove(i)
        for j in range(col):
            color[i][j]=temp[j]
    for j in range(c,col):
        temp = []
        for i in range(row):
            temp+=[color[i][j]]
            color[i][j]='R'
        setc.add(j)
        func(color,setr,setc,r,j+1)
        setc.remove(j)
        for i in range(row):
            color[i][j]=temp[i]
    return 0
    
dp = set()
row, col, k = map(int,input().split())
color = []
blackr = []
for _ in range(row):
    color.append(list(input()))
    blackr.append(color[-1].count('#'))
blackc = []
for i in range(col):
    c = 0
    for j in range(row):
        #print(j,i)
        if color[j][i]=='#':
            c+=1
    blackc.append(c)
total = sum(blackr)
#print(total)
if total<k:
    print(0)
else:
    func(color,set(),set(),0,0)
    print(len(dp))

Submission status: Accepted

Solution code:
import itertools

h, w, k = tuple(map(int, input().split()))
k2 = k
c = ''
for _ in range(h):
    c += input()

grid = []
for i in c:
    if i == '#':
        grid.append(1)
    else:
        grid.append(2)

ans = 0
for i in range(h+1):
    for j in list(itertools.combinations(range(h), i)):
        for k in range(w+1):
            for l in list(itertools.combinations(range(w), k)):
                tmp = grid[:]
                for j2 in j:
                    tmp[w*j2:w*(j2+1)] = [3] * w
                for l2 in l:
                    tmp[l2::w] = [3] * h
                if tmp.count(1) == k2:
                    ans += 1

print(ans)

Submission status: Accepted

Solution code:
# 幅優先探索（行きがけ）
import collections
import sys
import copy
import re


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


def main():
    H, W, K = LI()
    c = []

    N = H+W
    for i in range(H):
        c.append(list(S()))

    ans = 0
    for i in range(2**N):
        cow = []
        row = []
        cCopy = copy.deepcopy(c)
        blacks = 0
        for j in range(N):
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                if j >= W:
                    row.append(j)
                else:
                    cow.append(j)
        for h in range(H):
            if (h+W) in row:
                continue
            else:
                for w in range(W):
                    if w in cow:
                        continue
                    if cCopy[h][w] == "#":
                        blacks += 1

        if blacks == K:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools
H, W, K = map(int, input().split())
ans = 0
c = []
for _ in range(H):
  c.append(list(input()))
c = np.array(c)

for l in list(itertools.product([True,False], repeat=H)):
  for l2 in list(itertools.product([True,False], repeat=W)):
    c2 = c.copy()
    c2[l, :] = 'R'
    c2[:, l2] = 'R'
    if (c2== '#').sum() == K:
      ans += 1

print(ans)

Submission status: Accepted

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


l=0

for i in range(2**W):
    q=str(format(i, '0{}b'.format(W)))
    
    #print(q)
    b=copy.deepcopy(a)
    
    for u in range(W):
        if q[u]=='1':
            for y in range(H):
                b[y][u]='&'
                
    for i in range(2**H):
        c=copy.deepcopy(b)
        num=0
        e=str(format(i, '0{}b'.format(H)))
        for t in range(H):
            if e[t]=='1':
                for y in range(W):
                    c[t][y]='.'
        
        num=0
        for h in range(H):
                for w in range(W):
                    if c[h][w]=='#':
                        num+=1
        if num==K:
            l+=1
print(l)

Submission status: Accepted

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

cc = []
for i in range(h):
    cc.append([])
    for j in range(w):
        cc[i].append(c[i][j])

ccc = []
for i in range(h):
    ccc.append([])
    for j in range(w):
        ccc[i].append(c[i][j])

import copy

# ccc = copy.copy(cc)

# print(cc)
cnt2 = 0
for i in range(2**h):
    for j in range(2**w):
        
        cc = copy.deepcopy(ccc)
        ii = bin(i)[2:].zfill(h)
        jj = bin(j)[2:].zfill(w)
        # print(ii)
        # print(jj)
        for k in range(len(ii)):
            if ii[k] == '1':
                for l in range(w):
                    cc[k][l] = '0'
        for k in range(len(jj)):
            if jj[k] == '1':
                for l in range(h):
                    cc[l][k] = '0'
        cnt = 0
        for k in range(h):
            for l in range(w):
                if cc[k][l] == '#':
                    cnt += 1
        if cnt == kk:
            cnt2 += 1
            # print(cc)
        # print(cc)
print(cnt2)

Submission status: Accepted

Solution code:

H,W,K=map(int,input().split())
C=[]
for i in range(H):
  tmp=input()
  C+=[tmp]
ans=0
Hlis=[0 for i in range(H)]
Wlis=[0 for j in range(W)]
def Hsin(n):
  t=H-1
  while t>0:
    tmpo=n//(2**t)
    Hlis[H-1-t]=tmpo
    n=n%(2**t)
    t-=1
  Hlis[-1]=n
  return Hlis
def Wsin(n):
  t=W-1
  while t>0:
    tmpo=n//(2**t)
    Wlis[W-1-t]=tmpo
    n=n%(2**t)
    t-=1
  Wlis[-1]=n
  return Wlis

res=0
for l in range(H):
  for m in range(W):
    if C[l][m]=="#":
      res+=1
K2= res-K


ans=0


for i in range(2**H):
  r=Hsin(i)
  for j in range(2**W):
    co=Wsin(j)
    res=0
    for l in range(H):
      for m in range(W):
        if (r[l]==1) or (co[m]==1 ):
          if C[l][m]=="#":
            res+=1
    if res==K2:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:

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

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

cnt = 0

for i in range(w):
    for j in range(h):
        if c[j][i] == "#":
            cnt += 1
# print(cnt)
ans = 0
ans2 = 0
s = []
for i in range(w):
    s.append(i)

t = []
for i in range(h):
    t.append(i)

#print(s, t)
n = len(s)
for i in range(2 ** n):
    bag = []
    for j in range(n):
        if (i >> j) & 1:
            bag.append(s[j])
    n2 = len(t)
    for i11 in range(2 ** n2):
        bag2 = []
        for j in range(n2):
            if (i11 >> j) & 1:
                bag2.append(t[j])
        #print(bag)
        #print("aaa", bag2)
        d = 0
        for i3 in bag:
            for i2 in range(h):
                if c[i2][i3] == "#":
                    d += 1
            for j3 in bag2:
                if c[j3][i3] == "#":
                    d -= 1

        for j3 in bag2:
            for j2 in range(w):
                if c[j3][j2] == "#":
                    d += 1

        if cnt - d == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

yoko = [i for i in range(w)]
tate = [i for i in range(h)]
ans = 0

for i in range(w+1):
    for u in itertools.combinations(yoko, i):
        #print(u)

        for j in range(h+1):
            for v in itertools.combinations(tate, j):
                #print(v)
                #print('yoko'+ str(u) + 'tate' + str(v))

                #kazoeru
                poi = 0
                #print(10)
                for ii in range(w):
                    if not ii in u:
                        #print(76)
                        for jj in range(h):
                            if not jj in v:
                                #print(91)
                                if c[jj][ii]=='#':
                                    poi += 1
                if poi == k:
                    ans += 1
                #print('yoko'+ str(u) + 'tate' + str(v) + 'poi' + str(poi))
print(ans)

Submission status: Accepted

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

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

ans=0

comb_b=[j for j in range(2**W)]

comb=[(i,comb_b) for i in range(2**H)]

for i in range(2**H):
    for j in range(2**W):
        count=0
        for k in range(H):
            for l in range(W):
                if ((0b1<<k) & comb[i][0]) or ((0b1<<l) & comb[i][1][j]):
                    pass
                else:
                    if matrix[k][l]=="#":
                        count+=1
        if count==K:
            ans+=1

print(ans)

Submission status: Accepted

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

count = 0
he = [0 for i in range(h)]
for i in range(2**h):
    we = [0 for i in range(w)]

    h_set = set(range(h))
    for j in range(h):
        if(he[j] == 0):
            h_set.discard(j)
    h_a = list(h_set)
    for j in range(h):
        if(he[h-j-1] == 0):
            he[h-j-1] = 1
            for k in range(h-j,h):
                he[k] = 0
            break

    for j in range(2**w):
        w_set = set(range(w))
        for k in range(w):
            if(we[k] == 0):
                w_set.discard(k)
        w_a = list(w_set)
        for k in range(w):
            if(we[w-k-1] == 0):
                we[w-k-1] = 1
                for m in range(w-k,w):
                    we[m] = 0
                break


        black = 0
        for x in h_a:
            for y in w_a:
                if(c[x][y] == '#'):
                    black += 1
        if(black == K):
            count += 1
 
        

print(count)

Submission status: Accepted

Solution code:
import copy

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

ans = 0
for i in range(2 ** H):
    row_colored_board = copy.deepcopy(board)
    for ii in range(H):
        if (i >> ii) & 1:
            row_colored_board[ii] = list('*' * W)
    for j in range(2 ** W):
        cnt = 0
        col_colored_board = copy.deepcopy(row_colored_board)
        for jj in range(W):
            if (j >> jj) & 1:
                for k in range(H):
                    col_colored_board[k][jj] = '*'
        for l in range(H):
            for m in range(W):
                if col_colored_board[l][m] == '#':
                    cnt += 1
    
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
def grinp(h):
  ret=[]
  for i in range(h):
    ret.append(list(input()))
  return ret
h,w,k=map(int,input().split())
gr=grinp(h)
ans=0
for i in range(2**h):
  chx=[]
  for j in range(h):
    if((i>>j)&1):
      chx.append(j)
  for j in range(2**w):
    chy=[]
    for kk in range(w):
      if ((j>>kk)&1):
        chy.append(kk)
    com=0
    for kk in range(h):
      for l in range(w):
        if kk in chx or l in chy:
          continue
        if gr[kk][l]=="#":
          com+=1
    if com==k:
      ans+=1
print(ans)

Submission status: Accepted

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

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

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

print(cnt)

Submission status: Accepted

Solution code:
def dfs(i, m, l):
    if i == m:
        return [l]
    ans = dfs(i+1, m, l+[i])
    ans += dfs(i+1, m, l)
    return ans


def main():
    H, W, K = map(int, input().split())
    M = [input() for _ in range(H)]
    r_cnt = [0]*H
    c_cnt = [0]*W
    for i, row in enumerate(M):
        for j, c in enumerate(row):
            if row[j] == "#":
                r_cnt[i] += 1
                c_cnt[j] += 1
    ans = 0
    bc = 0
    r_combi = dfs(0, H, [])
    c_combi = dfs(0, W, [])
    for rc in r_combi:
        for cc in c_combi:
            for r in rc:
                bc += r_cnt[r]
            for r in rc:
                for c in cc:
                    if M[r][c] == "#":
                        bc -= 1
            if bc == K:
                ans += 1
            bc = 0
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
l = []
lh = []
lw = []
s = 0
r = 0
for i in range(h):
    il = input()
    l.append(il)
    s += il.count('#')
    lh.append(il.count('#'))
for i in range(w):
  j = 0
  for il in l:
    if il[i] == '#':
      j += 1
  lw.append(j)
    
t = s - k
if t == 0:
    r += 1
    
from itertools import combinations

for nh in range(1,h+1):
  for ih in combinations(range(h), nh):
    if sum([lh[x] for x in ih]) == t:
      r += 1
      
for nw in range(1,w+1):
  for iw in combinations(range(w), nw):
    if sum([lw[x] for x in iw]) == t:
      r += 1
      
for nh in range(1,h+1):
    for nw in range(1,w+1):
        for ih in combinations(range(h), nh):
            for iw in combinations(range(w),nw):
                ik = sum([lh[x] for x in ih]) + sum([lw[x] for x in iw])
                for jh in ih:
                    for jw in iw:
                        if l[jh][jw] == '#':
                            ik -= 1
                if ik == t:
                    r += 1
                    
print(r)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
import numpy as np
aa = np.zeros((h, w),dtype='int32')
for i in range(h):
    aa[i] = np.array([int(c=='#') for c in input()])
cnt = 0
for i in range(2**w):
    col = np.array([int(i&(2**j)>0) for j in range(w)])
    tmp = aa.dot(col)
    for p in range(2**h):
        row = np.array([int(p&(2**l)>0) for l in range(h)])
        if np.sum(tmp*row) == k:
            cnt += 1
print(cnt)

Submission status: Accepted

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

import numpy as np

A = np.zeros([H,W])
cntResult = 0

for i in range(H):
    B = input()
    for j in range(W):
        if B[j] == '.':
            A[i,j] = 0
        else:
            A[i,j] = 1

sumA = np.sum(A)
sumH = [0]*H
sumW = [0]*W
for i in range(H):
    sumH[i] = np.sum(A[i,:])

for i in range(W):
    sumW[i] = np.sum(A[:,i])


for i in range(2**H):
    cntH = format(i, '0%db' % H)
    for j in range(2**W):
        cntW = format(j, '0%db' % W)
        result = 0
        for k in range(H):
            for l in range(W):
                if int(cntH[k]) == 0 and int(cntW[l]) == 0:
                    result += A[k,l]
        if result == K:
            cntResult += 1

print(cntResult)