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 numpy
import numpy
import itertools

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

c = numpy.array(c, dtype = numpy.int)
ans = 0

for pi in itertools.product([0,1], repeat = H):
    for pj in itertools.product([0,1], repeat = W):
        Ii = numpy.array(pi) == 1
        Ij = numpy.array(pj) == 1
        d = c.copy()
        d[Ii, :] = 0
        d[:, Ij] = 0
        if numpy.sum(d) == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
#from bisect import bisect_left as bl                #c++ lowerbound bl(array,element)
#from bisect import bisect_right as br               #c++ upperbound br(array,element)
#from __future__ import print_function, division    #while using python2


def modinv(n,p):
    return pow(n,p-2,p)

from itertools import combinations

def main():
    #sys.stdin = open('input.txt', 'r')
    #sys.stdout = open('output.txt', 'w')

    n, m, k = [int(x) for x in input().split()]
    mat = [[0] * m for i in range(n)]
    for i in range(n):
        s = input()
        for j in range(m):
            if s[j] == '.':
                mat[i][j] = 1
    # print(mat)

    c = 0
    rows = [x for x in range(n)]
    cols = [x for x in range(m)]

    new_rows = []
    new_cols = []

    # print(rows)
    # print(cols)

    for i in range(2, n+1):
        temp = list(combinations(rows, i))
        # print(temp)
        for x in temp:
            new_rows.append(list(x))
    rows = [[x] for x in range(n)]
    for x in new_rows:
        rows.append(x)

    for i in range(2, m+1):
        temp = list(combinations(cols, i))
        # print(temp)
        for x in temp:
            new_cols.append(list(x))
    cols = [[x] for x in range(m)]
    for x in new_cols:
        cols.append(x)

    rows.append([])
    cols.append([])
    # print(rows)
    # print(cols)
    

    ans = 0
    # print(mat)
    for r in range(len(rows)):
        for c in range(len(cols)):
            new_mat = [[0] * m for x in range(n)]
            
            row = rows[r]
            col = cols[c]
            
            for i in range(n):
                for j in range(m):
                    if i in row or j in col:
                        new_mat[i][j] = 2
                    else:
                        new_mat[i][j] = mat[i][j]
            

            count_black = 0
            # print(new_mat)
            for x in new_mat:
                count_black += x.count(0)
            if count_black == k:
                ans += 1
            # print(row, col)
            # print(new_mat)
            # print(ans)
            # print()
    print(ans)

#------------------ Python 2 and 3 footer by Pajenegod and c1729-----------------------------------------
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__ == '__main__':
   main()

Submission status: Accepted

Solution code:
import copy
import itertools

def delete_H(num, C_rend):
  lenj = len(num)
  if lenj != 0:
    for count in range(lenj):
      C_rend[j[count]] = "r" * W
  return(C_rend)

def delete_W(num, C_rend):
  lenl = len(num)
  if lenl != 0:
    for count in range(lenl):
      for i in range(H):
        c_h_list = list(C_rend[i])
        c_h_list[l[count]] = "r"
        C_rend[i] = "".join(c_h_list)
  return(C_rend)

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

counter = 0
C_orig = copy.deepcopy(C)  

for i in range(H + 1):
  for j in itertools.combinations(range(H), i):
    for k in range(W + 1):
      for l in itertools.combinations(range(W), k):
        C = copy.deepcopy(C_orig)
        modified_C_a = delete_H(j, C)
        modified_C_b = delete_W(l, modified_C_a)
        result = "".join(modified_C_b)
        
        if result.count("#") == K:
          counter += 1
        
print(counter)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,itertools
import numpy as np
input = sys.stdin.readline
h, w, k = map(int, input().split())
c_ = []
for i in range(h):
  cc = input().split()
  c_.append([0 if s=='.' else 1 for s in cc[0]])
# print(c_)
c = np.array(c_)
# print(c)
# print(c[1,:])
# print(c[:,2])
h_s = []
for i in range(2**h):
  lis_h = []
  for j in range(h):
    if (i>>j) &1==1:
      lis_h.append(j)
  h_s.append(lis_h)
  
w_s = []
for i in range(2**w):
  lis_w = []
  for j in range(w):
    if (i>>j) &1==1:
      lis_w.append(j)
  w_s.append(lis_w)
