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 as np
import copy
from itertools import combinations
H,W,K=list(map(int,input().split()))
C1=[list(input()) for i in range(H)]
C1=np.array(C1)
listH=[i for i in range(H)]
listW=[i for i in range(W)]
listH2=[]
listW2=[]
for i in range(0,H+1):
    listH2.append(list(combinations(listH,i)))
listH2=[flat for i in listH2 for flat in i]

for i in range(0,W+1):
    listW2.append(list(combinations(listW,i)))
listW2=[flat for i in listW2 for flat in i]

ans=0
for h in listH2:
    for w in listW2:
        ans2=0
        C=copy.deepcopy(C1)
        if h!=():
            for i in h:
                C[i]='.'
        if w!=():
            for j in w:
                C[:,j]='.'
        for i in C:
            for j in i:
                if j=='#':
                    ans2+=1
        if ans2==K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
H , W , K = map(int,input().split())
C = [['' for i in range(W)] for j in range(H)]
c = [[0 for i in range(W)] for j in range(H)]
c = np.array(c) 
for i in range(H):
  C[i] = list(str(input()))
  
C = np.array(C)  
for i in range(W):
  for j in range(H):
    if C[j,i] == '#':
      c[j,i] = 1
Y = [i for i in range(H)]
X = [i for i in range(W)]
S = 0
for n in range(0,len(X) + 1):
  for comb in itertools.combinations(X,n):
    cdum = np.array(c)
    for i in comb:
      for k in range(H):
        cdum[k,i] = 0
    cdumx = np.array(cdum)
    for m in range(0,len(Y) + 1):
      for Comb in itertools.combinations(Y,m):
        for j in Comb:
          for k in range(W):
            cdumx[j,k] = 0
        if np.sum(cdumx) == K:
          S += 1
        cdumx = np.array(cdum)
print(S)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h, w, k = LI()
    c = SR(h)
    ans = 0
    for mask in range(1 << h):
        for mask2 in range(1 << w):
            tmp = 0
            for hi in range(h):
                for wi in range(w):
                    if mask & 1 << hi or mask2 & 1 << wi: continue
                    if c[hi][wi] == "#":
                        tmp += 1
            if tmp == k: ans += 1
            
    print(ans)


    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import copy

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

for n in range(1 << (H + W)):
    c = copy.deepcopy(C)
    for i in range(H):  # Hに対してbit
        if (n >> i) & 1 == 1:
            for w in range(W):  # 一致していたらその行を全てRED
                c[i][w] = "r"
    for j in range(H, H + W):
        if (n >> j) & 1 == 1:
            for h in range(H):
                c[h][j - H] = "r"

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools

import numpy as np

first, second, k = tuple(map(int, sys.stdin.readline().split()))

array = np.full(shape=(first, second), fill_value=0, dtype=np.int32)

for i, line in enumerate(sys.stdin):
  for j, c in enumerate(line.strip()):
    array[i, j] = 1 if c == '#' else 0

#v_counts = np.sum(array, axis=0)
#h_counts = np.sum(array, axis=1)
#array = array[np.argsort(-h_counts)][:, np.argsort(-v_counts)]

#indexes = list(range(h))

count = 0
def index_iter(size):
  indexes = list(range(size))
  for L in range(1, len(indexes)+1):
      for subset in itertools.combinations(indexes, L):
        yield list(subset)

for v_index in index_iter(first):
  for h_index in index_iter(second):
    #print(v_index, h_index)
    #print(array.shape)
    #print(np.sum(array[v_index][:, h_index]))

    if np.sum(array[v_index][:, h_index]) == k:
      count += 1

print(count)

Submission status: Accepted

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



def calc_black(field):
  co = 0
  for i in field:
    for j in i:
      if j == "#":
        co += 1
  return co

import copy
import itertools

aaa = list(itertools.product([0,1],repeat = H ))
bbb = list(itertools.product([0,1],repeat = W ))


count = 0
for i in aaa:
  for j in bbb:
    c_tmp = copy.deepcopy(c)    
    for ind,ii in enumerate(i):
      if(ii):
        c_tmp[ind] = ["r"]*W
    for ind,jj in enumerate(j):
      if (jj):
        for iii in range(H):
          c_tmp[iii][ind] = "r"
          
    if K == calc_black(c_tmp):
      count += 1


