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())
M = []
for h in range(H):
    col = []
    s = input()
    for w in range(W):
        if s[w] == '.':
            col.append('.')
        else:
            col.append('#')
    M.append(col)
    

result = 0
for i in range(2 ** (H + W)):
    bag = []
    for j in range(H  + W): 
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う 
            bag.append(j)  # フラグが立っていたら bag に追加
    
    #main
    #print(bag)
    
    hight_list =[]
    width_list = []
    for b in bag:
        if b < H:
            hight_list.append(b)
        else:
            width_list.append(b - H)
    
    count = 0
    for r_h in hight_list:
        for r_w in width_list:
            if M[r_h][r_w] == '#':
                count+=1
    
    if count == K:
        result+=1
        
print(result)

Submission status: Accepted

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

c = []
for _ in range(H):
    letters = input()
    my_row = [1 if letter == '#' else 0 for letter in letters]
    c.append(my_row)
    
import itertools
count = 0
for h in range(H + 1):
    for delete_rows in itertools.combinations(range(H), h):
        new_c = c
        new_c = [[0] * W if idx in delete_rows else row for idx, row in enumerate(c)]
        # print(new_c)
        for w in range(W + 1):
            for delete_cols in itertools.combinations(range(W), w):
                new_new_c = [[0 if idx in delete_cols else score for idx, score in enumerate(row)] for row in new_c]
                # print(new_new_c)
                # print(sum(sum(new_new_c[i]) for i in range(H)))
                if sum(sum(new_new_c[i]) for i in range(H)) == K:
                    count += 1
print(count)

Submission status: Accepted

Solution code:
import copy
h, w, k = map(int, input().split())
cp_c = []
ans = 0
for i in range(h):
    cp_c.append(list(input()))
for i in range(2**h):
    ti = format(i, '06b')
    ti = ti[6-h:]
    for j in range(2**w):
        tj = format(j, '06b')
        tj = tj[6-w:]
        c = copy.deepcopy(cp_c)
        for m in range(h):
            for l in range(w):
                if ti[m] == "1" or tj[l] == "1":
                    c[m][l] = '1'
        cnt = 0
        for s in range(h):
            for t in range(w):
                if c[s][t] == '#':
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

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

col_black = [0] * H
row_black = [0] * W
num_black = 0
for i in range(H):
    for j in range(W):
        if C[i][j]=='#':
            col_black[i] += 1
            row_black[j] += 1
            num_black += 1

ans = 0
for i in range(2**H):
    I = []
    num_i_black = 0
    for ii in range(H):
        if i>>ii & 1:
            I.append(ii)
            num_i_black += col_black[ii]
    for j in range(2**W):
        J = []
        num_j_black = 0
        for jj in range(W):
            if j>>jj & 1:
                J.append(jj)
                num_j_black += row_black[jj]
        
        num = num_i_black + num_j_black
        for ii in I:
            for jj in J:
                num -= C[ii][jj] == '#'
        
        if num_black - num == K:
            ans += 1

print(ans)

Submission status: Accepted

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline
import copy

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

d = []
for i in range(h):
    s = input()
    d.append(list(s[:-1]))


c_h = 2**h
c_w = 2**w
ans = 0
ans_d = defaultdict(int)


for i in range(c_h):
    d_ = copy.deepcopy(d)
    for _h in range(h):
        if i >> _h & 1:
            for _ in range(w):
                d_[_h][_] = 0

    for j in range(c_w):
        d2_ = copy.deepcopy(d_)
        for _w in range(w):
            if j >> _w & 1:
                for _ in range(h):
                    d2_[_][_w] = 0

        val = 0
        for s1 in range(h):
            for s2 in range(w):
                if d2_[s1][s2] == '#':
                    val += 1
        if val == k:
            ans += 1
        # print(f'(i,j), {i},{j}, {val}, {d2_}')
        del d2_

print(ans)

Submission status: Accepted

