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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

def solve(h, w, k, A):
    B = h + w
    ret = 0
    for b in range(2 ** B):
        count = 0
        for j in range(h):
            for i in range(w):
                if b & (1 << j) or b & (1 << (i + h)):
                    continue
                if A[j][i] == '#':
                    count += 1

        if count == k:
            ret += 1
    print(ret)
    return

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

squares = np.array([
           [0 if w == "." else 1 for w in input()] for h in range(H)
          ])

count = 0
for w in itertools.product([0, 1], repeat=W):
  paintedW = np.delete(squares, np.where(np.array(w)==1), axis = 1)
  for h in itertools.product([0, 1], repeat=H):
    paintedH = np.delete(paintedW, np.where(np.array(h)==1), axis = 0)
    if np.sum(paintedH) == K:
      count += 1

print(count)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
import numpy as np
C = np.zeros((H,W),dtype=np.bool)
for h in range(H):
    S = input()
    for w in range(W):
        if S[w] == '#':
            C[h][w] = 1
from copy import deepcopy as dp
hlen = len(str(bin(2**H-1))[2:])
wlen = len(str(bin(2**W-1))[2:])
ans = 0
for h in range(2**H):
    for w in range(2**W):
        t_arr = dp(C)
        tmp_h = str(bin(h))[2:].zfill(hlen)
        tmp_w = str(bin(w))[2:].zfill(wlen)
        for i,hh in enumerate(tmp_h):
            if hh == '1':
                t_arr[i,:] = 0
        for i,ww in enumerate(tmp_w):
            if ww == '1':
                t_arr[:,i] = 0
        if t_arr.sum() == K:
            ans += 1
print(ans)

Submission status: Accepted

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

L = []

for _ in range(H):
    S = input()
    x = [S[i] for i in range(len(S))]
    L.append(x)

item = [i for i in range(H)]
item2 = [i for i in range(W)]
Ans = 0
for i in range(2 ** H):
    bag = []
    for j in range(H):
        if ((i >> j) & 1):
            bag.append(item[j])
    #print(bag)
    for k in range(2 ** W):
        bag2 = []
        for j in range(W):
            if ((k >> j) & 1):
                bag2.append(item2[j])
        L_copy = [[L[i][j] for j in range(W)] for i in range(H)]
        for x in bag:
            for j in range(W):
                L_copy[x][j] = "red"
        for x in bag2:
            for j in range(H):
                L_copy[j][x] = "red"
        count = 0
        for j in range(H):
            for l in range(W):
                if L_copy[j][l] == "#":
                    count +=1
        if count == K:
            Ans +=1
print(Ans)

Submission status: Accepted

Solution code:

from copy import deepcopy

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

ans = 0
for h in range(1<<H):
    for w in range(1<<W):
        # print('h={}, w={}'.format(h, w))
        C2 = deepcopy(C)
        for i in range(H):
            if h >> i & 1:
                for j in range(W):
                    C2[i][j] = "."
        for j in range(W):
            if w >> j & 1:
                for i in range(H):
                    C2[i][j] = "."

        cnt = 0
        for i in range(H):
            for j in range(W):
                if C2[i][j] == "#":
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

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

def x(i,j,c):
    r=0
    if i<h:
        r+=x(i+1,j,copy.deepcopy(c))
        _c=copy.deepcopy(c)
        _c[i]=["r" for a in range(w)]
        r+=x(i+1,j,_c)
    elif j<w:
        r+=x(i,j+1,copy.deepcopy(c))
        _c=copy.deepcopy(c)
        for a in range(h):
            _c[a][j]="r"
        r+=x(i,j+1,_c)
    else:
        count=0
        for a in range(h):
            for b in range(w):
                if c[a][b]=="#":
                    count+=1
        if count==k:
            r=1
    return r
print(x(0,0,c))

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
c = []
a = 0


ww = []
hh = []
def count(c, hh, ww):
    ans = 0
    for i in range(h):
        for j in range(w):
            if not i in hh:
                if not j in ww:
                    if c[i][j]=="#":
                        ans+=1
    return ans
            
for _ in range(h):
    c.append(input())

for i in range(2**h):
    for j in range(2**w):
        cc = c
        hh = []
        ww = []
        for x in range(h):#行
            if ((i>>x)&1):
                hh.append(x)
        for y in range(w):
            if ((j>>y)&1):
                ww.append(y)
        if count(cc, hh, ww)==k:
            a += 1
