Problem:


Score : 300 points

Problem Statement

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

Consider doing the following operation:

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

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

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

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

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

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

Sample Output 4

208



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


Sample output:
5

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[[]]*h
for i in range(h):
    tmp =list(input())
    c[i] = [1 if x=='#' else 0 for x in tmp]

# print(c)
from itertools import product

aans=0

for i in product([0,1],repeat=h):
    for j in product([0,1],repeat=w):
        ans=0
        for hh in range(h):
            for ww in range(w):
                if i[hh] == 1 and j[ww] == 1:
                    if c[hh][ww] == 1:
                        # print(i,j)
                        ans += 1
        if ans == k:
            aans +=1

print(aans)

Submission status: Accepted

Solution code:
#1 <= H, W <= 6から、総当たりで求めるのが丸い

import itertools
import pprint

def count_black(A):
    ans = 0
    for a in A:
        ans += a.count("#")
    return(ans)

def make(n):
    ans = []
    for i in range(2 ** n):
        addition = []
        now = bin(i)[2:]
        now = "0" * (n - len(now)) + now
        for j in range(n):
            if now[j] == "1":
                addition.append(j + 1)
        ans.append(addition)
    return(ans)

def remove(C, r):
    rem_col = set(r[0])
    rem_row = set(r[1])
    kouho_col = {i + 1 for i in range(len(C))}
    kouho_row = {i + 1 for i in range(len(C[0]))}
    col = kouho_col - rem_col
    row = kouho_row - rem_row
    ret = []
    for i in col:
        c = C[i - 1]
        new_col = []
        for j in row:
            new_col.append(c[j - 1])
        ret.append(new_col)
    return(ret)


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

#赤く塗る行と列の選び方を全パターン分つくる
#[[1,2,3],[1,2,4]]みたいなので2^(H + W)作る
all = []
collum = make(H)
row = make(W)
all = list(itertools.product(collum, row))

#全パターン試して、うまく行ったものを数え上げる
ans = 0
for i in all:
    now = remove(C, i)
    black = count_black(now)
    if black == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

black=[]
for i in range(H):
    for j in range(W):
        if c[i][j] == '#':
            black.append([i,j])
black_cnt=len(black)
            
cnt=0
ans_list=[]
for i in range(H):
    for comb_H in itertools.combinations(range(H),i):
        for j in range(W):          
            for comb_W in itertools.combinations(range(W),j):
                temp_black=black.copy()
                temp=temp_black.copy()
                for k in temp_black:
                    if k[0] in list(comb_H):
                        if k in temp:
                            temp.remove(k)
                    if k[1] in list(comb_W):
                        if k in temp:
                            temp.remove(k)

                if len(temp) == K:
                    #print("comb:",comb_H,comb_W)
                    if [list(comb_H),list(comb_W)] in ans_list:
                        pass
                    else:
                        ans_list.append([list(comb_H),list(comb_W)])
                    
                    
print(len(ans_list))

Submission status: Accepted

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

black=0
for i in range(h):
    black+=c[i].count('#')

import itertools

count=0

for i in list(itertools.product((0,1),repeat=h)):
    for j in list(itertools.product((0,1),repeat=w)):
        b=black
        for k in range(h):
            b-=i[k]*(c[k].count('#'))
        for l in range(w):
            b-=j[l]*([d[l] for d in c].count('#'))
        for l in range(h):
            for m in range(w):
                if i[l]==1 and j[m]==1:
                    if c[l][m]=='#':
                        b+=1
        if b==K:
            count+=1

print(count)

Submission status: Accepted

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

sqr = [32, 16, 8, 4, 2, 1]

def bin_num(n):
    paint_num = []
    for i in range(6):
        if n > sqr[i]:
            paint_num.append(5-i)
            n -= sqr[i]
    return paint_num 

ans = 0
h_count = 2**h
w_count = 2**w
for i in range(h_count):
    h_ng = bin_num(i+1)
    for j in range(w_count):
        w_ng = bin_num(j+1)
        count = 0
        for m in range(h):
            for l in range(w):
                if (c[m][l] == '#') and (not m in h_ng) and (not l in w_ng):
                    count += 1
        if count == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
s=[]
Sh=[0]*h
Sw=[0]*w
cnt=[]
Th=[]
Tw=[]
for i in range(h):
    s.append(input())

for i in range(h):
    cnt.append(s[i].count('#'))

for i in range(w):
    c=0
    for j in range(h):
        if s[j][i]=='#':
            c+=1
    cnt.append(c)
