Problem:


Score : 300 points

Problem Statement

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

Consider doing the following operation:

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

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

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

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

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

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

Sample Output 4

208



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


Sample output:
5

Submission status: Accepted

Solution code:
import itertools
import copy
h, w, k = map(int, input().split())
lis = [list(map(str, *input().split())) for _ in range(h)]
gyo = list(itertools.product([0,1], repeat=h))
retu = list(itertools.product([0,1], repeat=w))
l = copy.deepcopy(lis)
ans =0
for i in gyo:
    for j in retu:
        scount = 0
        for x in range(h):
            if i[x] == 1:
                l[x] = ["."]*w
        for y in range(w):
            if j[y] == 1:
                for z in range(h):
                    l[z][y] = "."
        for p in range(h):
            scount += l[p].count("#")
        if scount == k:
            ans +=1
        l = copy.deepcopy(lis)
print(ans)

Submission status: Accepted

Solution code:
import math
def bittoarr(x):
  i = 1
  ret = []
  while i <= x:
    if i & x:
      ret.append(int(math.log2(i)))
    i <<= 1
  return ret
h, w, k = map(int, input().split())
c = []
result = 0
for i in range(h):
  c.append(input())
hh = 2 ** h
ww = 2 ** w
for i in range(hh):
  row = []
  #print(bittoarr(i))
  for tmp in bittoarr(i):
    row.append(c[tmp])
  #print(row)
  for j in range(ww):
    sm = 0
    for r in row:
      for cl in bittoarr(j):
        if r[cl] == "#":
          sm += 1
    if sm == k:
      result += 1
print(result)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
h,w,k = readInts()
c = [input() for _ in range(h)]
# dp = [[0] * (w+1) for _ in range(h+1)]
# dp[0][0] = 1
# # dp[i+1][j+1] = i列目, j行目を選んだ時
black = 0
for nya in c:
    black += nya.count('#')

# 視点からどのくらいの距離を見るか
ans = 0

# if black == k:
#     print(1)
# else:
for bitx in range(1 << w):
    for bity in range(1 << h):
        cost = 0
        table = [[0] * w for _ in range(h)]
        for y in range(h):
            for x in range(w):
                if bitx & (1 << x):
                    for i in range(h):
                        table[i][x] = 1
                if bity & (1 << y):
                    for i in range(w):
                        table[y][i] = 1
        for y in range(h):
            for x in range(w):
                if table[y][x] != 1:
                    if c[y][x] == '#':
                        cost += 1
        if cost == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

n_tate, n_yoko, n_kuro = map(int, input().split())

matrix = []
for _ in range(n_tate):
    yoko = [_ for _ in str(input())]
    yoko2 = []
    for char in yoko:
        if char == "#":
            yoko2.append(1)
        else:
            yoko2.append(0)
    matrix.append(yoko2)

matrix2 = np.array(matrix)

tmp = [0, 1]
tate_use_list  = list(itertools.product(tmp, repeat=n_tate))
yoko_use_list  = list(itertools.product(tmp, repeat=n_yoko))
# print("original")
# print(np.array(matrix))
# print()

i = 0
counter = 0
for tate_use in tate_use_list:
    for yoko_use in yoko_use_list:
#         print(i)
#         print("tate use:", tate_use)
#         print("yoko_use:", yoko_use)

        matrix3 = matrix2.copy()
        A = np.array(tate_use).reshape(-1, 1)
        B = np.array(yoko_use)

        matrix4 = matrix3 * A * B

        total = np.sum(matrix4)
        i += 1
#         print(matrix4)
#         print("total:", total)
        if total == n_kuro:
#             print("  -> OK!")
            counter += 1
#         print()
        
print(counter)

Submission status: Accepted

Solution code:
from copy import deepcopy
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    C = [list(readline().strip()) for _ in range(H)]
    
    ans = 0
    for i in range(2**(H+W)):
        c = deepcopy(C)
        for j in range(H+W):
            if (i >> j) & 1:
                if j < H:
                    for s in range(W):
                        c[j][s] = "."
                else:
                    for k in range(H):
                        c[k][j-H] = "."
        cnt = 0
        for line in c:
            cnt += line.count("#")
        if cnt == K:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