print(a)

Submission status: Accepted

Solution code:
H, W, K = [int(x) for x in input().split()]
S = [input() for _ in range(H)]
ans = 0
for i in range(2**H):
    tmp1 = S[:]
    for j in range(H):
        if (i >> j) & 1:
            # j+1桁目が1のときここに入る
            tmp1[j] = '.' * W
    for j in range(2**W):
        tmp2 = tmp1[:]
        for k in range(W):
            if (j >> k) & 1:
                tmp2 = [l[:k] + '.' + l[k+1:] for l in tmp2]
        cnt = sum([l.count('#')  for l in tmp2])
        ans += cnt == K
print(ans)

Submission status: Accepted

Solution code:
import copy
h, w, k = map(int, input().split())
mas_global = [[] for _ in range(h)]
for i in range(h):
    mas_global[i] = list(input())

# a, bはh, wからどれを選ぶかの情報2進数
def calc_black_cnt(a, b):
    mas = copy.deepcopy(mas_global)
    i = 0
    while 1<<i <= a:
        if a & 1<<i != 0:
            mas[i] = ['r' for _ in range(w)]
        i += 1
    j = 0
    while 1<<j <= b:
        if b & 1<<j != 0:
            for ii in range(h):
                mas[ii][j] = 'r'
        j += 1
    res = 0
    for i in range(h):
        res += mas[i].count('#')
    return res

ans = 0
for i in range(2**h):
    for j in range(2**w):
        cnt = calc_black_cnt(i, j)
        if cnt == k:
            ans += 1
print(ans)
# calc_black_cnt(0, 4)

Submission status: Accepted

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
import copy
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


H,W,K=nm()
mass=[[0 for i in range(W)] for i in range(H)]
for i in range(H):
    c=list(ns())
    for j in range(W):
        mass[i][j]=(0 if c[j]=='.' else 1)

ans=0
c=0
for i in range(2**W):
            for j in range(2**H):
                mass2=copy.deepcopy(mass)
                c=0
                for k in range(W):
                        if((i>>k) & 1):
                            for l in range(H):
                                mass2[l][k]=-1

                for k in range(H):
                        if((j>>k) & 1):
                            for l2 in range(W):
                                mass2[k][l2]=-1
                for k in range(W):
                    for l in range(H):
                        if(mass2[l][k]==1):
                            c+=1
                if(c==K):
                    ans+=1
print(ans)

Submission status: Accepted

Solution code:

def main():
  h, w, k = map(int, input().split())
  aaa = [list(map(int, input().replace('.', '0').replace('#', '1'))) for _ in range(h)]
  
  from itertools import combinations
  
  res = 0
  for i in range(1, 1+h):
    for j in range(1, 1+w):
      rrr = list(combinations(range(h), i))
      ccc = list(combinations(range(w), j))
      for rr in rrr:
        for cc in ccc:
          t = 0
          for r in rr:
            for c in cc:
              t += aaa[r][c]
          if t == k:
            res += 1
  print(res)


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import collections
from itertools import chain
H,W,K=map(int, input().split())

grid=[list(map(str,input())) for i in range(H)]

ans=0

for i in range(2**W):
    for j in range(2**H):
        
        temp=[[grid[s][t] for t in range(W)]for s in range(H)]
        ww=bin(2**W+i)[3:]
        hh=bin(2**H+j)[3:]
        for ws in range(W):
            for hs in range(H):
                if ww[ws]=='1' or hh[hs]=='1':
                    temp[hs][ws]='.'
        temtemp=list(chain.from_iterable(temp))
        cc=collections.Counter(temtemp)
        if cc['#']==K:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
g = []
from copy import deepcopy
for i in range(h):
    g.append(list(input()))
def count(g):
    result = 0
    for i in g:
        result += i.count('#')
    return result
ans = 0

for i in range(2 **(h+w)):
    ng = deepcopy(g)
    a = bin(i)[2:].zfill(h+w)
    for i, num in enumerate(a[:h]):
        if num == '1':
            for j in range(w):
                ng[i][j] = 'r'
    for j, num in enumerate(a[h:]):
        if num == '1':
            for i in range(h):
                ng[i][j] = 'r'
    if count(ng) == k:
        ans += 1