Solution code:
import copy
H,W,K = map(int,input().split())
C = [list(input()) for _ in range(H)]
D = copy.deepcopy(C)
ans = 0
for i in range(2**H):#行
    for j in range(2**W):#列
        black = 0
        for k in range(H):#行
            if (i>>k)&1:#行に対して調べる
                for l in range(W):
                    C[k][l] = "a"
        for m in range(W):#列に対して調べる
            if (j>>m)&1:
                for n in range(H):
                    C[n][m] = "a"
        
        for x in range(H):
            for y in range(W):
                if(C[x][y] == "#"):
                    black += 1
        
        if(black == K):
            ans += 1
        C = copy.deepcopy(D)
print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
x=[]
for i in range(h):
    l=input()
    l2=[]
    for o in range(len(l)):
        l2.append(l[o])
    x.append(l2)
n=2**(h+w)
ans=0
for i in range(n):
    q=i
    num=[0]*(h+w)
    p=0
    while q>0:
        if q%2!=0:
            num[p]=1
        q=q//2
        p+=1
    cnt=0
    for tat in range(h):
        if num[tat]==0:
            for yok in range(w):
                if num[yok+h]==0  and  x[tat][yok]=="#":
                        cnt+=1
    if cnt==k:
        ans+=1
print(ans)

Submission status: Accepted

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

R = 0
for i in range(2**H):
    iis = [0]*H
    tmp = 0
    while i:
        if i%2:
            iis[tmp] = 1
        i = i//2
        tmp += 1
    for j in range(2**W):
        jjs = [0]*W
        tmp = 0
        while j:
            if j%2:
                jjs[tmp] = 1
            j = j//2
            tmp += 1
        co = 0
        for u in range(H):
            for v in range(W):
                if iis[u] or jjs[v]:
                    continue
                if X[u][v] == "#":
                    co += 1
        if co == K:
            R += 1

print(R)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
H, W, K = [int(x) for x in input().split(" ")]

a = np.zeros((H, W), dtype=bool)
for i in range(H):
    a[i, [x == "#" for x in input()]] = True

c = [[True, False]] * (H + W)
count = 0
for i in itertools.product(*c):
    h = i[:H]
    w = i[H:]
    ap = np.copy(a)
    ap[h, :] = False
    ap[:, w] = False
    if ap.sum() == K:
        count += 1
print(count)

Submission status: Accepted

Solution code:
def kuro(x,y,c):
    dcr=0
    for cc in c:
        if cc[0] in x:
            dcr+=1
        if cc[1] in y:
            dcr+=1   
    for i in x:
        for j in y:
            if [i,j] in c:
                dcr-=1
    return dcr

def nshinsu(x,h):
    lis=[]
    xx=x
    for i in range(h-1,-1,-1):
        if xx >= 2**i:
            lis.append(i)
            xx=xx-(2**i)
    return lis
h,w,k= map(int,input().split())
c =[]
black=0
ans=0
for i in range(h):
    l= input()
    for j in range(w):
        if l[j]=="#":
            c.append([i,j])
            black+=1
for i in range(2**h):
    for j in range(2**w):
        x =nshinsu(i,h)
        y =nshinsu(j,w)
        d =kuro(x,y,c)
        if d== black-k:
            ans+=1
        #print(x,y,d)
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
c = []
for k in range(H):
    c.append(input())
"""
total = 0
for k in range(H):
    for j in range(W):
        if c[k][j] == '#':
            total +=1
"""
ans =0
for w in range(2**W):
    binw = str(bin(w))[2:]
    binw = "0"*(W-len(binw)) + binw
    for h in range(2**H):
        binh = str(bin(h))[2:]
        binh = "0"*(H-len(binh)) + binh 
        count = 0
        for k in range(H):
            for j in range(W):
                if binw[j] == '0' and binh[k] == '0':
                    if c[k][j] == '#':
                        count+=1
        if count == K:
            #print(binw, binh)
            ans +=1
print(ans)

Submission status: Accepted