c_list = []

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

import numpy as np
import itertools

c_array = np.array(c_list)

result = 0

for i in range(H+1):
    for j in range(W+1):
  
        select_row =  list(itertools.combinations(range(H),i))  
        select_col =  list(itertools.combinations(range(W),j))    
  
        finish = c_array[select_row,:][:,:,select_col]
        partial_result = np.sum(np.sum(np.sum(finish =='#',axis=3),axis=1) == K)
  
        result = result + partial_result
    
print(result)

Submission status: Accepted

Solution code:
from itertools import combinations

h, w, k = map(int, input().split(" "))
colored_blocks = []
result = 0
for i in range(h):
    for j, v in enumerate(list(input())):
        if v == "#":
            colored_blocks.append({"row": i, "col": j})

for i in range(0, h + 1):
    for t_r in combinations(list(range(h)), i):
        row_filtered_candidates = [b for b in colored_blocks if b["row"] not in t_r]
        for j in range(0, w + 1):
            for t_c in combinations(list(range(w)), j):
                col_filtered_candidates = [
                    b for b in row_filtered_candidates if b["col"] not in t_c
                ]
                if len(col_filtered_candidates) == k:
                    result += 1
print(result)

Submission status: Accepted

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

from collections import Counter
import itertools
import copy

h,w,K=L()
c=[]
c_row=[]
c_col=[]
b=0
for i in range(h):
    ci=list(input())
    c_row.append(ci.count('#'))
    b+=c_row[-1]
    c.append(ci)
for i in range(w):
    c_col.append(0)
    for j in range(h):
        c_col[-1]+=1 if c[j][i]=='#' else 0

ans=0
s=set()
for i in range(2 ** h):
    sum=0
    dup=[[0 for a in range(w)]for b in range(h)]
    dupnum=0
    for k in range(h):
        if (i>>k)&1:
            sum+=c_row[k]
            for a in range(w):
                dup[k][a]+=1
    tmpdup=copy.deepcopy(dup)
    tmpsum=sum
    for j in range(2 ** w):
        for l in range(w):
            if (j>>l)&1:
                sum+=c_col[l]
                for a in range(h):
                    dup[a][l]+=1
        
        tmp=""
        for i in range(h):
            for j in range(w):
                tmp+=str(dup[i][j])
                if dup[i][j]==2 and c[i][j]=='#':
                    dupnum+=1
        if(tmp in s):
            sum=tmpsum
            dup=copy.deepcopy(tmpdup)
            dupnum=0
            continue
        else:
            s.add(tmp)
        if b-(sum-dupnum)==K:
            ans+=1
        sum=tmpsum
        dup=copy.deepcopy(tmpdup)
        dupnum=0
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
h, w, k = map(int, input().split())
c = [input() for _ in range(h)]


def count_black():
    res = 0
    for i in range(h):
        if red_h[i] != 1:
            for j in range(w):
                if red_w[j] != 1:
                    if c[i][j] == "#":
                        res += 1
    if res == k:
        return 1
    else:
        return 0


ans = 0
for i in range(2**h):
    red_h = [0]*h
    for j in range(h):
        if i >> j & 1 == 1:
            red_h[j] = 1

    for x in range(2**w):
        red_w = [0]*w
        for y in range(w):
            if x >> y & 1 == 1:
                red_w[y] = 1
        ans += count_black()

print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**h):
    for j in range(2**w):
        ch=[0]*h
        cw=[0]*w
        blk=0
        for l in range(h):
            if (i>>l)&1:
                ch[l]=1
        for m in range(w):
            if (j>>m)&1:
                cw[m]=1
        for a in range(h):
            for b in range(w):
                if ch[a]==1 and cw[b]==1:
                    if c[a][b]=='#':
                        blk+=1
        if blk==k:
            ans+=1
print(ans)

Submission status: Accepted

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

C = [input() for i in range(H)]
C_b = [[0]*W for h in range(H)]

