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
import copy

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

h_comb = []
w_comb = []
for i, _ in enumerate(_h, 1):
    for j in combinations(_h, r=i):
        h_comb.append(list(j))
h_comb.append([])

for i, _ in enumerate(_w, 1):
    for j in combinations(_w, r=i):
        w_comb.append(list(j))
w_comb.append([])

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

ans = 0
for hc in h_comb:
    for wc in w_comb:
        tmp = copy.deepcopy(field)

        for i in hc:
            for j in range(w):
                tmp[i][j] = '.'
        for j in wc:
            for i in range(h):
                tmp[i][j] = '.'
        count = 0
        for i in range(h):
            for j in range(w):
                if tmp[i][j] == '#':
                    count += 1
        if count == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    h,w,K = map(int, input().split())
    mas = [list(input()) for i in range(h)]
    wk = []
    hk = []
    for i in range(h):
        plus = 0
        for j in range(w):
            if mas[i][j] == "#":
                plus += 1
        hk.append(plus)
    for i in range(w):
        plus = 0
        for j in range(h):
            if mas[j][i] == "#":
                plus += 1
        wk.append(plus)
    total = sum(wk)

    ans = 0
    for i in range(2**h):
        vert = []
        for k in range(h):
            vert.append((i>>k)&1)
        for j in range(2**w):
            hor = []
            for m in range(w):
                hor.append((j>>m)&1)
            subt = 0

            for n in range(len(vert)):
                subt += vert[n] * hk[n]
            for n in range(len(hor)):
                subt += hor[n] * wk[n]
            for n in range(len(vert)):
                for o in range(len(hor)):
                    if (vert[n] == 1) and (hor[o] == 1) and (mas[n][o] == "#"):
                        subt -= 1

            if total-subt == K:
                ans += 1


    print(ans)
resolve()

Submission status: Accepted

Solution code:
import copy
hwk = input('')
h = int(hwk.split(' ')[0])
w = int(hwk.split(' ')[1])
k = int(hwk.split(' ')[2])

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

cnt_all=0
for i in range(2**(h+w)):
    bag=[]
    clist2 = []
    for line in clist:
        clist2.append(line)
    for j in range(h+w):
        if ((i>>j)&1):
            if j < h:                
                # 行を選ぶ方
                bag.append("Y:{}".format(j))
                clist2[j] = 'R'*w
            else:
                # 列を選ぶ方
                bag.append("X:{}".format(j-h))
                for i2 in range(h):
                    line = list(clist2[i2])
                    line[j-h] ='R'
                    clist2[i2] = "".join(line)
    cnt = 0
    for c in clist2:
        cnt+=c.count('#')
    if cnt==k:
#        print(clist2)
        cnt_all+=1

print(cnt_all)

Submission status: Accepted

Solution code:
from collections import deque

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

def check(r):
    counter = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == '.':
                continue
            else:
                # black
                if r[h] or r[H + w]:
                    continue
                else:
                    counter += 1  
    return 1 if counter == K else 0

depth = 0
queue = deque()
queue.append(([], 0))
answer = 0
while len(queue) != 0:
    r, depth = queue.pop()
    if depth == H + W:
        answer += check(r)
    else:
        for mask in [True, False]:
            queue.append((r + [mask], depth + 1))
print(answer)

Submission status: Accepted

Solution code:
import copy
def main():
    H,W,K = map(int, input().split())
    road = [[0]*W for _ in range(H)]
    for i in range(H):
        c = input()
        for j in range(W):
            if c[j]=='.':
                road[i][j] = 0
            else:
                road[i][j] = 1
    ans = 0
    for h in range(2**H):
        for w in range(2**W):
            harr = [0]*H
            warr = [0]*W
            for i in range(H):
                harr[H-i-1] = (h>>i)&1
            for i in range(W):
                warr[W-i-1] = (w>>i)&1
            tmp = 0
            for i in range(H):
                for j in range(W):
                    if harr[i]==0 and warr[j]==0 and road[i][j]==1:
                        tmp += 1
            if tmp==K: ans += 1
    print(ans)

main()

Submission status: Accepted

Solution code:
from itertools import combinations as co
h,w,k=map(int,input().split())
m=[list(input()) for i in range(h)]
pr=[]
pc=[]
for i in range(h+1):
  pr+=list(co(range(h),i))
for i in range(w+1):
  pc+=list(co(range(w),i))