Solution code:
H,W,K = [int(i) for i in input().split()]
grid = [list(input()) for i in range(H)]
B = sum([i.count("#") for i in grid])
c = 0
for i in range(2**(H)):
    for j in range(2**(W)):
        gt = [[j for j in i] for i in grid]
        a,b = bin(i)[2:], bin(j)[2:]
        while len(a) < H:
            a = "0" + a
        while len(b) < W:
            b = "0" + b
        for x in range(H):
            if a[x] == "1":
                gt[x] = ["."]*W
        for y in range(W):
            for x in range(H):
                if b[y] == "1":
                    gt[x][y] = "."
        # print(gt)
        if sum([x.count("#") for x in gt]) == K:
            c += 1
        # k, p = 0,0
        # for x in range(H):
        #     for y in range(W):
        #         if a[x] == "1" or b[y] == "1":
        #             if grid[x][y] == "#":
        #                 if a[x] == "1" and b[y] == "1":
        #                     p += 1
        #                 else:
        #                     k += 1
        # if k + p/2 == K:
        #     print(a,b)
        #     print(k, p, K)
        #     c += 1
print(c)

Submission status: Accepted

Solution code:
import copy

def main():
    H,W,K = map(int,input().split())
    c = []
    for h in range(H):
        c.append(list(map(str,input())))
    
    ans = 0
    for hh in range(2**H):
        for ww in range(2**W):
            C = copy.deepcopy(c)
            for h in range(H):
                if ((hh >> h)&1):
                    C[h] = ['R' for i in range(W)]
            for w in range(W):
                if ((ww >> w)&1):
                    for i in range(H):
                        C[i][w] = 'R'
            count = 0
            for i in range(H):
                for j in range(W):
                    if C[i][j] == '#':
                        count += 1
            if count == K:
                ans += 1
    
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=''
for i in range(h):
    c+=input()
# print(c)
# row_dot_cnt=[c.count() for _ in range(h)]
# col_dot_cnt=[0]*w
ans=0
for i in range(2**h): # 行
    i_bin=format(i,'06b')
    for j in range(2**w): # 列
        j_bin=format(j,'06b')
        cnt=0
        # print(i_bin,j_bin)
        for s in range(h):
            if i_bin[5-s]=='0':
                for t in range(w):
                    if j_bin[5-t]=='0' and c[s*w+t]=='#':
                        # print(s,t)
                        cnt+=1
        if cnt==k:
            ans+=1
            # print(f'        {cnt}   {ans}')
print(ans)

Submission status: Accepted

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

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main(mtx, k):
    # print(count([['.','#','.'],['.','#','#']], [(1,2)], []))
    # return
    h_indices = []
    for i in range(len(mtx)):
        idx = [k for k in range(len(mtx))]
        h_indices += list(itertools.combinations(idx, i))

    w_indices = []
    for i in range(len(mtx[0])):
        idx = [k for k in range(len(mtx[0]))]
        w_indices += list(itertools.combinations(idx, i))

    cnt = 0
    for his in h_indices:
        for wis in w_indices:

            c = count(mtx, his, wis)
            # if len(mtx) == 2: print(his, wis, c)
            if k == c:
                cnt += 1

    print(cnt)

def count(mtx, his, wis):
    # print(his, wis)
    c = 0
    for h in range(len(mtx)):
        if h in his: continue

        for w in range(len(mtx[h])):
            if w in wis: continue
            if mtx[h][w] == '#':
                c += 1

    return c


if __name__ == '__main__':
    h, w, k = [int(i) for i in input().split()]
    mtx = []
    for _ in range(h):
        mtx.append(list(input()))
    main(mtx, k)

Submission status: Accepted

Solution code:
import copy
H, W, K = map(int,input().split())
ls = [list(input()) for i in range(H)]
ans = 0
for i in range(2**H):
  for j in range(2**W):
    A = copy.deepcopy(ls)
    B = 0
    for a in range(H):
      if (i >> a) & 1 == 1:
        for b in range(W):
          A[a][b] = "$"
    for c in range(W):
      if (j >> c) & 1 == 1:
        for d in range(H):
          A[d][c] = "$"
    for k in range(H):
      for l in range(W):
        if A[k][l] == "#":
          B += 1
    if B == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

