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:
from itertools import combinations

h,w,k = map(int,input().split())
cli = [list(input()) for _ in range(h)]

black = 0
for wli in cli:
    black += wli.count('#')


answer = 0
for i in range(h+w+1):
    combis = list(combinations(range(1,h+w+1),i))

    # 1パターン
    for combi in combis:
        tmp_black = black
        red_row = []
        red_column = []
        for red in combi:
            if 1 <= red <= h:
                red_row.append(red-1)
            elif h+1 <= red <= h+w:
                red_column.append(red-h-1)

        for j, wli in enumerate(cli):
            if j in red_row:
                tmp_black -= wli.count('#')
                continue

            for r in red_column:
                if wli[r] == '#':
                    tmp_black -= 1
            
        if tmp_black == k:
            answer += 1

print(answer)

Submission status: Accepted

Solution code:
import copy

def find(h):
    bits_active = {}
    for i in range(pow(2,h)):
        x = bin(i)[2:]
        if len(x) < h:
            x = '0'*(h-len(x))+x

        ones = x.count('1')
        if ones not in bits_active.keys():
            bits_active[ones] = []

        bits_active[ones].append(x)

    return bits_active

def good(grid,h,w,row_perm,col_perm,k):
    temp = copy.deepcopy(grid)
    for i in range(h):
        if row_perm[i] == '1':
            for j in range(w):
                temp[i][j] = 'r'

    for j in range(w):
        if col_perm[j] == '1':
            for i in range(h):
                temp[i][j] = 'r'

    count = 0
    for i in range(h):
        for j in range(w):
            if temp[i][j] == '#':
                count += 1

    if count == k:
        return True

    return False

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

    bits_active_rows = find(h)
    bits_active_cols = find(w)
    total = 0
        
    for rows_chosen in range(h+1):
        for cols_chosen in range(w+1):
            for row_perm in bits_active_rows[rows_chosen]:
                for col_perm in bits_active_cols[cols_chosen]:
                    if good(grid,h,w,row_perm,col_perm,k):
                        total += 1

    print(total)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from copy import deepcopy
from itertools import product
h, w, push = map(int, input().split())
ans = 0
an = []
a = ['@'] * w
c = []
d = []
for q in range(h):
    _ = list(input())
    c.append(_)
    d.append(_)
for H in product([0, 1], repeat=h):
    for W in product([0, 1], repeat=w):
        c = deepcopy(d)
        count = 0
        for i, j in enumerate(H):
            if j:
                c[i] = a
        for k, l in enumerate(W):
            if l:
                for x in range(h):
                    c[x][k] = '@'
        for hi in c:
            for wi in hi:
                if wi == '#':
                    count += 1
        an += [count]
for answer in an:
    if answer == push:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

for i in range(H):
	for h in range(W):
		if C_[i][h]==".":temp.append(0)
		else:temp.append(1)
	C.append(temp)
	temp=[]
C=np.array(C)

HP_=[h for h in range(H)]
HP=[]
for r in range(H):
	HP.append(list(itertools.combinations(HP_,r)))
WP_=[w for w in range(W)]
WP=[]
for r in range(W):
	WP.append(list(itertools.combinations(WP_,r)))
#print(HP,WP)

for i in range(len(HP)):
	for hp in HP[i]:
		C_del_wp=np.delete(C,hp,0)
		#print(C_del_wp)
		
		for h in range(len(WP)):
			for wp in WP[h]:
				C_del=np.delete(C_del_wp,wp,1)
				#print(C_del)
				#print(np.count_nonzero(C_del==1))
				if np.count_nonzero(C_del==1)==K:
					ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
H, W, K = map(int, input().split())
C = []
for _ in range(H):
    C.append(list(input()))