a=0
for i in pr:
  for j in pc:
    n=[m[x][:] for x in range(h)]
    for x in i:
      for y in range(w):
        n[x][y]="."
    for x in j:
      for y in range(h):
        n[y][x]="."
    if sum(x.count("#") for x in n)==k:
      a+=1
print(a)

Submission status: Accepted

Solution code:
from itertools import product
from copy import deepcopy
H, W, K = map(int, input().split())
c = []
for _ in range(H):
    c.append(list(input()))
ans = 0
for h in range(2**H):
    for w in range(2**W):
        tmp = deepcopy(c)
        for i in range(H):
            for j in range(W):
                if 1&(w>>j) or 1&(h>>i):
                    tmp[i][j] = "?"
        cnt = 0
        for i in range(H):
            cnt += tmp[i].count("#")
        if cnt==K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
import copy
H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

h_cnt=[]
for s in S:
    cnt=0
    for x in s:
        if x=="#":
            cnt+=1
    h_cnt.append(cnt)

T=sum(h_cnt)

w_cnt=[]
w=0
for w in range(W):
    cnt=0
    for h in range(H):
        if S[h][w]=="#":
            cnt+=1
    w_cnt.append(cnt)

HL=list( itertools.product(range(2), repeat=H) )
WL=list( itertools.product(range(2), repeat=W) )

ans=0
for hl in HL:
    for wl in WL:
        total=copy.deepcopy(T)
        for i,h in enumerate(hl):
            if h==1:
                total-=h_cnt[i]
        for j,w in enumerate(wl):
            if w==1:
                total-=w_cnt[j]

        for i,h in enumerate(hl):
            for j,w in enumerate(wl):
                if h&w==1:
                    if S[i][j]=="#":
                        total+=1

        if total==K:
            ans+=1
print ans

Submission status: Accepted

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

a = [[0 for j in range(6)] for i in range(6)]

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            a[i][j] = 0
        else:
            a[i][j] = 1

result = 0
for row in a:
    result += sum(row)

HH = range(H)
WW = range(W)

resH = [()]
resW = [()]
for n in range(1,len(HH)+1):
    for conb in itertools.combinations(HH, n):
        resH.append(list(conb)) 
for n in range(1,len(WW)+1):
    for conb in itertools.combinations(WW, n):
        resW.append(list(conb)) 

ko = 0
for i in resH:
    for j in resW:
        b = copy.deepcopy(a)
        p = itertools.product(i, j)
        for ii in i:
            for jj in range(W):
                b[ii][jj] = 0
        for jj in j:
            for ii in range(H):
                b[ii][jj] = 0

        result = 0
        for row in b:
            result += sum(row)
        if result == K:
            ko += 1

print(ko)

Submission status: Accepted

Solution code:
hwk,*ccc = open(0).read().splitlines()

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

ccc = list(map(list, ccc))

from itertools import product

from copy import deepcopy

ans = 0

count = 0

for hs in product([0,1], repeat=H):
    for ws in product([0,1], repeat=W):
        tmp = deepcopy(ccc)
        for h,b in enumerate(hs):
            if b:
                tmp[h] = list('r'* W)
        for h in range(H):
            for w,c in enumerate(ws):
                if c:
#                     print(hs, h, ws, w)
#                     print(tmp)
                    tmp[h][w] = 'r'
#                     print(tmp)
#         print(hs, ws)
#         count += 1
        ans += (''.join(sum(tmp, [])).count('#') == K)
#         print(''.join(sum(tmp, [])))
#         print(''.join(sum(tmp, [])).count('#'))

print(ans)

Submission status: Accepted

Solution code:
import itertools

inp = input()
split = inp.split()
h = int(split[0])
w = int(split[1])
k = int(split[2])
lines=[]
result = 0
for i in range(h):
    lines.append(input())
hList = list(range(h+1))[1:]
wList = list(range(w+1))[1:]
hResult = [[]]
wResult = [[]]
for n in range(1,len(hList)+1):
    for conb in itertools.combinations(hList, n):
        hResult.append(list(conb)) #タプルをリスト型に変換
for n in range(1,len(wList)+1):
    for conb in itertools.combinations(wList, n):
        wResult.append(list(conb)) #タプルをリスト型に変換
def check(hBanish, wBanish):
    result = 0
    for hNum in range(1, h + 1):
        if hNum in hBanish:
            continue
        else:
            for wNum in range(1, w + 1):
                if wNum in wBanish:
                    result += 0
                elif lines[hNum-1][wNum-1] == "#":
                    result += 1
                else:
                    result += 0
    return result