h, w, k = map(int, input().split())
painted = []
for i in range(h):
    painted.append(list(input()))
ans = 0
for i in range(2**(h+w)):
    painted_dum = np.array(painted)
    for j in range(h):
        if ((i >> j) & 1):
            painted_dum[j, :] = '*'
    for l in range(w):
        if ((i >> (h + l)) & 1):
            painted_dum[:, l] = '*'
    cnt_dum = np.count_nonzero(painted_dum == '#')
    if cnt_dum == k:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
comb = itertools.combinations

H, W, K = map(int, input().split())
C = [list(input()) for _ in range(H)]
C = [[1 if C[k][j] == '#' else 0 for j in range(W)] for k in range(H)]
C = np.array(C)
harray = np.arange(H)
warray = np.arange(W)

Corig = C.copy()

ans = 0
for h in range(H+1):
  for w in range(W+1):
    # import pdb;pdb.set_trace()
    Hc = list(comb(harray, h))
    Wc = list(comb(warray, w))
    for hc in Hc:
      for wc in Wc:
        C = Corig.copy()
        for hcc in hc:
            C[hcc,:] = 0
        for wcc in wc:
          C[:,wcc] = 0
        # print('-----')
        # print(hc, wc, C)
        # print('-----')
        if np.sum(C) == K:
          ans += 1
print(ans)

Submission status: Accepted

Solution code:
def count_black(matrix, mask_rows=[], mask_cols=[]):
  num_black = 0
  for i, row in enumerate(matrix):
    if i in mask_rows:
      continue
    for j, col in enumerate(row):
      if j in mask_cols:
        continue
      if col == "#":
        num_black += 1
  return num_black

def get_patterns(linenum):
  results = []
  patterns = 2**linenum
  for i in range(patterns):
    cmb = []
    if i & 1 == 1:
      cmb.append(0)
    if i & 2 == 2:
      cmb.append(1)
    if i & 4 == 4:
      cmb.append(2)
    if i & 8 == 8:
      cmb.append(3)
    if i & 16 == 16:
      cmb.append(4)
    if i & 32 == 32:
      cmb.append(5)
    results.append(cmb)
  return results

rows, cols, K = [int(x) for x in input().split(" ")]
matrix = []
for row in range(rows):
  matrix.append([x for x in input()])

row_ptrns = get_patterns(rows)
col_ptrns = get_patterns(cols)
result = 0
for row_ptrn in row_ptrns:
  for col_ptrn in col_ptrns:
    if count_black(matrix, row_ptrn, col_ptrn) == K:
      result += 1
print(result)

Submission status: Accepted

Solution code:
from itertools import product
from copy import deepcopy

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

ans = 0
for row in product(['.', '%'], repeat=H):
    if row == tuple(['%']*H):
        continue
    tmp1 = deepcopy(board)
    for h in range(H):
        if row[h] == '%':
            tmp1[h] = ['%']*W
    for col in product(['.', '%'], repeat=W):
        if col == tuple(['%']*W):
            continue
        tmp2 = deepcopy(tmp1)
        for w in range(W):
            if col[w] == '%':
                for h in range(H):
                    tmp2[h][w] = '%'
        if sum(tmp2, []).count('#') == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

import math
import itertools
import random
H, W, K = map(int, input().split())
li = [[''] * W for i in range(H)]
for h in range(H):
    tmp=input()
    for w in range(W):
        li[h][w] = tmp[w]
tmpli = [0]*H
for h in range(H):
    tmpli[h] = h
tmpli2 = [0] * W
for w in range(W):
    tmpli2[w] = w
    ans = 0
for h in range(0,H+1):
    combi_H=list(itertools.combinations(tmpli, h))
    for w in range(0,W+1):
        combi_W = list(itertools.combinations(tmpli2, w))
        for x in combi_H:
            for y in combi_W:
                tx = list(x)
                ty = list(y)
                cnt=0
                for a in range(H):
                    if (a not in tx):
                        continue
                    for b in range(W):
                        if (b not in ty):
                            continue
                        if (li[a][b] == '#'):
                            cnt += 1
                if (cnt == K):
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy
yoko,tate,left = map(int,input().split())
clist = []
ylist = [];tlist = []