for i, c in enumerate(C):
    for j, c_b in enumerate(c):
        C_b[i][j] = 0 if c_b =="." else 1

ans =0
for h in range(2**H):
    for w in range(2**W):
        h_s = bin(h)[:1:-1] + "000000"
        w_s = bin(w)[:1:-1] + "000000"
        cnt = 0
        for i, c in enumerate(C_b):
            for j, n in enumerate(c):
                if h_s[i] == "0":
                    if w_s[j] =="0":
                        if C_b[i][j] == 1:
                            cnt += 1
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import copy
import itertools

H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
S = np.array(S)
S = np.where(S == '#', 1, 0)

comb_H = []
for k in range(H + 1):
    comb_H += list(itertools.combinations(range(1, H + 1), k))
comb_W = []
for k in range(W + 1):
    comb_W += list(itertools.combinations(range(1, W + 1), k))

ans = 0
comb = list(itertools.product(comb_H, comb_W))
for h, w in comb:
    S_tmp = copy.deepcopy(S)
    if len(h) > 0:
        for i in h:
            S_tmp[i - 1, :] = 0
    if len(w) > 0:
        for j in w:
            S_tmp[:, j - 1] = 0

    if np.count_nonzero(S_tmp == 1) == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
h, w, k = map(int, input().split())
p = [list(str(input())) for _ in range(h)]
bl = p.count('#')
bl = bl - k
ee = list(range(h))
q = list(range(w))
kotae = 0
pp = []
qq = []
for i in range(h + 1):
    pp += list(itertools.combinations(ee, i))
for i in range(w + 1):
    qq += list(itertools.combinations(q, i))
for i in pp:
    for j in qq:
        ans = 0
        for zz in range(h):
            for ww in range(w):
                if zz not in i:
                    if ww not in j:
                        if p[zz][ww] == '#':
                            ans += 1
        if ans == k:
            kotae += 1
print(kotae)

Submission status: Accepted

Solution code:
import copy

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

def count_b(ar):
	count=0
	for i in ar:
		for j in i:
			if j== '#':
				count+=1
	return count

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


tot_b= count_b(ar)

ans=0
for i in range(2**(h+w)):
	test_ar= copy.deepcopy(ar)
	case= str(bin(i)[2:])
	while len(case)<h+w:
		case= '0'+case
	for j in range(len(case)):
		if case[j]=='1':
			if j<h:
				for i in range(len(test_ar[j])):
					test_ar[j][i]=None
			else:
				col_num= j-h
				for row_num in range(h):
					test_ar[row_num][col_num]=None
	if count_b(test_ar)==k:
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy
import itertools
def main():
    H, W,K = map(int, input().split())
    c = []
    for i in range(H):
        c.append(list(input()))
    alllist = [x for x in range(H+W)]
    ans = 0
    for i in range(H+W):
        numlist = list(itertools.combinations(alllist, i))
        for num in numlist:
            R = []
            C = []
            for n in num:
                if n < H:
                    R.append(n)
                else:
                    C.append(n-H)
            cnt = 0
            for h in range(H):
                for w in range(W):
                    if not h in R and not w in C:
                        if c[h][w] == '#':
                            cnt += 1
            if cnt == 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(W)] for j in range(H)]
yokoB=[0 for i in range(H)]
tateB=[0 for i in range(W)]
tateBcopy=[0 for i in range(W)]
countAll = 0
for i in range(H):
    cin = list(input())
    for j in range(W):
        c[i][j]=cin[j]
        if c[i][j]=="#":
            yokoB[i]+=1
            tateB[j]+=1
            countAll+=1
countAll-=K
count=0
countBin=0
countBin2=0
for ii in range(pow(2,W)):
    check=format(countBin,'0'+str(W)+'b')
    countBin2 = 0
    for jj in range(pow(2,H)):
        check2=format(countBin2,'0'+str(H)+'b')
        countB=0
        for i in range(W):
            if check[i]=="1":
                countB+=tateB[i]
                for j in range(H):
                    if check2[j]=="1" and c[j][i]=="#":
                        countB -= 1
        for j in range(H):
            if check2[j]=="1":
                countB+=yokoB[j]
        if countB==countAll:
            count+=1
        countBin2+=1
    countBin+=1
    