for hBanish in hResult:
    for wBanish in wResult:
        if check(hBanish, wBanish) == k:
            result  += 1
print(result)

Submission status: Accepted

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

ans = 0
for i in range(2**(H+W)):
  height = [x for x in range(H)]
  width = [y for y in range(W)]
  for j in range(H):
    if i >> j & 1:
      height.remove(j)
  for k in range(H, H+W):
    if i >> k & 1:
      width.remove(k-H)
  num = 0
  for p in height:
    for q in width:
      if c[p][q] == "#":
        num += 1
  if num == K:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

h, w, k = map(int, readline().split())
g = [list(readline().decode().rstrip()) for _ in range(h)]

ans = 0
for i in itertools.product([0, 1], repeat=h):
    for j in itertools.product([0, 1], repeat=w):
        cnt = 0
        for n,a in enumerate(i):
            for m, b in enumerate(j):
                if a == 1 and b == 1 and g[n][m] == '#':
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

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

p = [input() for i in range(h)]
H =[0]*h
W = [0]*w

b = 0
for i in range(h):
  for j in range(w):
    if p[i][j] == '#':
      H[i] += 1
      W[j] += 1
      b += 1
   
d = b - k

ans = 0

for i in range(2**h):
  for k in range(2**w):
    black1 = 0
    for j in range(h):

      if ((i>>j)&1):
        black1 += H[j]
    
    for l in range(w):

      if ((k>>l)&1):
        black1 += W[l]
        
    for j in range(h):
      for l in range(w):
        if (i>>j)&1 and (k>>l)&1 and p[j][l] == '#':
          black1 -= 1

    
    if black1 == d:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import copy
h,w,k = map(int, sys.stdin.readline().rstrip("\n").split())
labyrinth = []
for _ in range(h): 
    l = list(sys.stdin.readline().rstrip("\n"))
    labyrinth.append(l)
l_h = [format(i, 'b').zfill(h) for i in range(2**h)]
l_w = [format(i, 'b').zfill(w) for i in range(2**w)]
ans = 0
for hi in l_h:
    for wi in l_w:
        labyrinth_new = copy.deepcopy(labyrinth)
        s = 0
        for hii in range(h):
            if hi[hii] == '1':
                labyrinth_new[hii] = ['r']*w
        for wii in range(w):
            if wi[wii] == '1':
                for _ in range(h):
                    labyrinth_new[_][wii] = 'r'
        for _ in range(h):
            s += labyrinth_new[_].count('#')
        if s == k:
            ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**h):
  key = [0]*h
  for a in range(h):
    if (i>>a)&1:
      key[a] = 1
  for j in range(2**w):
    key2 = [0]*w
    for b in range(w):
      if (j>>b)&1:
        key2[b] = 1
    count = 0
    for p in range(h):
      for q in range(w):
        if grid[p][q] == "#" and key[p] == 0 and key2[q] == 0:
          count += 1
    if count == k:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
import sys
c = [[str(a) for a in l.strip()] for l in sys.stdin]

ans = 0

b = 2 ** (h + w)
for i in range(b):
  for j in range(h):
    for q in range(w):
      if ((i >> j) & 1) and (i >> (q+h)) & 1:
        if c[j][q] == "#":
          sum += 1
  if sum == k:
    ans += 1
  sum = 0
    
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

h, w, k = map(int, input().split())
ans = 0
grid = [[m for m in input()] for _ in range(h)]

flg=[True, False]
for fh in itertools.product(flg, repeat=h):
    for fw in itertools.product(flg, repeat=w):
        cnt = 0
        cflg = True
        for i in range(h):
            if not fh[i]: continue
            if not cflg: break
            for j in range(w):
                if not fw[j]: continue
                if grid[i][j] == '#': cnt += 1
                if cnt > k:
                    cflg = False 
                    break
                    
        if cnt == k: ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

H,W,K = map(int, input().split())
G = []
tate = [0]*W
yoko = [0]*H
for i in range(H):
  G.append(list(input()))

for i in range(W):
  for j in range(H):
    if(G[j][i]=="#"):
      tate[i]+=1
      yoko[j]+=1

su = sum(tate)
ans = su
ans2 = 0