ans = 0
def dfs(HSelect, WSelect):
    global ans, H, W, K
    if len(HSelect) == H and len(WSelect) == W:
        count = 0
        for j in range(W):
            for i in range(H):
                if HSelect[i] or WSelect[j]:
                    continue
                if C[i][j] == "#":
                    count += 1
        if count == K:
            ans += 1
        return

    Hnext = HSelect[:]
    Wnext = WSelect[:]
    if len(HSelect) < H and len(WSelect) < W:
        dfs(Hnext+[False], Wnext+[False])
        dfs(Hnext+[True], Wnext+[False])
        dfs(Hnext+[False], Wnext+[True])
        dfs(Hnext+[True], Wnext+[True])
    elif len(HSelect) < H:
        dfs(Hnext+[False], Wnext)
        dfs(Hnext+[True], Wnext)
    elif len(WSelect) < W:
        dfs(Hnext, Wnext+[False])
        dfs(Hnext, Wnext+[True])


dfs([], [])
print(ans)

Submission status: Accepted

Solution code:
import itertools
h,w,k=map(int,input().split())
C=[]
for _ in range(h):
    c=input()
    C.append(c)
l1=list(itertools.product([0,1],repeat=h))
l2=list(itertools.product([0,1],repeat=w))
count=0
for i in range(2**h):
    for j in range(2**w):
        black=0
        for ii in range(h):
            for jj in range(w):
                if l1[i][ii]==0 and l2[j][jj]==0 and C[ii][jj]=='#':
                    black+=1
        if black==k:
            count+=1
print(count)

Submission status: Accepted

Solution code:
import copy

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

ans = 0
for i in range(2**H):
  #print(i)
  tmp = copy.deepcopy(S)      
  #print(tmp)
  keta_i = 0
  ii = i
  while ii > 0:
    if ii & 1:
      #print(tmp)
      for k in range(W):
        tmp[keta_i][k] = "."
    keta_i += 1
    ii = ii >> 1
  #if i == 1:
    #print(tmp)
  for j in range(2**W):
    tmp2 = copy.deepcopy(tmp)
    keta_j = 0
    jj = j
    while jj > 0:
      if jj & 1:
        for l in range(H):
          #print(i,j,k,l,keta_i,keta_j)
          #print(tmp2)
          tmp2[l][keta_j] = "."
      keta_j += 1
      jj = jj >> 1
      #print(j)
    
    count = 0
    for l in range(H):
      for k in range(W):
        if tmp2[l][k] == "#":
          count += 1
    
    if count == K:
      ans += 1
      #print(i,j)
      
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

b = np.array([['.' for i in range(W)] for j in range(H)])

for h in range(H):
    b[h] = list(input())
    
h_conb = []
w_conb = []
for i in range(1,H+1):
    h_conb += list(itertools.combinations(range(H), i))
for i in range(1,W+1):
    w_conb += list(itertools.combinations(range(W), i))

count = 0

if K == 0:
    count += 1

for h in h_conb:
    for w in w_conb:
        #print(h, w)
        #print(b[list(h)][:,list(w)])
        if np.count_nonzero(b[list(h)][:,list(w)] == '#') == K:
            count += 1

print(count)

Submission status: Accepted

Solution code:
import numpy as np
H,W,K=map(int,input().split())
s=[]
for i in range(H):
    a=list(input())
    a=[0 if moji=="." else 1 for moji in a]
    s.append(a)
s=np.array(s)
count=0
for i in range(2**H):
    l1=[]
    ss = s.copy()
    for j in range(H):
        if i>>j&1:l1.append(j)
    for height in l1:
        ss[height, :] = 0
    for k in range(2**W):
        l2=[]
        ss2=ss.copy()
        for m in range(W):
            if k>>m&1:l2.append(m)
        for width in l2:
            ss2[:,width]=0
        if np.sum(ss2)==K:
            count+=1

print(count)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[list(input()) for i in range(h)]
black =0
for i in range(h):
  for j in range(w):
    if c[i][j]=='#':
      black+=1
      c[i][j]=1
    else:
      c[i][j]=0
ans=0
for i in range(2**h):
  for j in range(2**w):
    cnt = black
    for p in range(h):
      for q in range(w):
        if i >> p & c[p][q]:
          cnt-=1
          continue
        if j >> q & c[p][q]:
          cnt-=1
    if cnt == k:
      #print(i,j,cnt)
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import product