print(ans)

Submission status: Accepted

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

for H in range(2**h):
    for W in range(2**w):
        ans=0
        for i in range(h):
            for j in range(w):
                if not((H>>i)&1):
                    if not((W>>j&1)):
                        if a[i][j]=="#":
                            ans+=1
                    
        if ans==k:
            anss+=1

print(anss)

Submission status: Accepted

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

for i in range(1 << H):
    badH = []
    for j in range(H):
        if (i >> j) & 1 ==1:
            badH.append(j)
    for k in range(1 << W):
        badW = []
        count = 0
        for l in range(W):
            if (k >> l) & 1 ==1:
                badW.append(l)
        for m in range(H):
            for n in range(W):
                if maze[m][n] == '#':
                    if m not in badH and n not in badW:
                        count += 1
        if count == K:
            ans += 1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

ans = 0
for bit in range(2 ** (H + W)):
    row = []
    col = []
    acc = 0
    for i in range(H):
        if bit & (1<<i):
            row.append(i)
    for j in range(H, H + W):
        if bit & (1<<j):
            col.append(j - H)
    for i in row:
        acc += field[i].count('#')
    for j in col:
        for i in range(H):
            acc += field[i][j] == '#'
    for i in row:
        for j in col:
            if field[i][j] == '#':
                acc -= 1
    if t - acc == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

h, w, k = map(int, input().split(' '))
c = []
for i in range(h):
    instr = input()
    ci = []
    for char in instr:
        if char == '#':
            ci.append(1)
        else:
            ci.append(0)
    c.append(ci)

nanswers = 0
for hnow in range(h+1):
    for vh in itertools.combinations(range(h), hnow):
        for wnow in range(w+1):
            for vw in itertools.combinations(range(w), wnow):
                # print(vh, vw)
                nblacks = 0
                for i in range(h):
                    for j in range(w):
                        if i in vh or j in vw:
                            continue
                        if c[i][j] == 1:
                            nblacks += 1
                if nblacks == k:
                    nanswers += 1

print(nanswers)

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import defaultdict
from copy import deepcopy
H,W,K = map(int,input().split())

M = list(list(input()) for _ in range(H))
way = defaultdict()
ans = 0

for i in range(H+1):
    for j in range(W+1):
        for x in combinations(range(0,H),i):
            for y in combinations(range(0,W),j):
                tmp = deepcopy(M)
                for s in x:
                    for a in range(W):
                        tmp[s][a] = "r"
                for t in y:
                    for a in range(H):
                        tmp[a][t] = "r"
                if sum(i.count("#") for i in tmp) == K:
                    ans += 1

print(ans)

Submission status: Accepted

Solution code:

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

  table = [[0] * w for _ in range(h)]
  total = 0

  for i in range(h):
    for j, c in enumerate(input()):
      if c == "#":
        table[i][j] = 1
        total += 1


  ans = 0
  cols = [sum([table[i][j] for i in range(h)]) for j in range(w)]

  for i in range(2 ** h):
    cols_minus = [0] * w
    tmp_total1 = total

    for row in range(i):
      if i >> row & 1:
        for col in range(w):
          c = table[row][col]
          if c == 1:
            cols_minus[col] -= 1
            tmp_total1 -= 1

    for j in range(2 ** w):
      tmp_total2 = tmp_total1
      for col in range(j):
        if j >> col & 1:
          tmp_total2 -= cols[col] + cols_minus[col]

      if tmp_total2 == k:
        ans += 1




  print(ans)


main()

Submission status: Accepted

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

c = [input() for _ in range(H)]

row_num = 2 ** H
col_num = 2 ** W

result = 0

for row in range(row_num):
    for col in range(col_num):

        row_bin = format(row, 'b')
        row_bin = row_bin.zfill(H)
        col_bin = format(col, 'b')
        col_bin = col_bin.zfill(W)

        count = 0
        for i in range(H):
            for j in range(W):
                if c[i][j] == "#" and row_bin[i] == "0" and col_bin[j] == "0":
                    count += 1

        if count == K:
            result += 1

print(result)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W, K = MAP()
c = [input() for _ in range(H)]

ans = 0

total_black = 0
for i in range(H):
	for j in range(W):
		if c[i][j] == "#":
			total_black += 1