print(count)

Submission status: Accepted

Solution code:
import itertools
import copy
h,w,k=[int(x) for x in input().split()]
mh=[]
for i in range(h):
  s=list(input())
  mh.append(s)
mg=copy.deepcopy(mh)

l_h=[]
l_w=[]
a=itertools.product(range(2),repeat=h)
for i in a:
  l_h.append(i)
b=itertools.product(range(2),repeat=w)
for i in b:
  l_w.append(i)

ans=0
for y in range(2**h):
  for x in range(2**w):
    c=0
    mas=copy.deepcopy(mg)
    for j in range(h):
      if l_h[y][j]==1:
        for r in range(w):
          mas[j][r]="."
    for i in range(w):
      if l_w[x][i]==1:
        for l in range(h):
          mas[l][i]="."
    for m in mas:
      c+=m.count("#")
    if c==k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools

a=[]
b=[]
h, w, k = map(int, input().split())
h_list=[i for i in range(h)]
w_list=[i for i in range(w)]

for i in range(h+1) :
  c = list(itertools.combinations(h_list, i))
  a.extend(c)
for i in range(w+1) :
  c = list(itertools.combinations(w_list, i))
  b.extend(c)
list1 = []
for i in range(h):
  list1.append(input())

sum1 = 0
for i in range(h):
  for j in range(w):
    if list1[i][j] == '#':
      sum1 += 1
answer = 0
import copy
def count(list3,list4) :
  count1=0
  for i in list3 :
   for j in range(w) :
     if list1[i][j]=='#' :
       count1+=1
  for j in list4 :
   for i in range(h) :
     if list1[i][j]=='#' :
       count1+=1
  for i in list3 :
    for j in list4 :
      if list1[i][j] == '#':
        count1-=1
  return count1



answer = 0
for item1 in a :
  for item2 in b :
    if sum1-count(item1,item2)==k :
      answer += 1




print(answer)

Submission status: Accepted

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

for h in range(H):
    C += input()


Cw = 2 ** W
Ch = 2 ** H
ans = 0

C_tmp= C.copy()

for Y in range(Ch):
    C_tmp =[]
    for j in range(H):
        if Y >> j & 1:
            C_tmp += C[j*W:(j+1)*W]

    for X in range(Cw):
        C_tmp2 =[]
        for i in range(W):
            if X >> i & 1:
                C_tmp2 += C_tmp[i::W]

        if C_tmp2.count('#') == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations

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

temp = list(range(h))
dh = ["No"]
for i in range(1, h+1):
    dh += combinations(temp, i) 

temp = list(range(w))
dw = ["No"]
for i in range(1, w+1):
    dw += combinations(temp, i) 

cnt = (c == "#").sum()
ans = 0
for dhh in dh:
    for dww in dw:
        error = 0
        if dhh != "No":
          for i in dhh:
            error += (c[i, :] == "#").sum()
        if dww != "No":
          for j in dww:
            error += (c[:, j] == "#").sum()
        if dhh != "No" and dww != "No":
          for i in dhh:
            for j in dww:
              if c[i, j] == "#":
                    error -= 1
        
        if cnt - error == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
H,W,K = map(int,input().split())
c = [[0] * W for i in range(H)]
for i in range(H):
  s = input()
  for j in range(W):
    if(s[j] == "#"):
      c[i][j] = 1
#goukei = sum([sum(c[i]) for i in range(H)])
#sa = goukei-K
count = 0
for i in range(2**H):
  temp = copy.deepcopy(c)
  for j in range(H):
    if ((i >> j) & 1):
      for k in range(W):
        temp[j][k]=0
  for ii in range(2**W):
    temp2 = copy.deepcopy(temp)
    for jj in range(W):
      if ((ii >> jj) & 1):
        for k in range(H):
          temp2[k][jj]=0
    if(sum([sum(temp2[k]) for k in range(H)]) == K):
      count += 1    