# print(h_s,w_s)
count = 0
# if np.sum(c)==k:
#  count+=1
for hh in h_s:
  for ww in w_s:
    c_copy = c.copy()
    c_copy[hh,:]=0
    c_copy[:,ww]=0
    # print(c_copy)
    if np.sum(c_copy)==k:
      count+=1
print(count)

Submission status: Accepted

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

def generate_n_bit(n):
    bins= []
    for i in range(2**n):
        bins.append(list(str(format(i,'b').zfill(n))))
    
    return bins

h_all = generate_n_bit(h)
w_all = generate_n_bit(w)
ans = 0
n = 23
extra = 1
  
for i in range(1,n+1): 
    extra = extra * i 

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

for i_l in h_all:
    for j_l in w_all:
        c  = 0 
        fields = copy.deepcopy(field)
       
        
        for i_i, i in enumerate(i_l):
            for j_i, j in enumerate(j_l):
                n = 23
                extra = 1
  
                for xx in range(1,n+1): 
                    extra = extra * xx 
                if i == '1':
                    for a in range(w):
                        fields[i_i][a] = 'r'
                    
                if j == '1':
                    for b in range(h):
                
                        fields[b][j_i] = 'r'
                        
        
        for q in range(h):
            for e in range(w):
                if fields[q][e] == '#':
                    c += 1
       
        if c == k:
            ans += 1
        
n = 23
fact = 1
  
for i in range(1,n+1): 
    fact = fact * i         
                
print(ans)

Submission status: Accepted

Solution code:
import copy
H, W, K = map(int, input().split())
C = [list(input()) for _ in range(H)]
ans = 0
for i in range(1<<H):
  D = copy.deepcopy(C)
  for h in range(H):
    if (i>>h & 1):
      for l in range(W):
        D[h][l] = '.'
  for j in range(1<<W):
    k = 0
    for w in range(W):
      if not (j>>w & 1):
        for m in range(H):
          if D[m][w] == '#':
            k += 1
    if k == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
import itertools

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

field = []
for i in range(h):
  field.append(list(input()))
  
total = 0
for i in itertools.product([0,1], repeat=h):
  for j in itertools.product([0,1], repeat=w):
    count = 0
    temp = copy.deepcopy(field)
    for l in range(h):
      if i[l] == 1:
        temp[l] = ['.'] * w
    for l in range(w):
      if j[l] == 1:
        for m in range(h):
          temp[m][l] = '.'
    for l in range(h):
      count += temp[l].count('#')
    if count == k:
      total += 1
      
print(total)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[]
for i in range(h):
    y=list(input())
    c.append(y)