ans = 0
for ny in range(H+1):
	for nx in range(W+1):
		for y in combinations(range(H), ny):
			for x in combinations(range(W), nx):
				black = 0
				for yy in y:
					for i in range(W):
						if c[yy][i] == "#":
							black += 1
				for xx in x:
					for i in range(H):
						if c[i][xx] == "#":
							black += 1

				for xx in x:
					for yy in y:
						if c[yy][xx] == "#":
							black -= 1

				if black == total_black - K:
					ans += 1

print(ans)

Submission status: Accepted

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

rrn = lambda n: [ rr() for _ in xrange(n)]

N, M,K = rrm()
arr = rrn(N)
ans = 0
cum = 0
for i in range(N):
    for j in range(M):
        if arr[i][j] =='#':
            cum +=1
for i in range(2**(N)):
    for j in range(2**(M)):
        total = 0
        for x in range(N):
            for y in range(M):
                if ((1<<x) &i ==0)  and ((1<<y) &j==0) and arr[x][y] =='#':
                    total +=1
        if total == K:
            ans+=1
                
print(ans)

Submission status: Accepted

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


res = 0
ress = 0

import itertools
A =[0,1]
for i in itertools.product(A, repeat=h):
    for j in itertools.product(A, repeat=w):    
        res = 0
        for k in range(h):
            if i[k] ==1:
                for l in range(w):
                    if j[l] ==1 and ab[k][l]=="#":
                        res+=1
        if res ==z:
            ress+=1
print(ress)

Submission status: Accepted

Solution code:
import itertools

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

mas = [input() for i in range(H)]

mas_int = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    for j in range(W):
        if mas[i][j] == '.':
            mas_int[i][j]= 0
        else:
            mas_int[i][j] = 1

H_pers = itertools.product([0,1],repeat=H)

count = 0
for H_per in H_pers:
    W_pers = itertools.product([0, 1], repeat=W)
    for W_per in W_pers:
        mas_ex = mas_int
        mas_sum = 0
        for i in range(H):
            for j in range(W):
                if (H_per[i] == 0) & (W_per[j]==0):
                    mas_sum += mas_int[i][j]

        if mas_sum == K:
            count += 1

print(count)

Submission status: Accepted

Solution code:
h,w,q=map(int,input().split())
c2=[input() for _ in range(h) ]
ans=0
for i in range(2**w):#縦
  
  for j in range(2**h):#横
    c=c2[:]
    for k in range(w):#ビット
      if i>>k &1:
       
        for l in range(h):
          c[l]=c[l][:k]+"b"+c[l][k+1:]
    for k2 in range(h):
      if j>>k2 &1:
        c[k2]="a"*w
    sm=("".join(c).count("#"))

    if sm==q:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy
H, W, K=map(int, input().split())
C=[]
for _ in range(H):
    c=list(input())
    C.append(c)
ans=0
for i in range(2**(H)):
    for k in range(2**(W)):
        copy_c=copy.deepcopy(C)
        for j in range(H):
            for l in range(W):
                if (i>>j)&1: #H行目を赤にする
                    for w in range(W):
                        copy_c[j][w]=0
                if (k>>l)&1: #W列目を赤にする
                    for h in range(H):
                        copy_c[h][l]=0
        count=0
        for h in range(H):
            for w in range(W):
                if copy_c[h][w]=="#":
                    count=count+1
        if count==K:
            # print(copy_c)
            ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
import itertools
h, w, k = map(int, input().split())
c = [list(input()) for _ in range(h)]
ans = 0
for x in itertools.product([True, False], repeat=w):
    for y in itertools.product([True, False], repeat=h):
        t = 0
        for i in range(w):
            for j in range(h):
                if x[i] and y[j] and c[j][i] == '#':
                    t += 1
        if t == k:
            ans += 1
print(ans)

Submission status: Accepted

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

# 標準入力を取得
H, W, K = list(map(int, input().split()))
c = []
for h in range(H):
    c.append(input())

# 求解処理
l = np.zeros(shape=(H, W))
for h, w in itertools.product(range(H), range(W)):
    l[h, w] = (c[h][w] == "#")