def main():

    input = stdin.readline

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

    s = [] * H

    for _ in range(H):
        s.append(str(input())[:-1])

    ans = 0

    for h in list(product([0,1], repeat=H)):
        for w in list(product([0,1], repeat=W)):
            tmp_s = s.copy()
            count_num = 0

            for w_num in range(W):
                if w[w_num] == 1:
                    for w_s in range(H):
                        tmp_s[w_s] = tmp_s[w_s][:w_num] + "x" + tmp_s[w_s][w_num+1:]
        
            for h_num in range(H):
                if h[h_num] == 1:
                    tmp_s[h_num] = ""


            for i in tmp_s:
                count_num += i.count("#")

            if count_num == K:
                ans += 1


    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import copy
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))


H, W, K = LI()
c = []
for i in range(H):
    tmp_l = S()
    c.append([1 if c == "#" else 0 for c in tmp_l])


num_pattern = 0
for h in range(2 ** H):
    format_str = "{:0" + str(H) + "b}"
    h_update = [c == "1" for c in reversed(format_str.format(h))]

    for w in range(2 ** W):
        format_str = "{:0" + str(W) + "b}"
        w_update = [c == "1" for c in reversed(format_str.format(w))]
        # print(h_update, w_update)

        cc = copy.deepcopy(c)
        for i, flag in enumerate(h_update):
            if flag:
                cc[i] = [0 for _ in range(W)]
        for i, flag in enumerate(w_update):
            if flag:
                for j in range(H):
                    cc[j][i] = 0

        total = sum([sum(cc[i]) for i in range(H)])
        if total == K:
            num_pattern += 1

print(num_pattern)

Submission status: Accepted

Solution code:
import copy
H, W, K = map(int, input().split())
Co = [list(map(str, input())) for _ in range(H)]
ans = 0
for i in range(2 ** H):
  C = copy.deepcopy(Co)
#書き換え
  for j in range(H):
    if (i >> j & 1) == 1:
      for k in range(W):
        C[j][k] = ""
  for l in range(2 ** W):
    C1 = copy.deepcopy(C)
    for m in range(W):
      if (l >> m & 1) == 1:
        for n in range(H):
          C1[n][m] = ""
#数え上げ
    cnt = 0
    for o in range(H):
      for p in range(W):
        if C1[o][p] == "#":
          cnt += 1
    if cnt == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

# H, W, K = 2, 3, 4
# ARR = [
#     "..#",
#     "###",
# ]
#
# H, W, K = 6, 6, 8
# ARR = [
#     "..##..",
#     ".#..#.",
#     "#....#",
#     "######",
#     "#....#",
#     "#....#"
# ]

H, W, K = map(int, input().split())
ARR2 = np.zeros((H, W))
for i in range(H):
    s = list(input())
    for j in range(W):
        if s[j] == ".":
            ARR2[i][j] == 0
        else:
            ARR2[i][j] = 1

# ARR2 = np.zeros((H, W))
# for i in range(H):
#     for j in range(W):
#         if ARR[i][j] == ".":
#             ARR2[i][j] == 0
#         else:
#             ARR2[i][j] = 1


def calclulate(h, w, k, arr):
    result = 0
    hIndex = [i for i in range(h)]
    wIndex = [i for i in range(w)]

    for hChooseNum in range(h + 1):
        for wChooseNum in range(w + 1):
            for m in itertools.combinations(hIndex, hChooseNum):
                for n in itertools.combinations(wIndex, wChooseNum):

                    tmpArr = arr.copy()

                    for _m in m:
                        tmpArr[_m, :] = 0
                    for _n in n:
                        tmpArr[:, _n] = 0

                    if np.sum(tmpArr == 1) == k:
                        result += 1
    print(result)


calclulate(H, W, K, ARR2)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
init_kuro = 0
HW = []
for i in range(H):
    t = list(input())
    k = t.count('#')
    HW.append(t)
    init_kuro += k

#print(HW)
#print(init_kuro)
import itertools