for i in range(2**W):
  for j in range(2**H):
    temp = copy.deepcopy(G)
    for k in range(W):
      if((i>>k) & 1):
        for l in range(H):
          if(temp[l][k]=="#"):
            temp[l][k]="."
            ans-=1
    for m in range(H):
      if((j>>m) & 1):
        for o in range(W):
          if(temp[m][o]=="#"):
            temp[m][o]="."
            ans-=1
    if(ans==K):
      ans2 += 1
    ans = su
    #print(temp)



print(ans2)

Submission status: Accepted

Solution code:
import copy

h,w,k=[int(aaa) for aaa in input().split()]

c=[]
ans=0

for _ in range(h):
    c.append(list(input()))

for i in range(2**h):
    for j in range(2**w):
        d=copy.deepcopy(c)
        i2='000000'+format(i,'b')
        j2='000000'+format(j,'b')
        #対応する場所の色を変える
        #おケツから数える
        for k2 in range(1,h+1):
            if i2[-k2]=='1':
                for i3 in range(w):
                    d[k2-1][i3]='@'
        for l in range(1,w+1):
            if j2[-l]=='1':
                for j3 in range(h):
                    d[j3][l-1]='@'

        #数を数える
        cnt=0
        for d2 in d:
            cnt+=d2.count('#')
        #一致してたらプラ1
        if cnt==k:
            ans+=1
print(ans)

Submission status: Accepted

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

X = [input() for _ in range(h)]

Y = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if X[i][j] == '#':
            Y[i][j] = 1
# print(Y)

ans=0
for j in range(2**h):
    H=[]
    for _h in range(h):
        if (j>>_h)&1:
            H.append(Y[_h])
    # print(H)
    for l in range(2**w):
        _ans = 0
        for _w in range(w):
            if (l>>_w)&1:
                _ans += sum([_H[_w] for _H in H])
        if _ans == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
h,w,f=map(int, input().split())
box=[]
cnt=0
for i in range(h):
  box.append(list(str(input())))
htarget=list(itertools.product([0,1], repeat=h))
wtarget=list(itertools.product([0,1], repeat=w))
for j in range(len(htarget)):
  boxtemp=[["0"] * w for i in range(h)]
  for k in range(len(wtarget)):
    cnttemp=0
    for p in range(h):
      for q in range(w):
        if htarget[j][p]==1 or wtarget[k][q]==1:
          boxtemp[p][q]="?"
        else:
          boxtemp[p][q]=box[p][q]
    for s in range(h):
      for t in range(w):
        if boxtemp[s][t]=="#":
          cnttemp+=1
    if cnttemp==f:
      cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
def adj(n): return [[] for _ in range(n)]

h,w,k = imap()
grid = np.array([[int(elm=="#") for elm in sinput()] for i in range(h)])

ans = 0
for i in range(2**h):
    for ii in range(2**w):
        g = cp.deepcopy(grid)
        for j in range(h):
            if i>>j &1: g[j,:] = 0
        for jj in range(w):
            if ii>>jj &1: g[:,jj] = 0
        cnt = np.count_nonzero(g)
        if cnt == k: ans += 1
print(ans)

Submission status: Accepted

Solution code:

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


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


for i in range (2**h):
   a = [0] * w
   for p in range(h):
      for q in range(w):
         if c[p][0][q] == "#":
            if i//(2**p)%2==0:
               a[q]+=1
   for m in range(2**w):
      kk=0
      for j in range(w):
         if m//(2**j)%2==0:
            kk+=a[j]
      if k==kk:
         t+=1

print(t)

Submission status: Accepted

Solution code:
import copy

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

matrix = [[0 for i in range(w)] for j in range(h)]

def delRow(a, mat):
    for i in range(w):
        mat[a][i] = 0

def delCol(b, mat):
    for j in range(h):
        mat[j][b] = 0

def sum2d(mat):
    s = 0
    for i in range(len(mat)):
        for j in range(len(mat[i])):
            s += mat[i][j]
    return s

for i in range(h):
    c = input()
    for j in range(w):
        if c[j] == '#':
            matrix[i][j] += 1


for i in range(2 ** h):
    for j in range(2 ** w):
        mat = copy.deepcopy(matrix)
        for l in range(h):
            if ((i >> l) & 1):
                delRow(l, mat)
        for l in range(w):
            if ((j >> l) & 1):
                delCol(l, mat)
        if sum2d(mat) == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product
H, W, K = map(int, input().split())

C = [None] * H
for i in range(H):
    C[i] = input()

np_c = np.zeros((H, W), dtype=int)
for i in range(H):
    for j in range(W):
        if C[i][j] == "#":
            np_c[i][j] = 1