print(count)

Submission status: Accepted

Solution code:
def power_set(item_lists):

    p_sets = [[]]

    for item in item_lists:
        tmp = []
        for element in p_sets:
            tmp.append(element + [item])
        p_sets.extend(tmp)

    return p_sets

h,w,k= map(int,input().split())
a = []
for _ in range(h):
    a.append(input()) 
h1=[i for i in range(h)]
w1=[i for i in range(w)]
ans=0
for i in power_set(h1):
  for j in power_set(w1):
    cnt=0
    for x in i:
      for y in j:
        if a[x][y]=="#":
           cnt+=1
    if cnt==k:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split(' '))
default_line = [input() for i in range(H)]
H_list,W_list = ['0','1'],['0','1']
for i in range(H-1):
	H_list = [i+j for i in ['0','1'] for j in H_list]
for i in range(W-1):
	W_list = [i+j for i in ['0','1'] for j in W_list]
  
def draw_red_H(s,line__):
  for l in range(len(s)):
    if s[l] == '1' : line__[l] = ','*W
  return line__

def draw_red_W(s,line_):
  for k in range(len(s)):
    if s[k] == '1':
      for j in range(H):
        line_[j] = line_[j][:k]+','+line_[j][k+1:] 
  return line_
count = 0
for i in W_list:
  line = default_line.copy()
  line = (draw_red_W(i,line))
  for ii in H_list:
    lines = line.copy()
    lines = (draw_red_H(ii,lines))
    if sum([iii.count('#') for iii in lines])==K:count += 1
print(count)

Submission status: Accepted

Solution code:
from itertools import combinations

h, w, K = list(map(int, input().split()))
H = [i for i in range(h)]
W = [i for i in range(w)]
grid = [list(input()) for _ in range(h)]
ans = 0
for i in range(h+1):
    for hv in combinations(H, i):
        for j in range(w+1):
            for wv in combinations(W, j):
                cnt = 0
                for k in hv:
                    for l in wv:
                        if grid[k][l] == "#":
                            cnt += 1
                if cnt == K:
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
C = np.array([[i for i in input()] for j in range(H)])
h = [i for i in range(H)]
w = [i for i in range(W)]
ans = 0
for i in range(1, H+1):
    h_list = list(itertools.combinations(h, i))
    for j in range(1, W+1):
        w_list = list(itertools.combinations(w, j))
        for k in h_list:
            for l in w_list:
                k = list(k)
                l = list(l)
                if len(k) == H:
                    c = C[:, l]
                    if np.sum(c == "#") == K:
                        ans += 1
                elif len(l) == W:
                    c = C[k, :]
                    if np.sum(c == "#") == K:
                        ans += 1
                else:
                    c = C[np.ix_(k, l)]
                    if np.sum(c == "#") == K:
                        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

ans = 0
for hh in range(1 << h):
    cp = deepcopy(c)
    for hi in range(6):
        if hh >> hi & 1:
            for wi in range(w):
                cp[hi][wi] = "x"

    for ww in range(1 << w):
        cp2 = deepcopy(cp)
        for wi in range(6):
            if ww >> wi & 1:
                for hi in range(h):
                    cp2[hi][wi] = "x"

        cnt = 0
        for hi in range(h):
            for wi in range(w):
                if cp2[hi][wi] == "#":
                    cnt += 1

        if cnt == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# 多分全探索だと思われるけども
# 2111 ~
# 2115 解法にはbit全探索を用いる.各列，行について塗るか塗らないかでbit探索をしてあげるとたかだか2**(6*2) で10**4程度の計算量に収まる
# 実装

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