#cntの1~hは　行　の#の個数。h+1~wは　列　の#の個数

#関数の定義
def cheak(s,i,j):
    if s[i][j]=='#':
        return 1
    else:
        return 0

def rech(k):
    totalh=0
    if k==h:
        for i in range(h):
            if Sh[i]==1:
                totalh+=cnt[i]
        #print(Sh, totalh)
        th=Sh.copy()
        Th.append(th)
        Th.append(totalh)
        return
    rech(k+1)
    Sh[k]=1
    rech(k+1)
    Sh[k]=0

def recw(k):
    totalw=0
    if k==w:
        for i in range(w):
            if Sw[i]==1:
                totalw+=cnt[h+i]
        #print(Sw, totalw)
        tw=Sw.copy()
        Tw.append(tw)
        Tw.append(totalw)
        return
    recw(k+1)
    Sw[k]=1
    recw(k+1)
    Sw[k]=0

total=sum(cnt[0:h])
ans=0
'''
for i in range(h):
    for j in range(w):
        if total-(cnt[i]+cnt[h+j]-cheak(s,i,j))==k:
            ans+=1
'''
rech(0)
recw(0)
#print(Th)
#print(Tw)

for i in range(2**h):
    for j in range(2**w):
        cheaktotal=0
        for p in range(h):
            for q in range(w):
                if Th[2*i][p]==1 and Tw[2*j][q]==1:
                    cheaktotal+=cheak(s,p,q)
        if total-Th[2*i+1]-Tw[2*j+1]+cheaktotal==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations
h,w,k = map(int,input().split())
grid = [list(input()) for i in range(h)]
cnt = [[0 for _ in range(w)] for __ in range(h)]
ans = 0
for i in range(w):
    for j in range(h):
        if grid[j][i] == '#':
            cnt[j][i] = 1
cnt = np.array(cnt)

h_ = [i for i in range(h)]
w_ = [i for i in range(w)]
ans = 0
h_combo = []
w_combo = []
for i in range(1,h+1):
    for h_com in combinations(h_,i):
        h_combo.append(h_com)
for i in range(1,w+1):
    for w_com in combinations(w_,i):
        w_combo.append(w_com)

for i in h_combo:
    for j in w_combo:
        cnt2 =cnt.copy()
        for i2 in i:
            cnt2[i2,:] = 0
            for j2 in j:
                cnt2[:,j2] = 0
                
        if sum(sum(cnt2)) == k:
            ans += 1
            
for i in h_combo:
    cnt2 =cnt.copy()
    for i2 in i:
        cnt2[i2,:] = 0
    if sum(sum(cnt2)) == k:
            ans += 1
for j in w_combo:
    cnt2 =cnt.copy()
    for j2 in j:
        cnt2[:,j2] = 0
    if sum(sum(cnt2)) == k:
        ans += 1
        
if sum(sum(cnt)) == k:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
h,w,k=map(int,input().split())
g=np.ones((h,w))
l=['' for _ in range(h)]
for i in range(h):
  l[i]=str(input())
for i in range(h):
  for j in range(w):
    if l[i][j]=='.': g[i][j]=0
s=np.sum(g)
ans=0
for i in range(h):
  for j in range(w):
    u=list(itertools.combinations(range(h),i))
    v=list(itertools.combinations(range(w),j))
    for x in u:
      for y in v:
        a=0
        b=0
        c=0
        for p in x:
          a+=np.sum(g[p,:])
        for q in y:
          b+=np.sum(g[:,q])
        for p in x:
          for q in y:
            c+=g[p][q]
        if s-a-b+c==k: 
          ans+=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import Counter
import itertools
import copy
from itertools import product


def count_black(array):
    flatten = itertools.chain.from_iterable(array)
    c = Counter(flatten)
    return c['#']


def red_row(array, i):
    length = len(array[0])
    array[i] = ['r'] * length
    return array


def red_col(array, j):
    for row in array:
        row[j] = 'r'
    return array


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

for _ in range(H):
    row = list(input())
    C.append(row)

total = 0

row_select_patterns = product([True, False], repeat=H)
col_select_patterns = list(product([True, False], repeat=W))

for row_select_pattern in row_select_patterns:
    for col_select_pattern in col_select_patterns:
        c = copy.deepcopy(C)

        for i, i_flag in enumerate(row_select_pattern):
            for j, j_flag in enumerate(col_select_pattern):
                if i_flag:
                    c = red_row(c, i)

                if j_flag:
                    c = red_col(c, j)

        if count_black(c) == K:
            total += 1