tate = list(itertools.product([0, 1], repeat=H))
yoko = list(itertools.product([0, 1], repeat=W))

ans = 0


def solve(T, Y):
    tmp = 0
    for i, t in enumerate(T):
        if t == 1:
            for j, h in enumerate(HW[i]):
                if h == '#' and Y[j] == 0:
                    tmp += 1

    for i, y in enumerate(Y):
        if y == 1:
            for hw in HW:
               if hw[i] == '#':
                   tmp +=1

    if init_kuro - tmp == K:
        return 1
    else:
        return 0


ans = 0
for T in tate:
    for Y in yoko:
        ans += solve(T, Y)
print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2**H):
    for j in range(2**W):
        c_ = copy.deepcopy(c)
        for k in range(H):
            if ((i >> k) & 1):
                for l in range(W):
                    c_[k][l] = '-'
        for k in range(W):
            if ((j >> k) & 1):
                for l in range(H):
                    c_[l][k] = '-'
        if(sum([m.count('#') for m in c_]) == K):
            ans += 1


print(ans)

Submission status: Accepted

Solution code:
import numpy

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

data = []
for i in range(H):
    data.append(list(map(lambda x: int(x == "#"), input())))

data = numpy.asarray(data)

result = 0
for i in range(2**H):
    # bitが0なら未選択
    H_matrix = numpy.asarray([int(bool(i & (1 << h))) for h in range(H)])

    for j in range(2**W):
        W_matrix = numpy.asarray([int(bool(j & (1 << w))) for w in range(W)])
        if numpy.sum((data * W_matrix).T * H_matrix) == K:
            result += 1

print(result)

Submission status: Accepted

Solution code:
from itertools import combinations as comb
h,w,k = map(int,input().split())

def check(r,c,a):
  b = 0
  for i in range(h):
    if r[i]:
      for j in range(w):
        if c[j] and a[i][j] == '#':
          b += 1
  return int(b==k)

a = []
for _ in range(h):
  a.append(list(input()))
row_comb = []
col_comb = []
rows = [i for i in range(h)]
cols = [i for i in range(w)]
for i in range(h+1):
  row_comb += list(comb(rows,i))
for i in range(w+1):
  col_comb += list(comb(cols,i))