for i in range(yoko+1):
    ylist += list(itertools.combinations(range(yoko),i))
for i in range(tate+1):
    tlist += list(itertools.combinations(range(tate),i))

for i in range(yoko):
    clist.append(list(input()))

counter = 0
def color(y,t,clist):
    global yoko,tate
    black = 0
    temp = copy.deepcopy(clist)
    if len(y) == 0:
        for tcomb in t:
            for j in range(yoko):
                temp[j][tcomb] = 'r'

    for ycomb in y:
        temp[ycomb][:] = ['r' for i in range(tate)]
        for tcomb in t:
            for j in range(yoko):
                    temp[j][tcomb] = 'r'

    for yokol in temp:

        black += yokol.count('#')
    if black == left:
        return True
    else:
        return False

for y in ylist:
    for t in tlist:
        if color(y,t,clist):
            counter += 1

print(counter)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
s=[]
for i in range(H):
    ss=str(input())
    s.append(ss)
ans=0

for i in range(2**H):
    seen=[]
    for n in range(H):
        if ((i>>n) & 1):
            seen.append(s[n])
    for j in range(2**W):
        count=0
        for m in range(W):
            if ((j>>m) & 1):
                for l in range(len(seen)):
                    if seen[l][m]=="#":
                        count+=1
        if count==K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

r,c,k = ip()
x = []
ct = 0
for i in range(r):
    s = list(input())
    x.append(s)
    ct += s.count('#')
ans = 0
for ii in range(2**r):
    for jj in range(2**c):
        a = bin(ii)[2:].zfill(r)
        b = bin(jj)[2:].zfill(c)
        #print(a,b)
        new = 0
        for i in range(r):
            for j in range(c):
                if a[i] =='1' or b[j] == '1':
                    if x[i][j] == '#':
                        new += 1
        if ct-new == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

l_h = list(range(H))
l_w = list(range(W))


def count(h, w):
    cnt = 0
    for i in range(H):
        if i in h:
            continue
        for j in range(W):
            if j in w:
                continue
            if MAP[i][j] == '#':
                cnt += 1
    return cnt == K


c = 0

for ch in range(H+1):
    for hs in itertools.combinations(l_h, ch):
        for cw in range(W + 1):
            for ws in itertools.combinations(l_w, cw):
                c += count(list(hs), list(ws))


print(c)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
import numpy as np
def f(x):
  if x=='.':
    return 0
  else:
    return 1
C=np.array([list(map(f,list(input()))) for i in range(H)])
ans=0
for h in range(1,2**H):
  _h=[]
  for i in range(H):
    if h%2==1:
      _h.append(i)
    h=h//2
  
  for w in range(1,2**W):
    _w=[]
    for i in range(W):
      if w%2==1:
        _w.append(i)
      w=w//2
    _h=np.array(_h)
    _w=np.array(_w)
    a=C[_h[:,None],_w]
    if np.count_nonzero(a)==K:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
H,W,K = (int(i) for i in input().split())

# .は白
# #は黒
# K個になれば良い

master_list = []

for i in range(H):
  master_list.append(list(str(input())))

count = 0
for i in range(2**H):
  for j in range(2**W):
    K_count = 0
    bin_i = format(i,"b").zfill(H)
    bin_j = format(j,"b").zfill(W)
    for x in range(H):
      if bin_i[x] == "1":
        for y in range(W):
          if bin_j[y] =="1" and master_list[x][y] == "#":
            K_count += 1
    if K_count == K:
      count+=1

print(count)

Submission status: Accepted

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

pattern = []
for i in range(2 ** (H+W)):
    tmp = [False] * (H+W)
    for j in range(H+W):
        if i >> j & 1:
            tmp[j] = True
    pattern.append(tmp)

import copy