ans = 0
for h_bit in range(1 << H):
    l_copy = l.copy()
    for h in range(H):
        if h_bit & (1 << h):
            l_copy[h, :] = [0]
    if np.sum(l_copy) < K:
        continue
    for w_bit in range(1 << W):
        l_copy_copy = l_copy.copy()
        for w in range(W):
            if w_bit & (1 << w):
                l_copy_copy[:, w] = 0
        ans += (np.sum(l_copy_copy) == K)

# 結果出力
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    h,w,k=map(int,input().split())
    c = [input() for _ in range(h)]
    ans = 0
    for y in itertools.product([0,1], repeat=h):
        t1 = c[:]
        for i,v in list(enumerate(y))[::-1]:
            if v == 0:
                del t1[i]
        for x in itertools.product([0,1], repeat=w):            
            if count(t1, x, k) == k:
                ans += 1
    print(ans)

def count(t1, x, k):
    cnt = 0
    for t in t1:
        for i,v in enumerate(x):
            if v == 1 and t[i] == "#":
                cnt += 1
                if cnt > k:
                    return cnt
    return cnt

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W, K = [int(v) for v in input().strip().split(" ")]
C = []
for i in range(H):
    row = [v for v in input().strip()]
    C.append(row)

def calc(C):
    num = 0
    for i in range(H):
        c = C[i]
        for j in range(W):
            if C[i][j] == "#":
                num += 1
    return num

def maskC(C, rowcol):
    masked_C = []
    for i in range(H):
        row = []
        for j in range(W):
            row.append(C[i][j])
        masked_C.append(row)

    rows, cols = [], []
    for index in rowcol:
        if index < H:
            rows.append(index)
        else:
            cols.append(index - H)

    for row in rows:
        masked_C[row] = ["!"] * W
    for col in cols:
        for i in range(H):
            masked_C[i][col] = "!"
    return masked_C


def search(C, From=0, rowcol=[], result=0):
    # print(rowcol)
    masked_C = maskC(C, rowcol)
    num = calc(masked_C)
    # if rowcol == [0, 2]:
    #     print(masked_C)
    # print(num)
    if num == K:
        result += 1
    for i in range(From, H + W):
        result = search(C, i+1, rowcol + [i], result)
    return result

print(search(C))

Submission status: Accepted

Solution code:
from copy import deepcopy
h,w,k=map(int,input().split())
c = [[0 for _ in range(w)] for _ in range(h)]
ans = 0
for i in range(h):
    s = input()
    for j in range(w):
        if(s[j]=="#"):
            c[i][j] = 1

for i in range(2**h):
    ca = deepcopy(c)
    for d in range(h):
        if((i>>d) & 1):
            for e in range(w):
                ca[d][e] = 0
    for j in range(2**w):
        cb = deepcopy(ca)
        for d in range(w):
            if((j>>d)&1):
                for e in range(h):
                    cb[e][d] = 0
        summ = 0
        for j in range(h):
            summ += sum(cb[j])
        if(summ == k):
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
C=[]
ans=0
for i in range(h):
  C.append(input())
for i in range(2**h):
  for j in range(2**w):
    counts=0
    for l in range(h):
      for m in range(w):
        if C[l][m]=="#" and ((i>>l)&1) and ((j>>m)&1):
          counts+=1
    if counts==k:
      ans +=1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

H, W, K = map(int, input().split())
c = []
for _ in range(H):
    s = input()
    s = s.replace('#', '1')
    s = s.replace('.', '0')
    c.append(list(map(int, s)))

red = sum([sum(r) for r in c])

ans = 0
lim = (1 << (H+W))
for i in range(lim):
    tmp = deepcopy(c)
    tmp_red = red
    for j in range(H):
        bit = 1 & (i >> j)
        if bit == 1:
            for k in range(W):
                if tmp[j][k] == 1:
                    tmp[j][k] = 0
                    tmp_red -= 1
    for j in range(W):
        bit = 1 & (i >> (j + H))
        if bit == 1:
            for k in range(H):
                if tmp[k][j] == 1:
                    tmp[k][j] = 0
                    tmp_red -= 1
    if tmp_red == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
c = [["*"]*(W+1)]
num_black = 0
for i in range(H):
    inputed = ["*"] + list(input())
    num_black += inputed.count("#")
    c.append(inputed)