ans = 0
for row in row_comb:
  for col in col_comb:
    r = [True]*h
    c = [True]*w
    for i in row:
      r[i] = False
    for i in col:
      c[i] = False
    ans += check(r,c,a)
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
import numpy as np
mod = 10 ** 9 + 7
H, W, K = MAP()
L = [input() for i in range(H)]
S = [[0] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if L[i][j] == "#":
            S[i][j] = 1
S_n = np.array(S)

import itertools
L = [0, 1] #生成する数字


h_b = list(itertools.product([0, 1], repeat=H))
w_b = list(itertools.product([0, 1], repeat=W))


mask = [[0] * W for i in range(H)]

cnt = 0

for h_t in h_b:
    for w_t in w_b:
        for i, h_ in enumerate(h_t):
            for j, w_ in enumerate(w_t):
                mask[i][j] = h_ * w_
        m_n = np.array(mask)
        ada = np.sum(m_n * S_n)
        if ada == K:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import itertools
h,w,k = map(int, input().split())
c = []
for i in range(h):
    a = input()
    for j in range(w):
        if a[j] == '#':
            c.append((i,j))

ans = 0

sel = ['h'+str(i) for i in range(h)]
sel += ['w'+str(i) for i in range(w)]
for m in range(h+w):
    for v in  itertools.combinations(sel,m):
        count = [1 for kk in range(len(c))]
        for vv in v:
            if vv[0]=='h':
                for e,(i,j) in enumerate(c):
                    if i == int(vv[1]):
                        count[e] = 0
            if vv[0]=='w':
                for e,(i,j) in enumerate(c):
                    if j == int(vv[1]):
                        count[e] = 0
        if sum(count) == k:
            ans += 1


print(ans)

Submission status: Accepted

Solution code:
from itertools import product

H, W, K = map(int, input().split())
tiles = []
n = 0
for h in range(H):
    row = list(input())
    tiles.append(row)

cols, rows = [0] * W, [0] * H
for x in range(W):
    c = 0
    for y in range(H):
        if tiles[y][x] == "#":
            c += 1
    cols[x] = c
for y in range(H):
    c = 0
    for x in range(W):
        if tiles[y][x] == "#":
            c += 1
    rows[y] = c
n = sum(cols)

count = 0
for hy in product([0, 1], repeat=H):
    for hx in product([0, 1], repeat=W):
        c = set()
        for i, fy in enumerate(hy):
            if fy:
                for x in range(W):
                    if tiles[i][x] == "#":
                        c.add((x, i))
        for j, fx in enumerate(hx):
            if fx:
                for y in range(H):
                    if tiles[y][j] == "#":
                        c.add((j, y))
        if n - len(c) == K:
            count += 1
print(count)

Submission status: Accepted

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

#K個の#が残るのは何通りか
i_list=[i for i in range(H)]
j_list=[j for j in range(W)]
#塗り替え
for i in range(H+1):
    i_ = list(itertools.combinations(i_list, i))#0-H個選ぶ
    for j in range(W+1):
        j_ = list(itertools.combinations(j_list, j))#0-H個選ぶ
        
        #あるNGパターンにおいて
        for ii in i_: 
            for jj in j_:
                count=0
                #print("START") 
                #print(ii,jj) 
                #各マスを判定
                for iii in range(H):
                    for jjj in range(W):
                        if c[iii][jjj]=="#" and (iii not in ii) and (jjj not in jj):
                            #print(iii,jjj) 
                            count+=1
                #print(count)
                if count==K:
                    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    H, W, K = map(int, input().split())
    C = [input() for _ in [0] * H]

    ans, total = 0, 0
    for c in C:
        total += c.count('#')

    for mask in range(1 << H):
        c = C[:]
        x = []
        for i in range(H):
            if mask & 1 << i:
                x.append(i)
        n = total
        for i in x:
            n -= c[i].count('#')
            c[i] = '.' * W

        for mask in range(1 << W):
            k, y = n, []
            for i in range(W):
                if mask & 1 << i:
                    y.append(i)
            for i in range(H):
                for j in y:
                    if c[i][j] == '#':
                        k -= 1
            if k == K:
                ans += 1
    print(ans)


main()

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
import copy
p = []
for i in range(h):
    q = input()
    q = list(q)
    p.append(q)
def kaz(p):
    an = 0
    for i in range(len(p)):
        for j in range(len(p[i])):
            if p[i][j] == '#':
                an += 1
    return an
ans = 0
for i in range(2**(h+w)):
    s = copy.deepcopy(p)
    u = copy.deepcopy(i)
    for j in range(h):
        if u & 1:
            s[j] = [0]*w
        u = u >> 1
    u = copy.deepcopy(i)
    u = u >> h
    for e in range(w):
        if u &1:
            for m in range(h):
                s[m][e] = 0
        u = u >> 1
    if kaz(s) == k:
        ans += 1
print(ans)

Submission status: Accepted

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

from pprint import pprint
import copy
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


H, W, K = map(int, input().split())
field = []
for _ in range(H):
    line = list(input())
    field.append(line)
# pprint(field)


def calc(field_copy):
    res = 0
    for i in range(H):
        for j in range(W):
            if field_copy[i][j] == '#':
                res += 1
    return res


res = 0
for row in range(2 ** H):
    for col in range(2 ** W):
        field_copy = copy.deepcopy(field)
        for i_row in range(H):
            if row & (1 << i_row):
                for j_col in range(W):
                    field_copy[i_row][j_col] = '_'
        for i_col in range(W):
            if col & (1 << i_col):
                for j_row in range(H):
                    field_copy[j_row][i_col] = '_'
        if calc(field_copy) == K:
            res += 1

print(res)

Submission status: Accepted

Solution code:
import copy
import itertools

H, W, K = list(map(int, input().split()))
squares = {}

for i in range(H):
    c = list(input())
    for j in range(W):
        squares[(i, j)] = c[j]

cs = []
for i in range(H + W + 1):
    cs += list(itertools.combinations(range(1, H + W + 1), i))

count = 0
for c in cs:
    copy_squares = copy.copy(squares)
    for x in c:
        if x <= H:
            for j in range(W):
                copy_squares[(x - 1, j)] = "."
        else:
            x -= H
            for i in range(H):
                copy_squares[(i, x - 1)] = "."
    if list(copy_squares.values()).count("#") == K:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import copy
h,w,kl = map(int, input().split(" "))
b=list(list(input()) for i in range(h))
count = 0
ans = 0
for i in range(h):
  for j in range(w):
    if b[i][j] == "#":
      count += 1
      
for hi in range(2 ** (h + w)):
  a = copy.deepcopy(b)
  temp = count
  for hj in range(h):
    if (hi >> hj) & 1:
      for l in range(w):
        if a[hj][l] == "#":
          temp -= 1
        a[hj][l] = "*"
  for wj in range(w):
    if (hi >> wj) & (2 ** h):
      for k in range(h):
        if a[k][wj] == "#":
          temp -= 1
        a[k][wj] = "*"
  if temp == kl:
    ans += 1 
  #print(hi, a)
  
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np


readline = sys.stdin.readline
read = sys.stdin.read

h, w, k = map(int, input().split())
a = np.array(list(read())).reshape([h,-1])[:,:-1]
b = np.where(a=='.', 0, 1)

ans = 0
for i in range(2**h):
    for j in range(2**w):
        I = np.array(list(format(i, '0'+str(h)+'b')), dtype=np.int64)
        J = np.array(list(format(j, '0'+str(w)+'b')), dtype=np.int64)
        if np.sum((b[I==1])[:,J==1]) == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main1():
    H,W,K=map(int,input().split())
    c=[input() for _ in range(H)]
    ans=0
    cn=0
    for i in range(2**H):
        t=str(bin(i))[2:]
        if len(t)!=H:
            t="0"*(H-len(t))+t
        for j in range(2**W):
            cn=0
            tt=str(bin(j))[2:]
            if len(tt)!=W:
                tt="0"*(W-len(tt))+tt
            #検証
            for i_i,v_i in enumerate(t):
                for i_j,v_j in enumerate(tt):
                    if v_i =="0" and v_j == "0":
                        if c[i_i][i_j]=="#":
                                cn+=1
            if cn==K:
                ans+=1
    print(ans)
main1()

Submission status: Accepted

Solution code:
from copy import deepcopy
import itertools

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

maps = [list(input()) for _ in range(h)]
ans = 0

for i in range(2 ** h):
    for j in range(2 ** w):
        tmp_maps = deepcopy(maps)
        for x in range(h):
            if (i >> x) & 1:
                tmp_maps[x] = list('.' * w)
        for y in range(w):
            if (j >> y) & 1:
                for l in range(h):
                    tmp_maps[l][y] = '.'
        #print(i, j)
        #for map in tmp_maps:
        #    print(map)
        #print('')
        #print(list(itertools.chain.from_iterable(tmp_maps)))
        cnt = list(itertools.chain.from_iterable(tmp_maps)).count('#')
        if cnt == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy

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

for i in range(2 ** (H + W)):
    V = copy.deepcopy(C)
    for j in range(H + W):
        if (i >> j) & 1:
            if j < H:
                for k in range(W):
                    V[j][k] = "R"
            else:
                for k in range(H):
                    V[k][j - H] = "R"
    if sum(V, []).count("#") == K:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import chain,combinations
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

H, W, K = map(int, input().split())
c = []
for h in range(H):
    c.append(list(map(str, input())))
c = np.array(c)


h_list = [i for i in range(H)]
w_list = [i for i in range(W)]

h_comb_list = list(powerset(h_list))
w_comb_list = list(powerset(w_list))
#h_comb_list.remove(())
#w_comb_list.remove(())

comb_list = []
x = 0
for h_temp in h_comb_list:
    for w_temp in w_comb_list:
        if -1 in h_temp and -1 in w_temp:
                x += 1
        else:
            comb_list.append({'h':h_temp, 'w':w_temp})
ans = 0
for comb in comb_list:
    h_r = comb['h']
    w_r = comb['w']
    h_temp = [i for i in range(H)]
    w_temp = [i for i in range(W)]
    #print(h_r, w_r)
    if len(h_r) > 0:
        for h in h_r:
            h_temp.remove(h)
    if len(w_r) > 0:
        for w in w_r:
            w_temp.remove(w)
    #print(h_temp, w_temp)
    if np.sum(c[h_temp, :][:, w_temp] == '#') == K:
        #print(h_r, w_r)
        #print(c[h_temp, :][:, w_temp])
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

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

rows = []
for i in range(h + 1):
    rows += list(itertools.combinations(list(range(0, h)), i))

cols = []
for i in range(w + 1):
    cols += list(itertools.combinations(list(range(0, w)), i))

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

result = 0
for row in rows:
    for col in cols:
        temp = copy.deepcopy(data)
        for r in row:
            for j in range(w):
                temp[r][j] = 'r'
        for c in col:
            for i in range(h):
                temp[i][c] = 'r'
        count = 0
        for i in range(h):
            for j in range(w):
                if temp[i][j] == '#':
                    count += 1
        if count == k:
            result += 1

print(result)

Submission status: Accepted

Solution code:
import sys
import copy
import itertools
sys.setrecursionlimit(10**6)


def sum(table):
    t = 0
    for i in range(len(table)):
        for j in range(len(table[i])):
            t += table[i][j]
    return t


def main(input, print):
    h, w, K = map(int, input().split())
    table = [[0 for _ in range(w)] for _ in range(h)]

    for i in range(h):
        s = list(input())
        for j in range(w):
            if s[j] == '#':
                table[i][j] = 1
    ht = []
    for i in range(h+1):
        for v in itertools.combinations(range(h), i):
            ht.append(v)
    wt = []
    for i in range(w+1):
        for v in itertools.combinations(range(w), i):
            wt.append(v)

    ans = 0
    for i in range(len(ht)):
        now = copy.deepcopy(table)
        for j in range(len(ht[i])):
            for k in range(w):
                now[ht[i][j]][k] = 0
        for j in range(len(wt)):
            now2 = copy.deepcopy(now)
            for k in range(len(wt[j])):
                for l in range(h):
                    now2[l][wt[j][k]] = 0
            if sum(now2) == K:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

Solution code:
import copy

h, w, s = map(int, input().split())
li = [list(input()) for _ in range(h)]
ans = 0

for i in range(h):
    for j in range(w):
        if li[i][j] == '#':
            li[i][j] = 1
        else:
            li[i][j] = 0

cnt = 0

for i in range(2 ** h):
    for j in range(2 ** w):
        swicth1 = [0]*h
        swicth2 = [0]*w
        
        for k in range(h):
            for l in range(w):
                if ((i >> k) & 1):
                    swicth1[h - 1 - k] = 1

                if ((j >> l) & 1):
                    swicth2[w - 1 - l] = 1
        tmp = copy.deepcopy(li)
        
        for x in range(h):
            for y in range(w):
                if swicth1[x] == 1 or swicth2[y] == 1:
                    tmp[x][y] = 0
        cnt = 0
        for x in range(h):
            cnt += sum(tmp[x])
        
        if cnt == s:
            ans += 1
                
print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(1 << H):
    drow = []
    for i in range(H):
        if (bit >> i) % 2 == 1:
            drow.append(i)
    for bit2 in range(1 << W):
        dcol = []
        for j in range(W):
            if (bit2 >> j) % 2 == 1:
                dcol.append(j)
        b = 0
        for y in range(H):
            for x in range(W):
                if y in drow:
                    continue
                if x in dcol:
                    continue
                if C[y][x] == "#":
                    b += 1
        if b == K:
            ans += 1
print(ans)