print(total)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import copy

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

c = []

for i in range(H):
    row = list(input())
    c.append(row)

count = 0
for i in range(2 ** len(c)):        
    tmp_c = [c[k] for k in range(len(c)) if ((i >> k) & 1)]
    for j in range(2 ** len(c[0])):
        tmp_tmp_c = copy.copy(tmp_c)
        for l in range(len(tmp_c)):
            tmp_tmp_c[l] = [tmp_c[l][k] for k in range(len(tmp_c[0])) if ((j >> k) & 1)]

        total_blacks = 0
        for i in range(len(tmp_tmp_c)):
            total_blacks += tmp_tmp_c[i].count('#')
        
        if total_blacks == K:
            count += 1

print(count)

Submission status: Accepted

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

Black=[]
for h in range(H):
    L_=list(input())
    for w in range(W):
        if L_[w]=='#':
            Black.append([h,w])

from itertools import product

ans=0

for h in product(range(2),repeat=H):
    for w in product(range(2),repeat=W):
        h_=[]
        for _ in range(H):
            if h[_]==1:
                h_.append(_)
        w_=[]
        for _ in range(W):
            if w[_]==1:
                w_.append(_)
                    
        Black_=[]
        
        if len(h_) == 0 and len(w_) == 0:
            pass
        elif len(w_) > 0 and len(h_) == 0:
            for W_ in w_:
                for black in Black:
                    if black[1] == W_:
                        if black not in Black_:
                            Black_.append(black)
        
        elif len(w_) == 0 and len(h_) > 0:
            for H_ in h_:
                for black in Black:
                    if black[0] == H_:
                        if black not in Black_:
                            Black_.append(black)            
        
        elif len(h_)>0 and len(w_)>0:
            for H_ in h_:
                for W_ in w_:
                    for black in Black:
                        if black[0] == H_ or black[1] == W_:
                            if black not in Black_:
                                Black_.append(black)
                    
        if len(Black)-len(Black_) == K:
#             print(h_,w_,Black_)
            ans+=1
print(ans)

Submission status: Accepted

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

import copy

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

C = []

x_l = []
y_l = []

# マス目の読み込み
for y in range(H):
    tmp = list(str(input()))
    C.append(tmp)

# 計算用のリストの作成
for i in range(2 ** H):
    x_l.append(list(str(bin(i))[2:].zfill(H)))

for i in range(2 ** W):
    y_l.append(list(str(bin(i))[2:].zfill(W)))

#print(*x_l)
#print(*y_l)

# 演算
tmp_k = 0
ans = 0
for x in x_l:
    for y in y_l:
        tmp_k = 0
        tmp_C = copy.deepcopy(C)
        # x の演算
        for i in range(len(x)):
            if x[i] == '1':
                tmp_C[int(i)] = ['.'] * W
        # y の演算
        for j in range(len(y)):
            if y[j] == '1':
                for k in range(len(x)):
                            tmp_C[k][int(j)] = '.'
        # K の演算 
        for tmp_tmp_C in tmp_C:
            tmp_k = tmp_k + tmp_tmp_C.count('#')
        #print(tmp_k)
        if tmp_k == K:
            ans += 1

#print('-' * 40)
print(ans)

Submission status: Accepted

Solution code:
h,w,ka=map(int,input().split())
mat=[list(input()) for i in range(h)]
ans=0
for i  in range(2**(h+w)):
    b=bin(i)[2:].zfill(h+w)
    rs=b[:h]
    cs=b[h:]
    ct=0
    for l in range(h):
        for k in range(w):
            if mat[l][k]=='#' and rs[l]=='0' and cs[k]=='0':
                ct+=1
    if ct==ka: ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
H,W,K = LI()
c = [S() for _ in range(H)]
black = 0
for h in range(H):
    for w in range(W):
        if c[h][w]=='#':
            black += 1
ans = 0
for h in range(2**H):
    for w in range(2**W):
        copy_black = black
        bit_h = [h>>i&1 for i in range(H)]
        bit_w = [w>>i&1 for i in range(W)]
        for i,bit_i in enumerate(bit_h):
            for j in range(W):
                if bit_i==1:
                    if c[i][j]=='#':
                        copy_black -= 1
        for j,bit_j in enumerate(bit_w):
            for i in range(H):
                if bit_j==1:
                    if c[i][j]=='#':
                        copy_black -= 1
        for i,bit_i in enumerate(bit_h):
            for j,bit_j in enumerate(bit_w):
                if bit_i==bit_j==1:
                    if c[i][j]=='#':
                        copy_black += 1
        if copy_black==K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