ans = 0
for h_bin in product([True, False], repeat = H):
    for w_bin in product([True, False], repeat = W):
        copy_array = np_c.copy()
        for i, h in enumerate(h_bin):
            for j, w in enumerate(w_bin):
                if h:
                    copy_array[i, :] = 0
                if w:
                    copy_array[:, j] = 0
        if copy_array.sum() == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import itertools
from copy import deepcopy

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

Arr = np.zeros((H, W))
for i in range(H):
    words = input()
    for j, w in enumerate(words):
        if w == "#":
            Arr[i,j] = 1
#print(Arr)
ans = 0
for t in range(0,H+W):
    Ex = list(itertools.combinations([int(i) for i in range(H+W)],t))
    for j in Ex:
        TMP = deepcopy(Arr)
        for num in j:
            if num < H:
                TMP[num] = np.zeros(W)
            else:
                w = num - H
                #print(TMP)
                TMP[:,w] = np.zeros(H)
                #print(w,TMP[:,w])
        if K == int(np.sum(TMP)):
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import os
import itertools
import numpy as np
from collections import deque
import copy

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    # print(C)
    ans=0
    W_list = []
    for j in range(W+1): #横
        W_list.extend(list(itertools.combinations([i for i in range(W)],j)))

    H_list = []
    for j in range(H+1): #縦
        H_list.extend(list(itertools.combinations([i for i in range(H)],j)))

    for W_set in W_list:
        for H_set in H_list:
            # 消す作業
            tmp=copy.copy(C)
            # print(type(tmp[0][0]))
            # print(W_set)
            # print(tmp)
            for w in W_set:
                # print(w)
                for i in range(H):
                    # if w
                    tmp[i]=tmp[i][:w]+'.'+tmp[i][w+1:]

            for h in H_set:
                for i in range(W):
                    tmp[h]=tmp[h][:i]+'.'+tmp[h][i+1:]

            count = 0
            for w in range(W):
                for h in range(H):
                    if tmp[h][w]=='#':
                        count+=1

            if count == K:
                ans+=1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    ans = 0
    for a in range(2**h):
        for b in range(2**w):
            black_sum = 0
            row = list(format(a,'0'+str(h)+'b'))
            column = list(format(b,'0'+str(w)+'b'))
            for i in range(h):
                if row[i] == '1':
                    continue
                for j in range(w):
                    if column[j] == '1':
                        continue
                    elif c[i][j] == "#":
                        black_sum += 1
            if black_sum == k:
                ans += 1
        
    print(ans)

resolve()

Submission status: Accepted

Solution code:
import numpy as np
import math
H,W,K = map(int,input().split())
m = []
for i in range(H):
    m.append(list(input()))
m = np.array(m)
bcell = m=="#"

ans = 0
for i in range(2**H):
    r_pattern = np.array(list(format(i, f'0{H}b')))=='1'
    for j in range(2**W):
        c_pattern = np.array(list(format(j, f'0{W}b')))=='1'
        mask = r_pattern.reshape(H,1) & c_pattern.reshape(1,W)
        
        b_cell_num = np.sum(bcell&mask)
        if b_cell_num ==K:
            ans +=1
print(ans)

Submission status: Accepted

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

buf = []
total = 0
for row in range(h):
    row = list(input())

    buf.append(row)

    total += row.count('#')

colors = list(zip(*buf))

if k > total:
    print(0)
    exit()

# diff個減らせればOK
diff = total - k

candH = 2 ** h
candW = 2 ** w


def counting(text):
    res = []
    for i, c in enumerate(text):
        if c == '#':
            res.append(i)
    return res

ans = 0
for a in range(candH):
    for b in range(candW):
        hBit = a
        wBit = b
        currentCount = 0

        hIndexList = []
        for r in range(h):
            shouldAgg = hBit % 2 == 1
            hBit = hBit >> 1

            l = []
            if shouldAgg:
                l = counting(buf[r])
            hIndexList.append(l)
            currentCount += len(l)

        for c in range(w):
            shouldAgg = wBit % 2 == 1
            wBit = wBit >> 1

            if shouldAgg:
                cIndex = counting(colors[c])
                currentCount += len(cIndex)

                for ci in cIndex:
                    if c in hIndexList[ci]:
                        currentCount -= 1

        if currentCount == diff:
            ans += 1


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):
    IDh=format(i,"b").zfill(H)
    for j in range(2**W):
        n=0
        IDw=format(j,"b").zfill(W)
        c=copy.deepcopy(C)
        for k in range(H):
            if IDh[k]=="1":
                c[k]=["!" for i in range(W)]
        for k in range(W):
            if IDw[k]=="1":
                for l in range(H):
                    c[l][k]="!"
        for k in range(H):
            for l in range(W):
                if c[k][l]=="#":
                    n+=1
        if n==K:
            Ans+=1