ans = 0
for i in range(len(pattern)):
    copm = copy.deepcopy(maze)
    loop = 1
    for j in range(H+W):
        if loop <= H:
            loop += 1
            if pattern[i][j]:
                copm[j] = ['*' for i in range(W)]
        else:
            if pattern[i][j]:
                for k in range(len(maze)):
                    copm[k][j-H] = '*'
    k = 0
    for i in range(H):
        k += copm[i].count('#')
    if k == K:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

def make_01(H, W, C):
    ban = [[0 for j in range(W)] for i in range(H)]
    for h in range(H):
        S = C[h]
        for w in range(W):
            if S[w] == '.':
                ban[h][w] = 0
            else:
                ban[h][w] = 1
    return ban

def countban(H, W, hc, wc, ban):
    # print(hc, wc)
    # print(ban)
    for h in hc:
        for w in range(W):
            ban[h][w] = 0
    for w in wc:
        for h in range(H):
            ban[h][w] = 0
    # print(ban)
    val = sum(map(sum, ban))
    # print(val)
    # input()
    return val

def ban_copy(H, W, ban):
    bancopy = [[0 for j in range(W)] for i in range(H)]
    for h in range(H):
        for w in range(W):
            bancopy[h][w] = ban[h][w]
    return bancopy

def main():
    H, W, K = map(int, input().split())
    C = [input() for i in range(H)]
    ban = make_01(H, W, C)
    # print(ban)
    cnt = 0
    for n in range(H + 1):
        for hc in combinations(range(H), n):
            for m in range(W + 1):
                for wc in combinations(range(W), m):
                    tmpc = ban_copy(H, W, ban)
                    if K == countban(H, W, hc, wc, tmpc):
                        cnt += 1
    return cnt

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

Submission status: Accepted

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

c = []
ch = [0]*H        # H=iのときの黒の個数
cw = [0]*W        # W=jのときの黒の個数
sum_cnt = 0         #総数
for i in range(H):
    c_buf = input()
    ch[i] = c_buf.count('#')
    for j in range(W):
        if c_buf[j] == '#':
            cw[j] += 1
    sum_cnt += ch[i]
    c.append(c_buf)

import copy
cw_buf = copy.copy(cw)
ans = 0

for i in range(2**H):
    cw = copy.copy(cw_buf)
    cnt = sum_cnt
    for i2 in range(H):
        if (i >> i2) & 1:
            cnt -= ch[i2]
            for j in range(W):
                if c[i2][j] == '#':
                    cw[j] -= 1

    for j in range(2**W):
        cnt2 = cnt
        for j2 in range(W):
            if (j >> j2)&1:
                cnt2 -= cw[j2]

        if cnt2 == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy
h, w, k = map(int, input().split())
chiz_m = [[] for _ in range(w)]
for _ in range(h):
    tmp_list = input()
    for i in range(w):
        chiz_m[i].append(tmp_list[i])
chiz = copy.deepcopy(chiz_m)
n=12
perms=[]
for i in range(2**n):
    list2 = []
    for j in range(n):
        if (i >> j) &1 == 1:
            list2.append(1)
        else:
            list2.append(0)
    perms.append(list2)

def draw(rc):
    if rc < 6:
        for i in range(w):
            chiz[i][rc] = '='
    else:
        for i in range(h):
            chiz[rc-6][i] = '='
res = 0
for perm in perms:
    for idx,x in enumerate(reversed(perm[:6])):
        if x == 1:
            break
    if 6-idx > h:
        continue
    for idx,x in enumerate(reversed(perm[-6:])):
        if x == 1:
            break
    if 6-idx > w:
        continue
    for b in range(12):
        if b < 6:
            if b < h:
                if perm[b] == 1:
                    draw(b)
            else:
                continue
        else:
            if b-6 < w:
                if perm[b] == 1:
                    draw(b)
            else:
                continue
    cnt = 0
    for i in range(w):
        for j in range(h):
            if chiz[i][j] == "#":
                cnt += 1
    #print(perm)
    #print(cnt)
    if cnt == k:
        res += 1
    chiz = copy.deepcopy(chiz_m)
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import copy
import numpy as np
from itertools import combinations