print(count)

Submission status: Accepted

Solution code:
import pprint

def main():
    h, w, k = list(map(int, input().split()))
    # c_is_black_matrix = []
    black_num_in_each_row = [0 for _ in range(h)]
    black_num_in_each_column = [0 for _ in range(w)]
    black_num = 0
    black_coords = []

    match_condition_count = 0

    for hi in range(h):
        chars = input()
        black_num_in_each_row[hi] = chars.count("#")
        for wi, c in enumerate(chars):
            if c == "#":
                black_num_in_each_column[wi] += 1
                black_coords.append((hi, wi))
                black_num += 1

    # pprint.pprint(c_is_black_matrix)
    # pprint.pprint(black_num_in_each_row)
    # pprint.pprint(black_num_in_each_column)
    # pprint.pprint(black_coords)

    for hi in range(2 ** h):
        for wi in range(2 ** w):
            h_bin = '{0:0b}'.format(hi).zfill(h)
            w_bin = '{0:0b}'.format(wi).zfill(w)
            current_pattern_black_num = black_num

            # print("{0} {1}".format(h_bin, w_bin))
            for ri, r in enumerate(h_bin):
                if r == "1":
                    current_pattern_black_num -= black_num_in_each_row[ri]
            for ci, c in enumerate(w_bin):
                if c == "1":
                    current_pattern_black_num -= black_num_in_each_column[ci]
            
            for r, c in black_coords:
                if h_bin[r] == "1" and w_bin[c] == "1":
                    current_pattern_black_num += 1

            # print("{0} {1}".format(black_num, current_pattern_black_num))
            
            if current_pattern_black_num == k:
                match_condition_count += 1

    print(match_condition_count)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

import itertools as it

H, W, K = input_int()

maps = []



for h in range(H):
    maps.append(list(one_str()))

maps

#cols
cols_dict={i:[] for i in range(W+1)}

#rows
rows_dict={i:[] for i in range(H+1)}

sums = 0

for x in range(W):
    for y in range(H):
        if maps[y][x]=="#":
            cols_dict[x].append((y,x))
            rows_dict[y].append((y,x))
            sums+=1

count = 0
for x in range(W+1):
    xx = list(it.combinations([i for i in range(W)], x))
    
    for y in range(H+1):
        yy = list(it.combinations([i for i in range(H)], y))

        for xxx in xx:
            sum_set_x = set([])

            for xxxx in xxx:
                sum_set_x = sum_set_x | set(cols_dict[xxxx])
        
            for yyy in yy:
                sum_set_y = set([])
                for yyyy in yyy:
                    sum_set_y = sum_set_y | set(rows_dict[yyyy])

                sum_set = sum_set_x | sum_set_y
                if sums-len(sum_set) == K:
                    count+=1

print(count)

Submission status: Accepted

Solution code:
import itertools
h,w,k=map(int,input().split())
c=[list(input()) for _ in range(h)]
h_list=list(range(h))
w_list=list(range(w))
ans=0
cnt=0
for i in range(h):
  for j in range(w):
    if c[i][j]=="#":
      cnt+=1
if cnt==k:
  ans+=1
  
for i in range(1,h):
  for j in itertools.combinations(h_list, i):
    cnt=0
    for b in j: 
      cnt+=c[b].count("#")
    if cnt==k:
      ans+=1
      
for i in range(1,w):
  for j in itertools.combinations(w_list, i):
    cnt=0
    for b in j:
      for m in range(h):
        if c[m][b]=="#":
          cnt+=1
    if cnt==k:
      ans+=1

for i in range(1,h):
  for j in range(1,w):
    for l in itertools.combinations(h_list, i):
      for m in itertools.combinations(w_list, j):
        cnt=0
        for a in l:
          for b in m:
            if c[a][b]=="#":
              cnt+=1
        if cnt==k:
          ans+=1
print(ans)

Submission status: Accepted

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

count = 0

res = 0

c = []
for j in range(H):
    s = list(map(str, input()))
    c.append(s)
    count += s.count("#")