s=0
for i in range(2**h):
    for j in range(2**w):
        t=0
        for a in range(h):
            for b in range(w):
                if (i//(2**a))%2==1 and (j//(2**b))%2==1 and c[a][b]=="#":
                    t+=1
        if t==k:
            s+=1
print(s)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
MAP = [list(input()) for i in range(H)]
Ho = [MAP[i].count('#') for i in range(H)]
Whole = sum(Ho)
count = 0

def ve(j):
    count = 0
    for i in range(H):
        if MAP[i][j] == '#':
            count += 1
    return count

Ve = [ve(j) for j in range(W)]

def iter_p_adic(p, n):
    from itertools import product
    tmp = [range(p)] * n
    return product(*tmp)

ite_H = list(iter_p_adic(2, H))
ite_V = list(iter_p_adic(2, W))

for idx_H in ite_H:
    for idx_V in ite_V:
        count_double = 0
        count_minus = 0
        h = list(idx_H)
        v = list(idx_V)
        for k in range(W):
            if v[k] == 1:
                count_minus += Ve[k]
        
        for i in range(H):
            for j in range(W):
                if v[j] == 1 and h[i] == 1 and MAP[i][j] == '#':
                    count_double += 1
            if h[i] == 1:
                count_minus += Ho[i]
        if Whole - count_minus + count_double == K:
            count += 1

print(count)

Submission status: Accepted

Solution code:
from copy import copy

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

def draw_tate(c, i):
    #c = copy(c)
    for j in range(len(c)):
        c[j] = c[j][0:i] + "." + c[j][i+1:]
    #return c

def draw_yoko(c, i):
    #c = copy(c)
    c[i] = "." * w
        #return c

a = 0
b = 2 ** h # 横
e = 2 ** w # 縦
for i in range(b):
    for j in range(e):
        d = copy(c)
        for m in range(h):
            if ((1 << m) & i) != 0:
                draw_yoko(d, m)
        for l in range(w):
            if ((1 << l) & j) != 0:
                draw_tate(d, l)
        d = ''.join(d)
        if d.count("#") == k:
            a += 1
print(a)

Submission status: Accepted

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

total = list()
row = [0]*h
col = [0]*w

for i in range(h):
    wh = list(map(int,list(input().replace(".","0").replace("#","1"))))
    for j in range(w):
        col[j] += wh[j]
    row[i] = sum(wh)
    total.append(wh)

tc = sum(row)
ans = 0

for i in range(2**h):
    for j in range(2**w):
        tmp = list()
        cou = tc
        ti =i
        tj =j
        for th in range(h):
            if ti == 0:
                break
            if ti%2 == 1:
                cou -= row[th]
                tmp.append(th)
            ti = ti//2 
        for tw in range(w):
            if tj == 0:
                break
            if tj%2 == 1:
                cou -= col[tw]
                for hhh in tmp:
                    cou += total[hhh][tw]
            tj = tj//2
        if cou == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations, permutations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

H, W, K = nn()
C = sl(H)
D = array2(H, W)

for i in range(H):
    for j in range(W):
        D[i][j] = 1 if C[i][j] == "#" else 0

ans = 0
for n in range(2**H):
    for m in range(2**W):
        E = deepcopy(D)
        for i in range(H):
            if (n>>i) & 1 == 1:
                for k in range(W):
                    E[i][k] = 0

        for j in range(W):
            if (m>>j) & 1 == 1:
                for k in range(H):
                    E[k][j] = 0

        #print(n, m, E),

        count = 0
        for i in range(H):
            for j in range(W):
                if E[i][j] == 1:
                    count += 1

        #print(count)
        if count == K:
            #print("o"),
            ans += 1

        #print("")

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product

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


def cnt_black(lists):
    cnt = 0
    for lis in lists:
        cnt += Counter(lis).get('#', 0)
    return cnt


def to_red(lists, row_ops, col_ops):
    lists = lists.copy()
    for idx in range(H):
        if row_ops[idx] == '1':
            lists[idx] = ['r'] * W
    for idx in range(W):
        if col_ops[idx] == '1':
            lists = [lis[:idx] + ['r'] + lis[idx + 1:] for lis in lists]
    return lists

row_patterns = [format(n, f'0{H}b') for n in range(2 ** H)]
col_patterns = [format(n, f'0{W}b') for n in range(2 ** W)]

cnt = 0
for row_ops, col_ops in product(row_patterns, col_patterns):
    red_lists = to_red(lists, row_ops, col_ops)
    if cnt_black(red_lists) == K:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import copy
import numpy as np
H, W, K = map(int, input().split())
c_map = []
for _ in range(H):
    c = np.array(list(input()))
    c_map.append(c)
c_map = np.array(c_map)

ans = 0
for bit1 in range(2**H):
    y_map = copy.deepcopy(c_map)
    for i in range(H):
        if bit1 & (1<< i):
            y_map[i] = np.where(y_map[i]!=1, ".", y_map[i])

    for bit2 in range(2**W):
        x_map = copy.deepcopy(y_map)
        for j in range(W):
            if bit2 & (1<< j):
                x_map[:,j] = np.where(x_map[:,j]!=1, ".", x_map[:,j])
        if np.count_nonzero(x_map == "#") == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
def f(k):
    if k == 1:
        return [[0],[1]]
    else:
        h = f(k-1)
        h_plus = [hi + [0] for hi in h]
        h_minus = [hi + [1]for hi in h]
        return h_plus + h_minus

def count(select_h,select_w,hw):
    chw = hw.copy()
    count = 0
    for i,si in enumerate(select_h):
        for j,sj in enumerate(select_w):
            if not(si or sj):
                count += chw[i][j]
    return count

H,W,K = map(int,input().split( ))
hw = [list(str(input())) for _ in range(H)]
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
             hw[h][w] = 1
        else:
            hw[h][w] = 0

select_hs = f(H)
select_ws = f(W)
ans = 0
for select_h in select_hs:
    for select_w in select_ws:
        if count(select_h,select_w,hw) == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:


def resolve():
    import sys
    import numpy as  np
    input = sys.stdin.readline
    hwk = [int(x) for x in input().rstrip().split(" ")]
    h = hwk[0]
    w = hwk[1]
    k = hwk[2]
    matrix = np.zeros((h, w))

    for i in range(h):
        # 0白 1黒
        row = input().rstrip()
        for j in range(w):
            matrix[i, j] = 0 if row[j] == "." else 1
    
    import itertools
    ans = 1 if np.count_nonzero(matrix) == k else 0
    for n in range(1,h+w):
        for pair in itertools.combinations(list(range(h+w)), n):
            tmp = matrix.copy()
            # print(pair)
            # print(tmp)
            for i in pair:
                if(i < h):
                    tmp[i, :] = 0
                else:
                    tmp[:, i-h] = 0
            
            if np.count_nonzero(tmp) == k:
                ans += 1
            
            # print(tmp)
            # print(np.count_nonzero(tmp))
    print(ans)
        

        
            




if __name__ == "__main__":
    resolve()


# を理解する。そうすると、明らかに制限時間内に実行が終わらないソースコードを出さなくなる。ちなみに、競プロでは 108108 ～ 109109 回程度のループが回せるといわれている。

Submission status: Accepted

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

def to_int(s):
    if s == ".":
        return 0
    else:
        return 1

c = [0] * H
for i in range(H):
    c[i] = list(map(to_int, input()))

res = 0
for h_bit in range(1<<H):
    for w_bit in range(1<<W):
        sum_c = 0
        h = h_bit
        for i in range(H):
            if h % 2 == 1:
                w = w_bit
                for j in range(W):
                    if w % 2 == 1:
                        sum_c += c[i][j]
                    w //= 2
            h //= 2
        if sum_c == K:
            res += 1
    
print(res)

Submission status: Accepted

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

def contBlack(g, h, w):
    cnt = 0
    for i in range(h):
        for j in range(w):
            if g[i][j] == '#':
                cnt += 1
    return cnt

def turnrow(g, a, w):
    for j in range(w):
        g[a][j] = 'R'



def turnclumn(g, a, h):
    for i in range(h):
        g[i][a] = 'R'

from copy import deepcopy

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

    cnt = 0
    for i in range(1<<H):           
        G = deepcopy(grid)
        for j in range(H):
            if (i>>j) & 1:
                turnrow(G, j, W)

        for k in range(1<<W):
            Gg = deepcopy(G)
            for l in range(W):
                if (k>>l) & 1:
                    turnclumn(Gg, l, H)
            
            # for i in range(H):
            #     print(Gg[i])
            # print()

            if contBlack(Gg, H, W) == K:
                cnt += 1

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

Submission status: Accepted

Solution code:
import itertools,copy
H,W,K=map(int,input().split())
c=[]
for i in range(H):
    c.append(list(input()))
tmp=copy.deepcopy(c)
ans=0
for i in itertools.product([0,1], repeat=H+W):
    c=copy.deepcopy(tmp)
    for j in range(H):
        if(i[j]==0):
            for k in range(W):
                c[j][k]="R"
    for j in range(H,H+W):
        if(i[j]==0):
            for k in range(H):
                c[k][j-H]="R"
    s=0
    for i in range(H):
        s+=c[i].count("#")
    if(s==K):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations


h, w, k = map(int, input().split())
C = np.array([list(input()) for j in range(h)]) == "#"
out = 0

for row_n in range(h):
    for row_select in combinations(C, r=row_n + 1):
        # print(list(zip(*row_select)))
        for col_n in range(w):
            for col_select in combinations(zip(*row_select), r=col_n + 1):
                if np.array(col_select).sum() == k:
                    out += 1
print(out)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement as cwr
H,W,K=map(int,input().split())
C=[]
for _ in range(H):
    c = list(map(str, input()))
    C.append(c)
ans=0
lh = [0 for _ in range(H)]
while True:    
    lw = [0 for _ in range(W)]
    while True:
        num =0
        for i in range(H):
            for j in range(W):
                if lh[i]==1 or lw[j]==1 or C[i][j]==".":
                    continue
                else:
                    num+=1
        if num==K:
            ans +=1
        if sum(lw)==W:
            break
        for k in range(W):
            if lw[k]==0:
                lw[k]=1
                break
            if lw[k]==1:
                lw[k]=0
    if sum(lh)==H:
        break
    for k in range(H):
        if lh[k]==0:
            lh[k]=1
            break
        elif lh[k]==1:
            lh[k]=0

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations
h,w,k = map(int,input().split())
c = np.empty((h,w))
for i in range(h):
    c[i,:] = np.array(list(map(int,input().replace(".",'0 ').replace("#",'1 ').split())))

cnt = 0
row,col = range(h),range(w)

for i in range(1,h+1):
    for j in range(1,w+1):
        if i==h and j==w:
            break
        for x in combinations(row, i):
            for y in combinations(col,j): 
                s = c[np.array(x),:]
                s = s[:,np.array(y)].sum()
                if s==k:
                    cnt+=1
if c.sum()==k:cnt+=1
print(cnt)

Submission status: Accepted

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

c = [list(input()) for _ in range(h)]
#print(c)


black = []
a = 0

for i in range(h):
    for j in range(w):
        if c[i][j] == "#":
            black.append((i, j))


for i in range(2 ** (h+w)):
    total = 0
    row = []
    col = []
    for j in range(h + w):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            if j < h:
                row.append(j)
            else:
                col.append(j - h)
    #print(row, col)

    #print(black)
    s = 0
    for r, c in black:
        #print(r, c, row, col)
        if (r not in row) and (c not in col):
            s += 1
        #print(s)

    if s == k:
        a += 1

print(a)

Submission status: Accepted

Solution code:
import itertools

import numpy as np


def _run(H, W, K, C):
    input = np.zeros([H, W], dtype=np.int8)
    for h in range(H):
        for w in range(W):
            if C[h][w] == "#":
                input[h, w] = 1

    count = 0
    for r in itertools.product(*[[0, 1] for _ in range(H + W)]):
        copy_input = input.copy()
        for h in range(H):
            if r[h] == 1:
                copy_input[h] = 0
        for w in range(W):
            if r[H + w] == 1:
                copy_input[:, w] = 0

        if np.sum(copy_input) == K:
            count += 1
    print(count)


def _main():
    H, W, K = map(int, input().split())
    C = [str(input()) for _ in range(H)]
    _run(H, W, K, C)


if __name__ == "__main__":
    _main()

Submission status: Accepted

Solution code:
import numpy as np

s = input().split()

H = int(s[0])
W = int(s[1])
K = int(s[2])

m = np.zeros((H, W))

def make_list(n):
  r = []
  b = bin(n)[2:]
  for i in range(len(b)):
    if b[i] == "1":
      r.append(len(b) - i - 1)
  return r
    
for i in range(H):
  s = input()
  for j in range(W):
    if s[j] == "#":
      m[i, j] = 1

result = 0
for i in range(2**H):
  h = make_list(i)
  for j in range(2**W):
    w = make_list(j)
    M = np.delete(m, h, 0)
    M = np.delete(M, w, 1)
    if np.sum(M) == K:
      result += 1
      #print(h, w)
      
print(result)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
import itertools


def input():
    return sys.stdin.readline().rstrip()


def main():
    H, W, K = map(int, input().split())
    C = [[] for _ in range(H)]
    for i in range(H):
        C[i] = list(input())
    ccc =[0]*37
    ans = 0

    for h in itertools.product("01", repeat=H):
        for w in itertools.product("01", repeat=W):
            count = 0

            for i in range(H):
                for j in range(W):
                    if h[i] == "1" and w[j] == "1" and C[i][j] == "#":
                        count += 1
            ccc[count] +=1

    print(ccc[K])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np


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

c = np.array([[1 if s == '#' else 0 for s in input()] for _ in range(h)])

hs = [list(hs) for hh in range(1, h + 1) for hs in combinations(range(h), hh)]
ws = [list(ws) for ww in range(1, w + 1) for ws in combinations(range(w), ww)]

a = 0
for hss in hs:
    cc = c[hss]
    for wss in ws:
        if np.sum(cc[:, wss]) ==k:
            a += 1
print(a)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
from itertools import permutations
import itertools
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
def print_red(field, high):
    for i in range(len(high)):
        if high[i] == 1:
            field[i] = ['X' for _ in range(len(field[0]))]
    return field

def count_sharp_without_width(field, width):
    count = 0
    for i in range(len(field)): #高さ(横線)
        for j in range(len(width)): #横(縦ライン)
            if width[j] == 1:
                continue
            if field[i][j] == '#':
                count += 1
    return count

def main():
    h, w, k = list(map(int,input().split()))
    field = [list(input()) for _ in range(h)]
    #print(field)

    ans = 0

    for high in itertools.product([1, 0], repeat=h):
        field_temp = deepcopy(field)
        field_temp = print_red(field_temp, high)
        count_k = 0
        #print(field_temp)
        for i in range(h):
            count_k += field_temp[i].count('#') 
        #print(count_k)
        if count_k < k: continue # kを下回ったらブレイク
        
        for width in itertools.product([1, 0], repeat=w):
            #print(width)
            count_k = count_sharp_without_width(field_temp, width)
            if count_k == k:
                ans += 1
    print(ans)
    return 0

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import copy

def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

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

ans = 0
change_h = np.array(["." for _ in range(h)])
change_w = np.array(["." for _ in range(w)])

for i in range(2**h):
    for j in range(2**w):
        idx_i, idx_j = [], []
        for ii in range(h):
            if i>>ii & 1:
                idx_i.append(ii)
        for jj in range(w):
            if j>>jj & 1:
                idx_j.append(jj)

        d = copy.deepcopy(c)
        for item in idx_i:
            d[item, :] = change_w
        for item in idx_j:
            d[:, item] = change_h
        x = np.count_nonzero(d == "#")
        if x == k:
            ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
import itertools

def checker(data, h, w, k, h_ax, w_ax):
  flag = {i: {j: 0 for j in range(w)} for i in range(h)}
  for i in h_ax:
    for j in range(w):
      flag[i][j] = 1
  for i in w_ax:
    for j in range(h):
      flag[j][i] = 1
  c = 0
  for i in range(h):
    for j in range(w):
      if data[i][j] == "#" and flag[i][j] == 0:
        c += 1
  if c == k:
    return True
  else:
    return False

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

counter = 0
for i in range(h):
  for j in range(w):
    for h_ax in itertools.combinations(range(h), i):
      for w_ax in itertools.combinations(range(w), j):
        if checker(data, h, w, k, h_ax, w_ax):
          counter += 1

print(counter)

Submission status: Accepted

Solution code:
H,W,K = map(int, input().split())
c_table = [input() for _ in range(H)]
SUM = 0
for i in range(H):
    for j in range(W):
        if c_table[i][j] == '#':
            SUM += 1
answer = 0

for i in range(2 ** (H)):
    tmp_h = [False] * H
    for j in range(H):
        if i >> j & 1:
            tmp_h[j] = True
    for k in range(2**W):
        tmp_w = [False] * W
        for l in range(W):
            if k>>l & 1:
                tmp_w[l] = True
        cnt = 0
        for ti in range(len(tmp_h)):
            if tmp_h[ti]:
                for tk in range(W):
                    if c_table[ti][tk] == '#':
                        cnt += 1
        for tj in range(len(tmp_w)):
            if tmp_w[tj]:
                for tk in range(H):
                    if tmp_h[tk]:
                        continue
                    if c_table[tk][tj] == '#':
                        cnt += 1

        if K == SUM - cnt:
            answer += 1
        

print(answer)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
S = []
ans = 0

def binlist(x,k):
  s = []
  for i in range(k):
    s.append(x % 2)
    x = x // 2
  return s
    
for i in range(H):
  temp1 = input()
  temp2 = [temp1[i] for i in range(len(temp1))]
  S.append(temp2)
for i in range(2 ** H):
  for j in range(2 ** W):
    A = binlist(i, H)
    B = binlist(j, W)
    c = 0
    for k in range(H):
      for l in range(W):
        if A[k] == 0 and B[l] == 0 and S[k][l] == "#":
          c += 1
    if c == K:
      ans += 1
      
print(ans)