print(Ans)

Submission status: Accepted

Solution code:
import sys

[H,W,K]=[int(i) for i in sys.stdin.readline().split()]

arr=[]

for x in range(H):
	tmp=sys.stdin.readline().strip()
	arr.append(tmp)

rows=[0]*H
cols=[0]*W

total=0

for g in range(H):
	su=0
	for h in range(W):
		if(arr[g][h]=="#"):
			su+=1
			total+=1
	rows[g]=su

for p in range(W):
	su2=0
	for q in range(H):
		if(arr[q][p]=="#"):
			su2+=1
	cols[p]=su2

n1=pow(2,H)
n2=pow(2,W)

ans=0

for a in range(n1):
	for b in range(n2):
		rs=bin(a)[2:]
		cs=bin(b)[2:]
		
		rs="0"*(H-len(rs))+rs
		cs="0"*(W-len(cs))+cs

		num=total

		for p in range(len(rs)):
			if(rs[p]=="1"):
				num-=rows[p]

		for q in range(len(cs)):
			if(cs[q]=="1"):
				num-=cols[q]
				for g in range(len(rs)):
					if(rs[g]=="1" and arr[g][q]=="#"):
						num+=1

		if(num==K):
			ans+=1

print(ans)

Submission status: Accepted

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

ans = 0

c_h = [ 0 for _ in range( h ) ] # c[ i ] = i行目にある#の個数
c_w = [ 0 for _ in range( w ) ] # c[ j ] = j列目にある#の個数
all_black = 0

for i in range( h ):
    for j in range( w ):
        if c[ i ][ j ] == "#":
            c_h[ i ] += 1
            c_w[ j ] += 1
            all_black += 1

def count_black( list_h, list_w ):
    cnt = all_black
    for i in list_h:
        cnt -= c_h[ i ]
    for j in list_w:
        cnt -= c_w[ j ]
    for i in list_h:
        for j in list_w:
            if c[ i ][ j ] == "#":
                cnt += 1
    return cnt

def solve( i, list_h, j, list_w ):
    if i < h:
        solve( i + 1, list_h, j, list_w )
        solve( i + 1, list_h + [ i ], j, list_w )
    else:
        if j < w:
            solve( i, list_h, j + 1, list_w )
            solve( i, list_h, j + 1, list_w + [ j ] )
        else:
            if k == count_black( list_h, list_w ):
                global ans
                ans += 1

solve( 0, [], 0, [] )
print( ans )

Submission status: Accepted

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

def count(C0, H, W, hl, wl):
    T = [['' for i in range(W)] for j in range(H)]
    for i in range(H):
        for j in range(W):
            T[i][j] = C[i][j]       

    for j in hl:
        for i in range(W):
            T[j][i] = 'R'
    for i in wl:
        for j in range(H):
            T[j][i] = 'R'

    c = 0
    for i in range(H):
        for j in range(W):
            if T[i][j] == '#':
                c += 1
    return c
            

ans = 0
for j in range(W+1):
    for w in itertools.combinations(list(range(W)), j):
        for i in range(H+1):
            for v in itertools.combinations(list(range(H)), i):
                r = count(C, H, W, list(v), list(w))
                if r == K:
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:
""" C
    https://atcoder.jp/contests/abc173/tasks/abc173_c
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def _pattern(N):
    if N > 1:
        pa = _pattern(N-1)
        return [[0] + p for p in pa] + [[1] + p for p in pa]
    else:
        return [[0], [1]]

def main(H, W, K, c):
    count = 0
    pwSet = _pattern(W)
    phSet = _pattern(H)
    for ph in phSet:
        result = []
        for i in range(0, len(ph)):
            if ph[i] == 1:
                result.append(c[i])
        for pw in pwSet:
            s = 0
            for r in result:
                s += sum([1 if r[j] == "#" and pw[j] == 1 else 0 for j in range(0, len(r))])
            if s == K:
                count += 1
    return count

if __name__ == "__main__":
    _H, _W, _K = readIntegerSet(3)
    _c = [list(readString().strip()) for _ in range(0, _H)]

    print(main(_H, _W, _K, _c))