m = 0
for i in range(2 ** H):
    t = copy.deepcopy(c)
    count_tmp = copy.deepcopy(count)
    for j in range(H):
        if((i>>j) & 1):
            for a in range(W):
                if t[j][a] == "#":
                    t[j][a] = "@"
                    count_tmp -= 1
    for k in range(2 ** W):
        count_tmp2 = copy.deepcopy(count_tmp)
        t2 = copy.deepcopy(t)
        for l in range(W):
            if((k>>l) & 1):
                for b in range(H):
                    if t2[b][l] == "#":
                        t2[b][l] = "@"
                        count_tmp2 -= 1
        m += 1
        if count_tmp2 == K:
            res += 1

print(res)

Submission status: Accepted

Solution code:
import copy

def count_num_of_black(c):
    num = 0
    for row in c:
        for e in row:
            if e == '#':
                num += 1
    return num


if __name__ == "__main__":
    H, W, K = list(map(int, input().split()))
    original = []
    ans = 0
    for i in range(H):
        original.append(list(input()))
    for l in range(2 ** H):
        c = copy.deepcopy(original)
        for i in range(H):
            if ((l >> i) & 1):
                c[i] = list('*'*W)            
            c_after_line_change = copy.deepcopy(c)
        for r in range(2 ** W):
            c_before_row_change = copy.deepcopy(c_after_line_change)
            for j in range(W):
                if ((r >> j) & 1):
                    for k in range(H):
                        c_before_row_change[k][j] = '*'
            if K == count_num_of_black(c_before_row_change):
                ans += 1

    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

board = np.zeros((H, W), dtype=int)

for row in range(H):
    C = list(input())
    for col in range(W):
            board[row][col] = int(C[col] == "#")

ans = 0
for h in range(2 ** H):
    h_idx = list(map(int, list(map(int, str(bin(h))[2:].zfill(H)))))
    h_idx = [i for i, flag in enumerate(h_idx) if flag]
    for w in range(2 ** W):
        w_idx = list(map(int, list(map(int, str(bin(w))[2:].zfill((W))))))
        w_idx = [i for i, flag in enumerate(w_idx) if flag]
        if np.sum(board[h_idx][:, w_idx]) == K:
            ans += 1
print(ans)

Submission status: Accepted

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

for i in range(H):
    table[i] = input()

for i in range(H+1):
    list_H = list(itertools.combinations(range(H), i))
    for X in list_H:
        for j in range(W+1):
            list_W = list(itertools.combinations(range(W), j))
            for Y in list_W:
                H_check = [0 for i in range(H)]
                W_check = [0 for i in range(W)]
                black = 0
                if i != 0:
                    for A in range(i):
                        H_check[X[A]] = 1
                if j != 0:
                    for B in range(j):
                        W_check[Y[B]] = 1
                for k in range(H):
                    for l in range(W):
                        if H_check[k] == 0 and W_check[l] == 0:
                            if table[k][l] == "#":
                                black += 1
                if black == K:
                    ans += 1
                # print(black)
                # S += 1
print(ans)
# print(S)

Submission status: Accepted

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

ans = 0
for i in range(2 ** H):
    # 行方向の黒の個数を列挙
    tmp_black_cnt = black_cnt
    for j in range(H):
        if (i >> j) & 1:
            for k in range(W):
                if colors[j][k] == '#':
                    tmp_black_cnt -= 1
    # print(i, tmp_black_cnt)
    for l in range(2 ** W):
        row_tmp_black_cnt = tmp_black_cnt
        for m in range(W):
            if l == 4:
                a = 1
            if (l >> m) & 1:
                for n in range(H):
                    if colors[n][m] == '#':
                        row_tmp_black_cnt -= 1
        for j in range(H):
            for m in range(W):
                if (l >> m) & 1 and (i >> j) & 1 and colors[j][m] == '#':
                    row_tmp_black_cnt += 1
        # print(i, l, row_tmp_black_cnt)
        if row_tmp_black_cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
m=[]
for _ in range(H):
    m.append([1 if s=='#' else 0 for s in input()])


def cnt(m_in):
    ans = 0
    for r in m_in:
        ans +=sum(r)
    return ans