h = []
w = []

def countSharp(work):
    cnt = 0
    for row in work:
        for col in row:
            if col == '#':
                cnt += 1
    return cnt

def makeH(current, end):
  if len(current) == end:
    h.append(copy.copy(current))
    return
  else:
    current.append(True)
    makeH(current, end)
    current.pop(len(current) - 1)

    current.append(False)
    makeH(current, end)
    current.pop(len(current) - 1)

def makeW(current, end):
  if len(current) == end:
    w.append(copy.copy(current))
    return
  else:
    current.append(True)
    makeW(current, end)
    current.pop(len(current) - 1)

    current.append(False)
    makeW(current, end)
    current.pop(len(current) - 1)

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

makeH([], H)
makeW([], W)

# print(h)
# print(w)

matrix = []
for i in range(0, H):
    row = []
    for c in input():
        row.append(c)
    matrix.append(row)

# for i in range(0, H):
# 	print(matrix[i])

answer = 0

for hh in h:
    for ww in w:
        work = []
        for h in range(0, H):
            work.append(copy.copy(matrix[h]))

        for i in range(0, H):
            for j in range(0, W):
                if hh[i] == True:
                    for jjj in range(0, W):
                        work[i][jjj] = 'r'
                if ww[j] == True:
                    for iii in range(0, H):
                        work[iii][j] = 'r'

        count = countSharp(work)
        if count == K:
            answer += 1

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools

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

    B = 0
    BH = [0]*H
    BW = [0]*W
    BHW = []
    pBHW = []
    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
                pBHW.append((i,j))

    cnt = 0
    for ibit in range(0,1<<H):
        for jbit in range(0,1<<W):
            icost = 0
            jcost = 0
            ijcost = 0
            for i in range(H):
                if (1<<i) & ibit:
                    icost += BH[i]
            for j in range(W):
                if (1<<j) & jbit:
                    jcost += BW[j]
            for i in range(H):
                for j in range(W):
                    if (1<<i) & ibit and (1<<j) & jbit:
                        ijcost += BHW[i][j]
            b = B - icost - jcost + ijcost
            if K == b:
                cnt += 1
            # print(b,B,icost,jcost,ijcost,cnt)
    print(cnt)
                        
    # print(B)
    # print(BH)
    # print(BW)
    # print(BHW)
    # print(pBHW)
    # for k in itertools.combinations(pBHW,2):
    #     print(k)
    # cnt = 0

    # costs_i = []
    # for ibit in range(0,1<<H):
    #     cost = 0
    #     for i in range(H):
    #         if (1<<i) & ibit:
    #             cost += BH[i]
    #     costs_i.append(cost)
    # costs_j = []
    # for jbit in range(0,1<<W):
    #     cost = 0
    #     for j in range(H):
    #         if (1<<j) & jbit:
    #             cost += BW[j]
    #     costs_j.append(cost)
    # print(costs_i)
    # print(costs_j)
    
    # for ci in costs_i:
    #     for cj in costs_j:
    #         b = B - ci - cj + BHW[i][j]
    #         if K == b:
    #             cnt += 1
    #         print(i,j,b,B,BH[i],BW[j],BHW[i][j],cnt)
    # print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

h, w, k = map(int, input().split())
table = [0]*h
for i in range(h):
    table[i] = [0 if j == "." else 1 for j in input()]
ans = 0

for i in range(2 ** (h + w)):
    t = copy.deepcopy(table)
    for j in range(h + w):
        if ((i >> j) & 1):
            if j < h:
                for l in range(w):
                    t[j][l] = 0
            else:
                for l in range(h):
                    t[l][j-h] = 0
    black = sum(map(sum, t))
    if black == k:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:

import math
import itertools
h, w, k = map(int, input().split())
c = []
cnt_ans = 0
for i in range(h):
    c.append(input())
#print(c)
y = itertools.product([0, 1], repeat=h)
x = itertools.product([0, 1], repeat=w)

y = [s for s in y]
x = [s for s in x]

for i in y:
    for j in x:
        cnt_kuro = 0
        for a in range(h):
            if i[a] == 0:
                continue
            for b in range(w):
                if j[b] == 0:
                    continue
                if c[a][b] == "#":
                    cnt_kuro += 1
        if cnt_kuro == k:
            cnt_ans += 1