num_black_row = [0]*(H+1)
num_black_col = [0]*(W+1)
for i in range(1, H+1):
    num_black_row[i] = c[i].count("#")
    for j in range(1, W+1):
        if c[i][j] == "#":
            num_black_col[j] += 1
ans = 0
from itertools import combinations
for n_row in range(0, 7):
    for n_col in range(0, 7):
        row_pattern = list(combinations(range(1, H+1), n_row))
        col_pattern = list(combinations(range(1, W+1), n_col))
        for rows in row_pattern:
            for cols in col_pattern:
                temp = 0
                if len(rows) != 0:
                    for row in rows:
                        temp += num_black_row[row]
                if len(cols) != 0:
                    for col in cols:
                        temp += num_black_col[col]
                        dbl = 0
                        for row in rows:
                            if c[row][col] == "#":
                                dbl += 1
                        temp -= dbl
                if num_black - temp == K:
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
dic = {}
for i in range(h):
  s = input()
  for j in range(w):
    if s[j] == '#':
      dic[(i, j)] = 1
res = 0
for ibit in range(2 ** h):
  for jbit in range(2 ** w):
    cnt = 0
    for tpl in dic:
      if ((ibit >> tpl[0]) & 1) and ((jbit >> tpl[1]) & 1):
        cnt += 1
    if cnt == k:
      res += 1
print(res)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
C = [[] for _ in range(H)]
for i in range(H):
    C[i] = input()
ans = 0
for h_bit in range(1<<H):
    h_bit = list(bin(h_bit)[2:].zfill(H))
    for w_bit in range(1<<W):
        w_bit = list(bin(w_bit)[2:].zfill(W))
        count = 0
        for i in range(H):
            if h_bit[i] == '1':
                continue
            for w in range(W):
                if w_bit[w] == '1':
                    continue
                if C[i][w] == '#':
                    count += 1
        if count == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
color=[]
from itertools import combinations
for i in range(H):
	col=list(input())
	color.append(col)
ans=0
cmb_i=[]
for i in range(H+1):
	cmb_i.extend(list(combinations(range(H),i)))
cmb_j=[]
for i in range(W+1):
	cmb_j.extend(list(combinations(range(W),i)))

for i in cmb_i:
	for j in cmb_j:
		cnt=0
		for i0 in range(H):
			for j0 in range(W):
				if color[i0][j0]=="#" and (i0 not in i) and (j0 not in j):
					cnt+=1
		if cnt==K:
			ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0
for hl in product([0, 1], repeat=h):
    for wl in product([0, 1], repeat=w):
        cij = [list(c[i]) if hi == 0 else list('r' * w)
               for i, hi in enumerate(hl)]
        for j, wj in enumerate(wl):
            if wj == 1:
                for i in range(h):
                    cij[i][j] = 'r'
        cnt = 0
        for s in cij:
            cnt += sum(si == '#' for si in s)
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product


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

    ans = 0
    zo = (0, 1)

    select_H = list(product(zo, repeat=H))
    select_W = list(product(zo, repeat=W))

    for sh in select_H:
        for sw in select_W:
            tmp = 0
            for i, cc in enumerate(c):
                for j, ccc in enumerate(cc):
                    if sh[i] == 1 or sw[j] == 1:
                        continue
                    elif ccc == '#':
                        tmp += 1
            if tmp == K:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

hs = [i for i in range(h)]
ws = [i for i in range(w)]
m = []
total = 0
for _ in range(h):
   l = input()
   total += l.count('#')
   m.append(l)

ans = 0
from itertools import combinations
# removing
for i in range(h+1):
   for hcomb in combinations(hs, i):
      total_ = total - sum(m[h_].count('#') for h_ in hcomb)
      for j in range(w+1):
         for wcomb in combinations(ws, j):
            total__ = total_
            for i_ in range(h):
               if i_ in hcomb:
                  continue
               total__ -= len([w_ for w_ in wcomb if m[i_][w_] == '#'])
            if total__ == k:
               ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

h, w, k = map(int, input().split())
field = [list(input()) for _ in range(h)]
npfield = np.array(field)
#%%
ans = 0
for i in itertools.product([False, True], repeat=h):
    for j in itertools.product([False, True], repeat=w):
        cnt = np.count_nonzero(npfield[np.ix_(i, j)] == '#')
        if cnt == k:
            ans += 1

print(ans)