def paintred(lr,lc):
    #print(m)
    '''
    m_ans = m
    for i in range(H):
        if lr[i] == 1:
            m_ans[i]=[0]*W
    for i in range(W):
        if lc[i] == 1:
            for j in range(H):
                m_ans[j][i]=0
    '''
    m_ans = [[0]*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if lr[i]==0 and lc[j]==0 and m[i][j]==1:
                m_ans[i][j]=1
    return m_ans
        

def f(l):
    #print(l)
    if len(l) == (H+W):
        lr=l[:H]
        lc=l[H:]
        m_tmp=paintred(lr,lc)
        #print(m_tmp,lr,lc,cnt(m_tmp))
        if cnt(m_tmp) == K:
            #print('a')
            return 1
        else:
            #print('b')
            return 0
    ans = 0
    for binary in [0,1]:
        ans += f(l+[binary])
        #print(binary,ans)
    return ans
#print(paintred([0,0],[1,1,0]))
print(f([]))

Submission status: Accepted

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

import numpy as np
import copy
import itertools


M = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if c[i][j]=='.':
            M[i][j] = 0
        else:
            M[i][j] = 1

l = [0,1]

h_list = list(itertools.product(l, repeat=H))
w_list = list(itertools.product(l, repeat=W))
h_list = np.array(h_list)
w_list = np.array(w_list)

ans = 0

for item_h in h_list:
    for item_w in w_list:
        tmp = copy.deepcopy(M)
        l = np.where(item_h==1)
        for item in l:
            tmp[item,:] = 0
        l = np.where(item_w==1)
        for item in l:
            tmp[:,item] = 0
        if np.sum(tmp) == K:
            ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
C = [[] for _ in range(H)]
for i in range(H):
    hoge = input()
    for j in range(W):
        C[i].append(hoge[j])
#print(C)
import copy
ans = 0
for i in range(2**H):
    for j in range(2**W):
        tmp = copy.deepcopy(C)
        for k in range(H):
            if i>>k&1:
                for m in range(W):
                    tmp[k][m] = "r"
        for l in range(W):
            if j>>l&1:
                for n in range(H):
                    tmp[n][l] = "r"
        cnt = 0
        for a in range(H):
            for b in range(W):
                if tmp[a][b] == "#":
                    cnt += 1
        #print(tmp)
        if cnt ==K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def solve(R, C, K, A):
  ans = 0
  for mask in range(1 << C):
    rsums = []
    for row in A:
      rsums.append(0)
      for c in range(C):
        if row[c] == '#' and mask >> c & 1:
          rsums[-1] += 1
      
    count = {0: 1}
    for s in rsums:
      count2 = Counter()
      for k in count:
        v = count[k]
        count2[k] += v
        count2[k + s] += v
      count = count2
    ans += count[K]
  return ans


R, C, K = map(int, raw_input().split())
A = [raw_input() for _ in xrange(R)]
print solve(R, C, K, A)

Submission status: Accepted

Solution code:
y,x,moku=map(int,input().split())
yoko=[0]*y #横列の黒の数
tate=[0]*x #縦行の黒の数
glid=[0]*y
ans=0
for i in range(y):
  glid[i]=input()
  yoko[i]=glid[i].count('#')
m=sum(yoko)
for i in range(x):
  tmp=0
  for j in range(y):
    if glid[j][i]=="#":
      tmp+=1
  tate[i]=tmp
for i in range(2**x):
  xls=[]
  decx=0
  for k in range(x):
    if (i>>k)&1:
      xls.append(k)
      decx+=tate[k]
  for j in range(2**y):
    decy=0
    yls=[]
    for k in range(y):
      if (j>>k)&1:
        yls.append(k)
        decy+=yoko[k]
    decd=0
    for z in xls:
      for w in yls:
        if glid[w][z]=="#":
          decd+=1
    #print([m,i,j,decx,decy,decd])
    tmp=m-decx-decy+decd
    if tmp==moku:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy

# a = get_int()
def get_int():
    return int(input())

# a = get_string()
def get_string():
    return input()

# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]

# a_list = get_string_list():
def get_string_list():
    return input().split()

# a, b = get_int_multi()
def get_int_multi():  # a, b = get_int_multi()
    return map(int, input().split())

# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

ans = 0

def recu(ori, ban, idx, h, w, k, ans):
    if idx == h + w:
        count = 0
        for m in range(h):
            for n in range(w):
                if ban[m][n] == "#":
                    count += 1
        if count == k:
            ans += 1
        return ans

    ans = recu(ori, ban, idx+1, h, w, k, ans)

    ban2 = copy.deepcopy(ban)

    if (idx < h):
        ban2[idx] = ["r"] * w
    else:
        for row in range(h):
            ban2[row][idx-h] = "r"

    ans = recu(ori, ban2, idx+1, h, w, k, ans)

    return ans

def main():
    h, w, k = get_int_multi()

    ans = 0
    ori_ban = []
    for num in range(h):
        ori_ban.append(get_string_char_list())

    print(recu(ori_ban, ori_ban, 0, h, w, k, 0))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,t = map(int,input().split())
masume = [list(input()) for _ in range(h)]

ans = 0

for i in range(2 ** h):
    for j in range(2 ** w):
        count = 0
        for k in range(h):
            if ((i >> k) & 1):
                for l in range(w):
                    if ((j >> l) & 1):
                        if masume[k][l]=="#":
                            count += 1
        if count == t:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

h, w, k = list(map(int, input().split()))
def convert(char):
  if char == '.':
    return 0
  else:
    return 1

def add_elements(c, row, column):
  s = 0
  for i in range(h):
    for j in range(w):
      if (i not in row) and (j not in column):
        s += c[i,j]
  return s

c = np.empty((h, w))

ans = 0

for i in range(h):
  line = list(map(convert, list(input())))
  c[i,:] = np.array(line)

for i in range(h+1):
  for j in range(w+1):
    rows = list(itertools.combinations(range(h),i))
    columns = list(itertools.combinations(range(w),j))
    for row in rows:
      for column in columns:
        s = add_elements(c, row, column)
        if s == k:
          ans += 1

print(ans)

Submission status: Accepted

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

for a in range(2**h):
    sa="0"+str(h)+"b"
    la=list(format(a,sa))
    for b in range(2**w):
        sb = "0" + str(w) + "b"
        lb = list(format(b, sb))
        cnt=0
        for i in range(h):
            for j in range(w):
                if la[i]!="1" and lb[j]!="1" and c[i][j]=="#":
                    cnt+=1
        if cnt==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy


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

    ans = 0
    for hi in range(2 ** h):
        hib = format(hi, f'0{h}b')
        for wi in range(2 ** w):
            wib = format(wi, f'0{w}b')

            CC = copy.deepcopy(C)
            for hci, hc in enumerate(hib):
                for wci, wc in enumerate(wib):

                    if hc == '1':
                        CC[hci] = ['r'] * w

                    if wc == '1':
                        for cc in CC:
                            cc[wci] = 'r'

            if sum([cc.count('#') for cc in CC]) == k:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import copy
h,w,k=map(int,input().split())
c=np.empty((h,w), dtype=int)
for i in range(h):
    s=np.array(list(input()))
    c[i,:]=np.where(s=="#", 1, 0)

ans=0
loop=0
for i in range(2**h):
    tmp=copy.deepcopy(c)
    for j in range(h):
        if (i>>j)&1:
            tmp[j,:]=0
    
    for p in range(2**w):
        tmp1=copy.deepcopy(tmp)
        for q in range(w):
            if (p>>q)&1:
                tmp1[:,q]=0
        if tmp1.sum()==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,k=nii()
c=[list(input()) for i in range(h)]

black=0
for i in c:
  black+=i.count('#')

ans=0
for th in range(2**h):
  for tw in range(2**w):
    h_use=[]
    for i in range(h):
      if (th>>i)&1:
        h_use.append(i)
    w_use=[]
    for i in range(w):
      if (tw>>i)&1:
        w_use.append(i)

    t_cnt=0
    for i in h_use:
      t_cnt+=c[i].count('#')
    for i in w_use:
      for z in range(h):
        if c[z][i]=='#':
          t_cnt+=1
    for i in h_use:
      for j in w_use:
        if c[i][j]=='#':
          t_cnt-=1

    if black-t_cnt==k:
      ans+=1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import copy
import sys

h,w,k = map(int, input().split())
C = np.array([[int(elm=="#") for elm in sys.stdin.readline().strip()] for i in range(h)])

ans = 0
for i in range(2**h):
    for ii in range(2**w):
        g = copy.deepcopy(C)
        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:
import itertools
a = input().split(" ")
row = list(itertools.product([0,1],repeat=int(a[0])))
column = list(itertools.product([0,1],repeat=int(a[1])))
field = []
for i in range(int(a[0])):
    field.append(list(input()))

b = len(row)
c = len(column)
row_m = []
column_m = []
all = 0
for i in range(int(a[0])):
    count = 0
    for j in range(int(a[1])):
        if field[i][j] == "#":
            count += 1
            all += 1
    row_m.append(count)

for i in range(int(a[1])):
    count = 0
    for j in range(int(a[0])):
        if field[j][i] == "#":
            count += 1
    column_m.append(count)
result = 0
for i in row:
    for j in column:
        mainasu = 0

        for k in range(len(i)):
            if i[k] == 1:
                for l in range(len(j)):
                    if j[l] == 1:
                        if field[k][l] == "#":
                            mainasu += 1
        
        row_num = sum([x*y for (x,y) in zip(i,row_m)])
        column_num = sum([x*y for (x,y) in zip(j,column_m)])
        if int(a[2]) == all - (row_num+column_num - mainasu):
            result += 1
print(result)

Submission status: Accepted

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for _ in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))