def main():
    H, W, K = map(int, input().split())
    c = np.array([list(input()) for _ in range(H)], dtype='str')
    cnt = 0

    h_pattern = []
    w_pattern = []

    for h_num in range(H + 1):
        h_pattern.extend(list(combinations(range(H), h_num)))

    for w_num in range(W + 1):
        w_pattern.extend(list(combinations(range(W), w_num)))

    cnt = 0
    for hp1 in h_pattern:
        for wp1 in w_pattern:
            d = copy.deepcopy(c)
            for hp2 in hp1:
                d[hp2, :] = 'x'
            for wp2 in wp1:
                d[:, wp2] = 'x'
            if np.count_nonzero(d == '#') == K:
                cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations

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

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

def make(a):
    new = []
    for i in a:
        new.append(c[i])
    return new

def counter(lines, b):
    cnt = 0

    for i in b:
        for j in lines:
            if j[i] == '#':
                cnt += 1
    if cnt == k:
        return 1
    else:
        return 0
            


count = 0
for r in range(1,h+1):
    for i in combinations(range(h), r):
        new = make(i)
        for l in range(1, w+1):
            for j in combinations(range(w), l):
                num =counter(new, j)
                count += num
print(count)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
h,w,k=map(int,input().split())
c=[input() for _ in range(h)]
ans=0
n=2**h
m=2**w
for x in range(n):
    for y in range(m):
        count=0
        for i in range(h):
            for j in range(w):
                if (x>>i)&1 and (y>>j)&1 and c[i][j]=="#":
                    count+=1
        if count==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from itertools import combinations, product

H, W, K = map(int, input().split())
board = []
for _ in range(H):
    row = input()
    row = [r == "#" for r in row]
    board.append(row)

all_h_comb = [()]
for r in range(1, H):
    comb_obj = combinations(range(H), r)
    all_h_comb += list(comb_obj)
all_w_comb = [()]
for c in range(1, W):
    comb_obj = combinations(range(W), c)
    all_w_comb += list(comb_obj)
all_comb = list(product(all_h_comb, all_w_comb))

res = 0
for comb in all_comb:
    r, c = comb
    tmp_board = deepcopy(board)
    for _r in r:
        tmp_board[_r] = [False] * W
    for _c in c:
        for b in tmp_board:
            b[_c] = False
    s = sum(sum(l) for l in tmp_board)
    if s == K:
        res += 1
print(res)

Submission status: Accepted

Solution code:
h,w,v = map(int,input().split())
c = []
for i in range(h):
    c.append(input())
b = 0
x = []
for i in range(h):
    x.append([0]*w)
    for j in range(w):
        if(c[i][j] == '#'):
            b += 1

p = 0
for i in range(2**h):
    for j in range(2**w):
        x = bin(64^i)
        y = bin(64^j)
        cnt = 0
        for k in range(1,h+1):
            for l in range(1,w+1):
                if(x[-k] == '1' and y[-l] == '1' and c[k-1][l-1] == '#'):
                    cnt += 1
        if(cnt == v):
            p += 1
print(p)

Submission status: Accepted

Solution code:
#! env/bin/local python3
# -*- coding: utf-8 -*-

import numpy as np


def fill_red(height, width, table, h, w):
    for hn in range(h):
        if (2 ** hn) & height == (2 ** hn):
            table[hn:hn + 1] = '+'

    for wn in range(w):
        if (2 ** wn) & width == (2 ** wn):
            table[:, wn:wn+1] = '+'

    return table


def count_black(table, k):
    if np.sum(table == "#") == k:
        return True
    else:
        return False


def main():
    h, w, k = map(int, input().split())
    original_table = []

    while True:
        try:
            row = list(input())
            original_table.append(row)
        except EOFError:
            break

    original_table = np.array(original_table)

    counter = 0
    for height in range(2**h):
        for width in range(2**w):
            table = original_table.copy()
            table = fill_red(height, width, table, h, w)
            if count_black(table, k):
                counter += 1

    print(counter)


if __name__ == '__main__':
    main()