H_num = 2**H
W_num = 2**W
ans = 0
import copy
for i in range(H_num):
    for j in range(W_num):
        M = copy.deepcopy(Mo)
        # sumの計算をしないといけない
        dumi = i
        dumj = j
        SH = [(dumi & 2**kh)//(2**kh) for kh in range(H)]
        SW = [(dumj & 2**kw)//(2**kw) for kw in range(W)]
        num = 0
        for ih,h in enumerate(SH):
            if h == 1:
                M[ih] = ['.' for _ in range(W)]
        for iw,w in enumerate(SW):
            if w == 1:
                for k in range(H):
                    M[k][iw] = '.'
        count = 0
        for ii in range(H):
            for jj in range(W):
                if M[ii][jj] == '#':
                    count += 1
        if count == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

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

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

for v in itertools.product([1,0],repeat=(h+w)):
  grid_dum = np.array(grid.copy())
  for i,x in enumerate(v[:h]):
    if x == 1:
      grid_dum[i,:] = 0 
  for i,x in enumerate(v[h:]):
    if x == 1:
      grid_dum[:,i] = 0 
  if grid_dum.sum() == k:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy
H,W,K= map(int,input().split())
c =[]
shape_count=0
count=0
ans_count=0
for i in range(H):
    c.append(list(input()))
    shape_count+=c[i].count("#")
ans_c = copy.deepcopy(c)
for i in range(2 ** H):
    for k in range(2 ** W):
        for j in range(H):
            if((i >> j) & 1):
                for test in range(W):
                    if(c[j][test]=="#"):
                        count+=1
                        c[j][test] = "."
        for l in range(W):
            if((k >> l) & 1):
                for test1 in range(H):
                    if(c[test1][l]=="#"):
                        count+=1
                        c[test1][l] = "."

        if(shape_count-count==K):
            ans_count+=1
        c = copy.deepcopy(ans_c)
        count=0        
print(ans_count)

Submission status: Accepted

Solution code:
con = 0;
h,w,k = map(int,input().split());
gy = [0]*h
re = [0]*w
alist = [str(input()) for aaa in range(h)]
atuple = tuple(alist)
n = 0;
for a in range(h):
    n += alist[a].count('#');

for p in range(2**h):
    plist = list(atuple)
    delete = 0;
    for pp in range(h):
        if ((p >> pp) & 1):
            delete += plist[pp].count('#');
            plist[pp] = '.'*w

    for q in range(2**w):
        deletex = delete
        for qq in range(w):
            if ((q >> qq) & 1):
                for i in range(h):
                    v = plist[i]
                    if v[qq]== '#':
                        deletex += 1;
        
        if deletex + k == n:
            con += 1;

print(con);

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
l=[]
n=0
ANS=0
answer=0
for i in range(H):
    l.append(input())
    ANS+=l[i].count("#")
#print(ANS)
for i in range(2**H):
    anss=0
    X=format(i,"b")
    n=X.zfill(H)
    for p in range(H):
        if n[p:p+1]=="0":
            anss+=l[p].count("#")
    for k in range(2**W):
        ans=anss
        Y=format(k,"b")
        m=Y.zfill(W)
        for a in range(W):
            if m[a:a+1]=="0":
                for b in range(H):
                    if n[b:b+1]=="1" and l[b][a:a+1]=="#":
                        ans+=1   
        if ANS-ans==K:
            answer+=1
print(answer)

Submission status: Accepted

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


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


h, w, k = LI()
c = [list(S()) for _ in range(h)]
c = np.array(c)
# print(c)
hl = list(range(h))
wl = list(range(w))
ans = 0
for i in range(h + 1):  # i 個の行を選ぶ
    for j in range(w + 1):  # j 個の列を選ぶ
        # print(list(combinations(hl, i)))
        for choice_line in combinations(hl, i):
            for choice_col in combinations(wl, j):
                tmp_c = np.copy(c)
                # print('i', choice_line)
                # print('j', choice_col)
                for line in choice_line:
                    tmp_c[line] = 'r'
                for col in choice_col:
                    tmp_c[:, col] = 'r'
                # print(tmp_c)
                if np.sum(tmp_c == '#') == k:
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
def check(S):
    n=0
    for ch in S:
        if ch=='#':
            n+=1
    return n
h,w,k=map(int, input().split())
tmp=[list(input()) for _ in range(h)]
c=deepcopy(tmp)

y=0
for l in c:
    x=check(''.join(l))
    y+=x

n=0
for i in range(h+w):
    n+=2**i
n+=1
m=0
for i in range(n):
    i=format(i, str(h+w).zfill(2)+'b')
    H=i[:h]
    W=i[h:]
    ans=0
    x=0
    for j in H:
        if j=='1':
            ans+=check(''.join(c[x]))
            #print(''.join(c[x]))
            c[x]=['.']*w
        x+=1
    x=0
    for j in W:
        if j=='1':
            s=str()
            for z in range(h):
                s+=c[z][x]
            ans+=check(s)
            for z in range(h):
                c[z][x]='.'
        x+=1
    #print(H,W,y-ans,k)
    if k==y-ans:
        m+=1
    c=deepcopy(tmp)

print(m)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

H,W,K=map(int,input().split())
L=np.array([list(x for x in input()) for _ in range(H)])
H=np.arange(H)
W=np.arange(W)

white='.'
black='#'
ans=0

for i in range(len(H)):
  for j in itertools.combinations(H, i):
    temp=L.copy()
    for x in j:
      temp[x,:]=0
    for k in range(len(W)):
      for l in itertools.combinations(W, k):
        temp2=temp.copy()
        if len(l)==0:
          if np.count_nonzero(temp2=='#')==K:
            ans+=1
          continue
        for y in l:
          temp2[:,y]=0
        if np.count_nonzero(temp2=='#')==K:
          ans+=1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

count = 0
for h in range(2**H):
  h_bin = np.array(list(map(int, list(format(h,f"0{H}b")))))
  d = c[h_bin==1,:]
  for w in range(2**W):
    w_bin = np.array(list(map(int, list(format(w,f"0{W}b")))))
    e = d[:,w_bin==1]
    if e.sum() == K:
      count += 1
print(count)

Submission status: Accepted

Solution code:
import collections
import itertools
import numpy as np
H,W,K = map(int, input().split())
C = [list(input()) for i in range(H)]
MAP = np.array(C)
EraseLine = np.count_nonzero(MAP == '#', axis=1)
EraseRow = np.count_nonzero(MAP == '#', axis=0)
sumSharp = sum(EraseLine)


cnt = 0
for i in itertools.product([0,1], repeat=(H+W)):
    EraseCnt = 0
    # 行の処理
    for j in range(H):
        if i[j] == 1:
            EraseCnt += EraseLine[j]

    # 列の処理
    for m in range(W):
        if i[H+m] == 1:
            EraseCnt += EraseRow[m]
            for n in range(H):
                if i[n] == 1:
                    EraseCnt -= C[n][m] == '#'

    if K == sumSharp - EraseCnt:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from itertools import combinations
def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]
ans = 0

def check(c, x, y, k, w, h):
    li = [[k for k in i[:]] for i in c[:]]
    for yy in y:
        li[yy] = ['x' for _ in range(w)]
    for xx in x:
        for yyy in range(h):
            li[yyy][xx] = 'x'
    ct = 0
    for i in li: ct += i.count('#')
    return ct == k

h, w, k = m_in(int)
c = [input() for _ in range(h)]
count = 0
for i in c: count += i.count('#')
xc = []
yc = []
for i in range(w):
    for res in combinations(range(w), i):
        xc.append(res)
for i in range(h):
    for res in combinations(range(h), i):
        yc.append(res)
for x in xc:
    for y in yc:
        if check(c, x, y, k, w, h):
            ans += 1

print(ans)

Submission status: Accepted

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

#c =[list(map(str,input().split())) for l in range(h)]

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

ans=0

for i in range(2**h):
    x=format(i, "06b")
    for j in range(2**w):
        y=format(j, "06b")
    
        cnt=0
        for i_i in range(h):
            if x[-1*(i_i+1)]=="1":
                continue
            for j_j in range(w):
                if y[-1*(j_j+1)]=="1":
                    continue
                else:
                    if c[i_i][j_j]=="#":
                        cnt+=1
        if cnt==k:
            ans+=1

print(ans)