def count_black(subset, c):
    black = total_black
    for i in range(len(c)):
        if i in subset:
            for item in c[i]:
                if '#' == item:
                    black -= 1

    for i in range(len(c[0])):
        if len(c) + i in subset:
            for j in range(len(c)):
                if j not in subset:
                    if '#' == c[j][i]:
                        black -= 1
    return black


def candidates(subset, k, c):
    start_at = 0 if len(subset) == 0 else subset[-1] + 1
    go_to = len(c) + len(c[0])
    for i in range(start_at, go_to):
        yield subset + [i]


solutions = 0
def backtrack(subset, k, c):
    curr = count_black(subset, c)
    if curr < k:
        return
    if curr == k:
        global solutions
        solutions += 1
    for cand in candidates(subset, k, c):
        backtrack(cand, k, c)


def solve(h, w, k, c):
    backtrack([], k, c)
    return solutions


total_black = 0
if __name__ == "__main__":
    h, w, k = arr_in()
    c = []
    for _ in range(h):
        c.append(str_in())
        total_black += c[-1].count("#")
    out(solve(h, w, k, c))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache
from numba import jit

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	h, w, k = LI()
	grid = GRIDfromString(h,w)
	ans = 0
	cnt = 0
	for i in range(h):
		for j in range(w):
			h_comb = list(itertools.combinations(list(range(h)),i))
			w_comb = list(itertools.combinations(list(range(w)),j))
			if i == 0 and j == 0:
				if np.count_nonzero(grid == b'#') == k:
					ans += 1
			elif i == 0 and j > 0:
				for w_omits in w_comb:
					if np.count_nonzero(np.delete(grid,list(w_omits),1) == b'#') == k:
						ans += 1
			elif i > 0 and j == 0:
				for h_omits in h_comb:
					if np.count_nonzero(np.delete(grid,list(h_omits),0) == b'#') == k:
						ans += 1
			else:
				for h_omits in h_comb:
					grid_tmp = np.delete(grid,list(h_omits),0)
					for w_omits in w_comb:
						if np.count_nonzero(np.delete(grid_tmp,list(w_omits),1) == b'#') == k:
							ans += 1
	print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import copy
h, w, k = map(int, input().split())
table = [list(input()) for _ in range(h)]
ans = 0
for ptr_h in itertools.product([0, 1], repeat=h):
    for ptr_w in itertools.product([0, 1], repeat=w):
        times = 0
        tmp = copy.deepcopy(table)
        for i, v in enumerate(ptr_w):
            if v == 1:
                for p in tmp:
                    p[i] = "red"
        for i, v in enumerate(ptr_h):
            if v == 1:
                for ind, l in enumerate(tmp):
                    if ind == i:
                        for n in range(w):
                            l[n] = "red"
        for i in tmp:
            for j in i:
                if j == "#":
                    times += 1
        if times == k:
            ans += 1
print(ans)