print(cnt_ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[]
for _ in range(h):
  c.append(list(input()))
ans=0
for i in range(2**h):
  for j in range(2**w):
    q=0
    for i_ in range(h):
      for j_ in range(w):
        if ((i>>i_)&1) and ((j>>j_)&1) and c[i_][j_]=='#':
          q+=1
    if q==k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:

import numpy as np

from itertools import combinations, product

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

ls = []

for h in range(H):
    ls.append(
        list(
            map(
                lambda x : 1 if x == "#" else 0, list(input())
                )
            )
        )

ls = np.array(ls)

all_sum = np.sum(ls)

cnt = 0

bool_ind_h = np.array([False for _ in range(H)])
bool_ind_w = np.array([False for _ in range(W)])
ls_tmp = ls.copy()

for h in range(H + 1):
    for w in range(W + 1):
        ls_tmp = ls.copy()
        comb_h = combinations(range(H), h)
        comb_w = combinations(range(W), w)
        for ch, cw in product(comb_h, comb_w):
            ls_tmp = ls.copy()
            ls_tmp[list(ch), :] = 0
            ls_tmp[:, list(cw)] = 0
            if np.sum(ls_tmp) == K:
                cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
c = []
w_count = []
h_count = [0 for _ in range(w)]
n = 0
for _ in range(h):
    tmp = list(input())
    for i in range(w):
        if tmp[i] == "#":
            h_count[i] += 1
    tc = tmp.count("#")
    n += tc
    w_count.append(tc)
    c.append(tmp)
# print(w_count, h_count)

ans = 0
for w_bin in range(2 ** w):
    for h_bin in range(2 ** h):
        w_bin_st = bin(w_bin)[2:].zfill(w)
        h_bin_st = bin(h_bin)[2:].zfill(h)
        # print(w_bin_st, h_bin_st)
        num = 0
        i_list = []
        j_list = []
        for i, wb in enumerate(list(w_bin_st)):
            if wb == "1":
                i_list.append(i)
                num += h_count[i]
        for j, hb in enumerate(list(h_bin_st)):
            if hb == "1":
                j_list.append(j)
                num += w_count[j]
        if n-num <= k:
            for il in i_list:
                for jl in j_list:
                    if c[jl][il] == "#":
                        num -= 1
            if n-num == k:
                # print(i_list, j_list)
                ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
h,w,k2=map(int,input().split())
temp=[]
htemp=[i for i in range(h+w)]

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

retsum=0
import copy
def check(temp3,htemplist2):
    temp2=copy.deepcopy(temp3)
    for k in range(len(htemplist2)):
        if htemplist2[k]<h:
            for l in range(w):
                temp2[htemplist2[k]][l]="."
        if htemplist2[k]>=h:
            for l in range(h):
                temp2[l][htemplist2[k]-h]="."
    tempsum=0
    for x in range(h):
        for y in range(w):
            if temp2[x][y]=="#":
                tempsum+=1
    if tempsum==k2:
        return 1
    else:
        return 0

tempsum2=0
for x in range(h):
    for y in range(w):
        if temp[x][y]=="#":
            tempsum2+=1
if tempsum2==k2:
    retsum+=1

for i in range(1,h+w):
    htemplist=list(itertools.combinations(htemp,i))
    for j in range(len(htemplist)):
        retsum+=check(temp,htemplist[j])



print(retsum)

Submission status: Accepted

Solution code:
import itertools
import copy
import numpy as np

def main():
    H, W, K  = map(int, input().split())
    if K == 0:
        print(1)
        exit()
    c = np.full((H, W), False)
    for h in range(H):
        for w, s in enumerate(input()):
            if s == '#':
                c[h][w] = True
            else:
                c[h][w] = False
    ans = 0
    for h in range(H):
        for coh in itertools.combinations(range(H), h):
            cc = np.delete(c, coh, 0)
            for w in range(W):
                for cow in itertools.combinations(range(W), w):
                    ccc = np.delete(cc, cow, 1)
                    if ccc.sum() == K:
                        ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def resolve():
  H, W, K = map(int, input().split(" "))
  tasksH = []
  tasksH.append([])
  rangeH = range(H)
  for h in rangeH:
    tasksH.extend([list(x) for x in combinations(rangeH, h + 1)])

  tasksW = []
  tasksW.append([])
  rangeW = range(W)
  for w in rangeW:
    tasksW.extend([list(x) for x in combinations(rangeW, w + 1)])


  tasks = [list(x) for x in product(tasksH, tasksW)]

  C = []
  for h in range(H):
    C.append([x == "#" for x in list(input()) ])
  C = np.array(C)

  result = 0
  for task in tasks:
    if np.sum(C[np.ix_(task[0], task[1])]) == K:
      result += 1
  print(result)

if __name__ == "__main__":
  resolve()

Submission status: Accepted

Solution code:
import itertools
from dataclasses import dataclass, field
from typing import List


@dataclass
class Cell:
    i: int
    j: int
    color: str

    def to_red(self):
        return Cell(self.i, self.j, color='R')


@dataclass
class Board:
    cells: List[Cell] = field(default_factory=list)
    count: int = 0

    @classmethod
    def create(cls, H: int, W: int, C: List[List[str]]):
        cells = []
        for i in range(H):
            for j in range(W):
                cell = Cell(i + 1, j + 1, C[i][j])
                cells.append(cell)

        return Board(cells)

    def count_black(self) -> int:
        return len([c for c in self.cells if c.color == '#'])

    def paint_row(self, row: int):
        new_cells = []

        for cell in self.cells:
            if cell.i == row:
                new_cells.append(cell.to_red())
            else:
                new_cells.append(cell)

        return Board(new_cells)

    def paint_col(self, col: int):
        new_cells = []

        for cell in self.cells:
            if cell.j == col:
                new_cells.append(cell.to_red())
            else:
                new_cells.append(cell)

        return Board(new_cells)


def actual(H, W, K, C):
    count = 0

    patterns = list(itertools.product(range(2), repeat=H + W))

    for pattern in patterns:
        board = Board.create(H, W, C)

        row_info = pattern[:H]
        col_info = pattern[H:]

        for row_idx, row in enumerate(row_info, start=1):
            if row == 1:
                board = board.paint_row(row_idx)

        for col_idx, col in enumerate(col_info, start=1):
            if col == 1:
                board = board.paint_col(col_idx)

        if board.count_black() == K:
            count += 1

    return count

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

print(actual(H, W, K, C))

Submission status: Accepted

Solution code:
import sys

def main():
    H,W,K=map(int,input().split())
    gyou=[]
    retu_index=[]
    retu=[0 for _ in range(W)]
    black=0
    for i in range(H):
        s=input()
        gyou.append(s.count("#"))
        tmp=[]
        for j in range(W):
            if s[j]=="#":
                retu[j]+=1
                black+=1
                tmp.append(j)
        retu_index.append(tmp)

    p=black-K
    if p<0:
        print(0)
        sys.exit()


    gyou.extend(retu)
    matrix=gyou

    res=0
    for i in range(pow(2,H+W)):
        n=0
        matrix_=matrix[:]
        for j in range(H+W):
            if (i & (1<<j))!=0:
                if j<H:
                    for k in retu_index[j]:
                        matrix_[H+k]-=1
                n+=matrix_[j]

        if n==p:
            res+=1
    print(res)


if __name__=="__main__":
    main()

Submission status: Accepted

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

c = list()
judge = list()
for a in range(h):
    c.append(list(input()))
    judge.append([False]*w)

red = '*'

exist = False

ans = list()

for i in range(2 ** h):
    tmp = copy.deepcopy(c)
    for j in range(h):
        if (i >> j) & 1:
            tmp[j] = [red]*w
    ans.append(tmp)

result = list()

length = len(ans)
for now in range(length):
    for i in range(2**w):
        tmp = copy.deepcopy(ans[now])
        for j in range(w):
            if (i >> j) & 1:
                tmp_length = len(tmp)
                for z in range(tmp_length):
                    tmp[z][j] = red
        result.append(tmp)

result_length = len(result)

num = 0

for a in range(result_length):
    red_count = 0
    for b in range(h):
        red_count += result[a][b].count('#')
    if k == red_count:
        num += 1

print(num)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[]
#行ごと
hk=[]
for i in range(h):
    kki=0
    hwi=input()
    hw=[]
    for j in range(w):
        if hwi[j]=='#':
            hw.append(1)
            kki+=1
        else:
            hw.append(0)
    c.append(hw)
    hk.append(kki)
kk=sum(hk)
ans=0
#残す行を選ぶ
for i in range(2**h):
    #列ごと
    wk=[0]
    wk*=w
    for j in range(h):
        if (i>>j &1):
            #残った行の列ごとの和
            for l in range(w):
                wk[l]+=c[j][l]
    #残す列を選ぶ
    for j in range(2**w):
        ansi=0
        for l in range(w):
            if (j>>l & 1):
                ansi+=wk[l]
        if ansi==k:
            ans+=1
    
print(ans)