Problem:


Score : 300 points

Problem Statement

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

Consider doing the following operation:

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

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

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

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

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

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

Sample Output 4

208



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


Sample output:
5

Submission status: Accepted

Solution code:
import itertools
import copy

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

c = ['a'] * H
cnt = 0

for i in range(H):
    c[i] = input()
    cnt += c[i].count('#')

#print(cnt)
#print(c)
cnt = cnt - K
ans = 0
comH = list(range(H))
comW = list(range(W))

#print(comH, comW)

for n in range(len(comH)+1):
    for combiH in itertools.combinations(comH, n):
        #print(list(combiH))
        LcomH = list(combiH)
        tmpc = copy.deepcopy(c)
        Hchange = 0
        for i in LcomH:
            Hchange += tmpc[i].count('#')
            tmpc[i] = tmpc[i].replace('#', 'r')
        for m in range(len(comW)+1):
            for combiW in itertools.combinations(comW, m):
                #print(list(combiW))
                LcomW = list(combiW)
                Wchange = 0
                for j in LcomW:
                    for gyo in range(H):
                        if tmpc[gyo][j] == '#':
                            Wchange += 1
                #print(tmpc)
                #print(Hchange, Wchange)
                if Hchange + Wchange == cnt:
                    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy
h,w,k2=map(int, input().split())
c = [list(input()) for i in range(h)]
ans = 0

for i in range(2**h):
    for j in range(2**w):
        d = copy.deepcopy(c)
        for k in range(h):
            if i%(2**(k+1))//(2**k)==1:
                for j2 in range(w):
                    d[k][j2]='r'
        for l in range(w):
            if j%(2**(l+1))//(2**l)==1:
                for i2 in range(h):
                    d[i2][l]='r'
        black = 0
        for i3 in range(h):
            for j3 in range(w):
                if d[i3][j3]=='#':
                    black +=1
        if black == k2:
            ans+=1
print(ans)

Submission status: Accepted

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

#for h in range(H):
#  for w in range(W):
#    if c[h][w] == '#':

h = len(c)
hl = []
for i in range(2 ** h):
 bit_set = []
 for j in range(h):
   if ((i >> j) & 1):
     bit_set.append(j)

 hl.append(bit_set)

wl = []
for i in range(2 ** W):
 bit_set = []
 for j in range(W):
   if ((i >> j) & 1):
     bit_set.append(j)
 wl.append(bit_set)


ans = 0
for w in wl:
  wll = []
  for ww in w:
    wll.append(ww)

  for h in hl:
    count = 0
    for i, cc in enumerate(c):
      if not i in h:
        for k, ccc in enumerate(cc):
          if not k in wll:
            if ccc == '#':
              count += 1

    if count == K:
      ans += 1


print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools
import copy

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

def p(arr):
	for i in arr:
		for j in i:
			print(j, end="")
		print()

def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans

def dyeh(arr,b):
	for i in range(len(b)):
		if b[i]==1:
			for j in range(w):
				arr[i][j]="."
	return arr

def dyew(arr,b):
	for i in range(len(b)):
		if b[i]==1:
			for j in range(h):
				arr[j][i]="."

def count(arr):
	ans = 0
	for i in arr:
		for j in i:
			if j=="#":
				ans+=1
	return ans

h,w,k = readInts()
c = [list(input()) for i in range(h)]
ans = 0
for i in bitArr(h):
	d = copy.deepcopy(c)
	dyeh(d,i)

	for j in bitArr(w):
		e = copy.deepcopy(d)
		dyew(e,j)
		if count(e)==k:
			ans+=1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import numpy as np
H, W, K = list(map(int, input().split()))

org = np.zeros((H, W), dtype=np.uint8)

'''
.: shiro -> 0
#: kuro  -> 1
'''

for h in range(H):
    l = list(input())
    l = [0 if val == '.' else 1 for val in l]

    org[h, :] = l

# =========

j_list = [[None]]
for j_b in range(2 ** H): # 全列挙

    tmp_l = []
    for j_l in range(H):
        j = (j_b >> j_l) & 1  # こいつが赤に塗る列
        if j == 1:
            tmp_l.append(j_l)

    if len(tmp_l) > 0:
        j_list.append(tmp_l)
        

i_list = [[None]]
for i_b in range(2 ** W): # 全列挙

    tmp_l = []
    for i_l in range(W):
        i = (i_b >> i_l) & 1  # こいつが赤に塗る列
        if i == 1:
            tmp_l.append(i_l)

    if len(tmp_l) > 0:
        i_list.append(tmp_l)
        
     
cnt = 0
for j_s in j_list:
    for i_s in i_list:
        dst_array = org.copy()

        for j in j_s:
            if j is not None:
                dst_array[j, :] = 0

        for i in i_s:
            if i is not None:
                dst_array[:, i] = 0

       
        sumval = np.sum(dst_array)

        if sumval == K:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

cells = []
for _ in range(h):
  cells.append(list(input()))
cells = np.asarray(cells)

n_choice = 0
for n_target_rows in range(h + 1):
  target_rows = list(itertools.combinations(range(h), n_target_rows))
  
  for n_target_clms in range(w + 1):
    target_clms = list(itertools.combinations(range(w), n_target_clms))
    
    for rows in target_rows:
      row_converted_cells = cells.copy()
      row_converted_cells[rows, :] = 'r' * w
      
      for clms in target_clms:
        clm_converted_cells = row_converted_cells.copy()
        clm_converted_cells[:, clms] = 'r'
        n_black = np.count_nonzero(clm_converted_cells == '#')
        
        if n_black == k:
          n_choice += 1
                    
print(n_choice)

Submission status: Accepted

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

for i in range(1<<W):
    D = [0]*37
    D[0] = 1

    for c in C:
        cnt = 0
        for b in range(6):
            if (i & (1<<b)) and c[b] == '#':
               cnt += 1

        for j in range(36-cnt, -1, -1):
            D[j+cnt] += D[j]

    ANS += D[K]

print(ANS)

Submission status: Accepted

Solution code:
import numpy as np
def main():
  h,w,k = map(int, input().split())
  c = []
  for i in range(h):
    c.append(list(input()))
  c = np.array(c)=='#'
  
  count = 0
  for i in range(2**(h+w)):
    tmp = np.array(list(bin(4096+i)))=='1'
    row = tmp[(h+w)*-1:w*-1]
    col = tmp[w*-1:]
    if c[np.ix_(row,col)].sum()==k:
      count += 1
  print(count)
main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
import random
from decimal import Decimal
import itertools as it


H, W, K = [int(x) for x in stdin.readline().rstrip().split()]
# A = list(map(int, input().split()))
c = []
for i in range(H):
    c.append(list(input()))
# print(c)
# for i in range(H):
a = [[(0,)]]
a2 = [[(0,)]]
b = []
b2 = []
for i in range(1, H+1):
    b.append(i)
for i in range(1, H):
    a.append(list(it.combinations(b, i)))
for i in range(1, W+1):
    b2.append(i)
for i in range(1, W):
    a2.append(list(it.combinations(b2, i)))
# print(a)
b.append(0)
b2.append(0)
ans = 0
ans1 = 0
for iw, vw in enumerate(a2):
    for kw in range(len(vw)):
        for ih, vh in enumerate(a):
            for kh in range(len(vh)):
                vw[kw] = list(vw[kw])
                vh[kh] = list(vh[kh])
                ans = 0
                for iww in range(1, W+1):
                    if iww not in vw[kw]:
                        for ihh in range(1, H+1):
                            if ihh not in vh[kh]:
                                if c[ihh-1][iww-1] == '#':
                                    ans += 1
                # print(vw[kw],vh[kh],ans)
                if ans == K:
                    ans1 += 1
print(ans1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
H, W, K = map(int, input().split())

c_list = []
for i in range(H):
    c_list.append(str(input()))

case_list = []

for i in range(2 ** (H + W)):
    case_list.append(format(i, "#0" + str(H + W + 2) + "b")[2:])

ans = 0
for i in range(2 ** (H + W)):
#     temp_c_list = c_list.copy()
    counter = 0
    for j in range(H):
        for k in range(W):
            if case_list[i][j] == "0" and case_list[i][H + k] == "0" and c_list[j][k] == "#":
                counter += 1
    if counter == K:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
import string
def main():  #startline-------------------------------------------
    h, w, K = map(int, input().split())
    cmat = [input() for i in range(h)]
    ans = 0
    sublist = []
    com_sublist = [] #sublistの補集合
    #最初に黒の数を数えておく
    firstblack = 0
    for i in range(h):
        firstblack += cmat[i].count("#")
    for i in range(1 << h):
        for j in range(h):
            if (i >> j) & 1:
                sublist.append(cmat[j])
            else:
                com_sublist.append(cmat[j])
        #選ばれた横の行に対して行う操作
        lensub = len(sublist)
        lencomsub = len(com_sublist)
        elecnt = 0
        for ele in sublist:
            elecnt += ele.count("#")
        #次に選ばれてないcomの縦の行を全探索する
        #行列を転置したほうが分かりやすい
        newcomsub = []
        for j in range(w):
            newcomsub.append([com_sublist[k][j] for k in range(lencomsub)])
        #今は縦の長さがw,横の長さがlencomsub
        for j in range(w):
            if not (newcomsub[j]):
                continue
            newcomsub[j] = "".join(newcomsub[j])
        subcomsub = []
        for j in range(1 << w):
            comelecnt = 0
            for k in range(w):
                if (j >> k) & 1:
                    subcomsub.append(newcomsub[k])
            #comsubのなかから選ばれたほう(subcomb)、補集合は考えなくてよい
            for subele in subcomsub:
                comelecnt += subele.count("#")
            #これで最初の値から選ばれた値をひいたものが等しければよい
            if firstblack - (elecnt + comelecnt) == K:
                ans += 1
            subcomsub = []
        #リストの初期化
        sublist = []
        com_sublist = []

    print(ans)


if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import numpy as np
H, W, K = (int(i) for i in input().split())
C = np.zeros((H, W))
for h in range(H):
    C[h,:] = [int(i=='#') for i in list(input())]
res = 0
for i in range(2 ** H):
    for j in range(2 ** W):
        hv = np.array(list(format(i, '0{}b'.format(H))), dtype='int')
        wv = np.array(list(format(j, '0{}b'.format(W))), dtype='int')
        if C[hv==1,:][:, wv==1].sum() == K:
            res = res + 1
print(res)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
H, W, K = map(int, input().split())
L = np.array([list(input()) for i in range(H)])
Ans = 0
for h in range(H):
    for w in range(W):
        if L[h,w] == '.':
            L[h,w] = '0'
        else:
            L[h,w] = '1'
L = L.astype("int64")

def del_w(w):#w列目
    if w != 0:
        for h1 in range(H):
            L1[h1,w-1] =  0   

def del_h(h):#h行目
    if h != 0:
        for w1 in range(W):
            L1[h-1,w1] =  0
            
H_list = []
for h in range(H+1):
    H_list += list(itertools.combinations(range(1,H+1),h))

W_list = []
for w in range(W+1):
    W_list += list(itertools.combinations(range(1,W+1),w))
    
for h_list in H_list:
    for w_list in W_list:
        
        L1 = L.copy()
        
        for w1 in w_list :
            for h in range(H):
                L1[h,w1-1] =  0
                
        for h1 in h_list :
            for w in range(W):
                L1[h1-1,w] =  0 
                
        if np.sum(L1) == K:
            #print(L1,h_list,w_list)
            Ans += 1
            
print(Ans)

Submission status: Accepted

Solution code:
# C
import itertools

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

l1 = [i for i in range(H)]
l2 = [i for i in range(W)]

ans = 0
for i in range(H + 1):
    p1 = list(itertools.combinations(l1, i))
    for j in p1:
        for k in range(W + 1):
            p2 = list(itertools.combinations(l2, k))
            for l in p2:
                cnt = 0
                for m in range(H):
                    for n in range(W):
                        if (m not in list(j) and n not in list(l) and lst[m][n] == '#'):
                            cnt += 1
                if (cnt == K):
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:

def main():
    H,W,K = map(int,input().split())
    board = [] #board[行][列]
    for h in range(H):
        board.append(list(input()))

    total = 0

    for bit_h in range(2 ** H):
        for bit_w in range(2 ** W):
            check_board = [[True for _ in range(W)] for _ in range(H)]
            for h_cheker in range(H):
                if (bit_h >> h_cheker) & 1:
                    for temp_w in range(W):
                        check_board[h_cheker][temp_w] = False
            for w_checker in range(W):
                if (bit_w >> w_checker) & 1:
                    for temp_h in range(H):
                        check_board[temp_h][w_checker] = False
            counter = 0
            for h in range(H):
                for w in range(W):
                    if check_board[h][w] and board[h][w] == "#":
                        counter += 1

            if counter == K:
                total += 1

    print(total)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

H,W,K=map(int,input().strip().split())
c=[]
for n in range(H):
    c.append(list(input()))
for h in range(H):
    for w in range(W):
        if c[h][w]==".":
            c[h][w]=0
        else:
            c[h][w]=1
c=np.array(c)

cnt=0
def rec(l,H,W,K):
    global cnt
    if len(l)==H+W:
        t=c.copy()
        for i in range(len(l)):
            if i<=H-1:
                if l[i]==1:
                    t[i,:]=0
            else:
                if l[i]==1:
                    t[:,i-H]=0
        if np.sum(t)==K:
            cnt+=1
    else:
        for n in range(2):
            l.append(n)
            rec(l,H,W,K)
            l.pop()

rec([],H,W,K)
print(cnt)

Submission status: Accepted

Solution code:
import copy
H,W,K=map(int,input().split())
List = []
for i in range (H):
  List.append(list((input())))
res = 0
List2 = copy.deepcopy(List)
List3 = copy.deepcopy(List)

                   
def checkBlack(listA, check):
  inter =0
  for k in range(H):
    inter += listA[k].count("#")
  if check == inter:
    return True
  else:
    return False
  
#横は塗らずに縦だけ塗る
def paintH(listB,k):
  for i in range(H):
    listB[i][k] = 0
  return listB

#縦は塗らずに横だけ塗る
def paintW(listB,k):
  for i in range(W):
    listB[k][i] = 0
  return listB

for bits in range(2**W):
  for j in range(W):
    if((bits>>j) & 1): 
      List3 = paintH(List2,j)
  List4 = copy.deepcopy(List3)  
  for bits2 in range(2**H):
    for l in range(H):
      if((bits2>>l) & 1): 
        List2 = paintW(List4,l)
    if checkBlack(List4,K):
      res +=1
    List4 = copy.deepcopy(List3)
  List2 = copy.deepcopy(List)
print(res)

Submission status: Accepted

Solution code:
import copy
H, W, K = map(int,input().split())
c = [list(input()) for j in range(H)]
c_tmp =copy.deepcopy(c)


w_combs =[]
for i in range(2**W):
  w_comb = []
  for j in range(W):
    if (i >>j) & 1 :
      w_comb.append(j)
  w_combs.append(w_comb)

h_combs = []
for i in range(2**H):
  h_comb = []
  for j in range(H):
    if (i >>j) & 1 :
      h_comb.append(j)
  h_combs.append(h_comb)


ans = 0

for h_comb in h_combs:
  for w_comb in w_combs:
    c_tmp =copy.deepcopy(c)


    for w_one in w_comb:
      for y in range(H):
        c_tmp[y][w_one] = 'r'
    
    for h_one in h_comb:
      for x in range(W):
        c_tmp[h_one][x] = 'r'
    

    cnt_black = 0
    for row in c_tmp:
      for c_i in row:
        if c_i == '#':
          cnt_black +=1

    if cnt_black == K:
      ans +=1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
inpl = lambda: list(map(int,input().split()))
H, W, K = inpl()
c = [input() for _ in range(H)]

ans = 0
for p in product(range(2),repeat=H):
    for q in product(range(2),repeat=W):
        num = 0
        for h in range(H):
            if p[h]:
                continue
            for w in range(W):
                if q[w]:
                    continue
                if c[h][w] == '#':
                    num += 1
                    if num > K:
                        break
            else:
                continue
            break
        else:
            if num == K:
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

answer=0

C=tuple(C)
A=[]

hs=[]
ws=[]
suuji=[i for i in range(H)]
for i in range(2 ** H):
  skill=[]
  for j in range(H):
    if ((i >> j) & 1):
        skill.append(suuji[j])
  hs.append(skill)
del hs[0]
suuji=[i for i in range(W)]
for i in range(2 ** W):
  skill=[]
  for j in range(W):
    if ((i >> j) & 1):
        skill.append(suuji[j])
  ws.append(skill)
del ws[0]

suuji=0
for h in hs:
    for w in ws:
        number=0
        D=np.array(C)
        for h_ in h:
            D[h_,:]=0
        for w_ in w:
            D[:,w]=0
        for c in D:
            for c_ in c:
                if c_=='#':
                    number+=1
        if number==K:
            answer+=1
for h in hs:
    number=0
    D=np.array(C)
    for h_ in h:
        D[h_,:]=0

    for c in D:
        for c_ in c:
            if c_=='#':
                number+=1
    if number==K:
        answer+=1
for h in ws:
    number = 0
    D = np.array(C)
    for h_ in h:
        D[:, h_] = 0

    for c in D:
        for c_ in c:
            if c_ == '#':
                number += 1
    if number == K:
        answer += 1

number=0
D=np.array(C)
for d in D:
    for d_ in d:
        if d_=='#':
            number+=1
if number==K:
    answer+=1

print(answer)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations

def blk_counter(mat):
    cnt = np.count_nonzero(mat == '#')
    return cnt


def main():
    H, W, K = map(int,input().split(' '))
    r_index = [i for i in range(H)]
    c_index = [i for i in range(W)]
    mat = []
    for i in range(H):
        mat.append(list(input()))
    
    mat = np.array(mat)

    blk_cnt = 0
    cnt = 0

    dele_r_list = []
    dele_c_list = []

    for i in range(H+1):
        for j in combinations(r_index,i):
            dele_r_list.append(j)

    for i in range(W+1):
        for j in combinations(c_index,i):
            dele_c_list.append(j)

    for deler in dele_r_list:
        mat_d = np.delete(mat, deler, 0)
        for delec in dele_c_list:
            mat_dd = np.delete(mat_d, delec, 1)
            blk_cnt = blk_counter(mat_dd)
            if blk_cnt == K:
                cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
h,w,k = map(int,input().split())
c= [[0] * w for i in range(h)]
for i in range(h):
  l = list(input())
  for j in range(w):
    if l[j]=="#":
      c[i][j]=1
cc = 0
for bit in range(2**(h+w)):
  temp = copy.deepcopy(c)
  for i in range(h):
    if ((bit >> (i+w)) & 1):
      temp[i][:]=[0]*w
  for j in range(w):
    if ((bit >> j) & 1):
      for i in range(h):
        temp[i][j]=0
  temp_c = 0
  for i in range(h):
    for j in range(w):
      if temp[i][j]==1 : temp_c+=1
  if temp_c==k : cc+=1
print(cc)

Submission status: Accepted

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

hlst = [0] * H
wlst = [0] * W
looph = []
loopw = []
def dfs(cnt, lst, loop):
    if cnt == len(lst):
        loop.append(copy.deepcopy(lst))
        return
    for i in range(2):
        lst[cnt] = i
        cnt += 1
        dfs(cnt, lst, loop)
        cnt -= 1

dfs(0, hlst, looph)
dfs(0, wlst, loopw)

total = 0
for i in looph:
    for j in loopw:
        cnt = 0
        for k in range(H):
            for l in range(W):
                if i[k] == 1:
                    continue
                if j[l] == 1:
                    continue
                if c[k][l] == '#':
                    cnt += 1

        if cnt == K:
            total += 1

print(total)

Submission status: Accepted

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

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

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

c_rep = c.copy()
for i in range(h):
    for j in range(w):
        if c[i][j] == ".":
            c_rep[i][j] = 0
        else:
            c_rep[i][j] = 1
c = np.array(c_rep)

hp = [""] * (h+1)
for i in range(1,h+1):
    hp[i] = list(itertools.combinations(range(h), i))

hp_lis = [[]]
for i in range(len(hp)):
    if i == "":
        hp_lis.append([])
    else:
        for j in range(len(hp[i])):
            hp_lis.append(list(hp[i][j]))

wp = [""] * (w+1)
for i in range(1,w+1):
    wp[i] = list(itertools.combinations(range(w), i))

wp_lis = [[]]
for i in range(len(wp)):
    if i == "":
        wp_lis.append([])
    else:
        for j in range(len(wp[i])):
            wp_lis.append(list(wp[i][j]))

count = 0
for i in range(len(hp_lis)):
    for j in range(len(wp_lis)):
        #print(i,j)
        temp = np.delete(c, obj=hp_lis[i], axis=0)
        temp = np.delete(temp, obj=wp_lis[j], axis=1)
        #print("temp", temp)
        if np.sum(temp) == k:
            count += 1

print(count)

Submission status: Accepted

Solution code:
import itertools

[H,W,K] = list(map(int,input().split()))
count=0

c = []
for i in range(H):
    c.append(list(input()))

# print('c',c)

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

#gyou=[0]*H
#retu=[0]*W
a = [0,1]
Gs = list(itertools.product(a, repeat=H))
Rs = list(itertools.product(a, repeat=W))

for G in Gs:
    for R in Rs:
        # print('G,R:', G,R)
        l=0
        gyo=0
        for i in G:
            if i==1:
                #行を潰す
                gyo+= c[l].count('#')
            l+=1
        # print('gyo:', gyo)

        #列を潰す
        r=0
        retu=0
        for j in R:
            if j==1:
                #retu=0
                for k in range(H):
                    #print('k,r,c[k][r]:',k,r,c[k][r] )
                    if c[k][r]=='#':
                        retu+=1
            r+=1
        # print('retu:', retu)

        #かぶるやつ
        iii=0
        hiku=0
        for ii in G:
            jjj=0
            for jj in R:
                if ii==1 and jj==1:
                    if c[iii][jjj]=='#':
                        hiku+=1
                jjj+=1
            iii+=1
        # print('hiku:', hiku)

        if ini - (gyo+retu-hiku)==K:
            count+=1
        # print('count:',count)

# print('ini:',ini)
print(count)

Submission status: Accepted

Solution code:
import copy

H, W, K = map(int, input().split())
ll = [[0 for w in range(W)] for h in range(H)]
ans = 0

for h in range(H):
  row = input()
  for w in range(W):
    if (row[w] == '.'):#白
      ll[h][w] = 0
    else:
      ll[h][w] = 1

for h in range(2 ** H):
  hstr = format(h, f'0{H}b')
  for w in range(2 ** W):
    wstr = format(w, f'0{W}b')
    l = copy.deepcopy(ll)
    count = 0
    for h1 in range(H):
      for w1 in range(W):
        if (hstr[h1] == '1' or wstr[w1] == '1'):
          l[h1][w1] = 0
        count += l[h1][w1]
    if (count == K):
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy
s=0
a=0
H,W,K=map(int,input().split())
L=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
  c=list(input())
  L[i]=c
for i in range(2**(H+W)):
  c=bin(i)[2:]
  c=str(c)
  if len(c)<H+W:
    c=str((H+W-len(c))*"0"+c)
  T=copy.deepcopy(L)
  for k in range(H+W):
    if c[k]=="1":
      if k<H:
        T[k]=[0]*W
    if c[k]=="1" and k>=H:
      for n in range(H):
        T[n][k-H]=0
  for j in range(1,(H*W)+1):
    if j%W==0:
      if T[(j//W)-1][-1]=="#":
        a+=1
    else:
      if T[j//W][(j%W)-1]=="#":
        a+=1
  if a==K:
    s+=1
  a=0
print(s)

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

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

    res = 0

    for h in list(product([0, 1], repeat=H)):
        for w in list(product([0, 1], repeat=W)):
            hash_count = 0
            for row in range(H):
                if h[row]:
                    continue
                else:
                    for col in range(W):
                        if C[row][col] == '#' and w[col] == 0:
                            hash_count += 1
            
            if hash_count == K:
                res += 1
    
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
l=[input()for _ in range(h)]
def t(m,h,w):
    n=[]
    for i in range(w):
        s=''
        for j in range(h):
            s+=m[j][i]
        n.append(s)
    return n
ans=0
for i in range(2**h):
    m=l.copy()
    b=bin(i)[2:].zfill(h)
    for n,i_ in enumerate(b):
        if i_=='1':
            m[n]='x'*w
    m=t(m,h,w)
    for j in range(2**w):
        x=m.copy()
        b=bin(j)[2:].zfill(w)
        for n,j_ in enumerate(b):
            if j_=='1':
                x[n]='x'*h
        c=0
        for r in x:
            c+=r.count('#')
        if c==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools

def bit(n, k):
    s = [0 for _ in range(k)]
    u = n
    b = 0
    while(u > 0):
        s[k-1-b] += u % 2
        u = u // 2
        b += 1
    return s

h, w, k = map(int, input().split())
c = []
for _ in range(h):
    c.append(input())
    
tate = [0 for _ in range(w)]
yoko = [0 for _ in range(h)]
for i in range(w):
    for j in range(h):
        if(c[j][i] == "#"):
            tate[i] += 1
for i in range(h):
    yoko[i] += c[i].count("#")
m = sum(yoko)

ans = 0
for i in range(2**h):
    for j in range(2**w):
        g = m
        comb_s = bit(i, h)
        comb_t = bit(j, w)
        for p in range(h):
            if(comb_s[p] == 1):
                g -= yoko[p]
        for q in range(w):
            if(comb_t[q] == 1):
                g -= tate[q]
        for p in range(h):
            for q in range(w):
                if(c[p][q] == "#" and comb_s[p] == 1 and comb_t[q] == 1): 
                    g += 1
        if(g == k):
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int,input().split())
c = []
for i in range(h):
    r = []
    s = input()
    for j in s:
        if j == '.':
            r.append(0)
        else:
            r.append(1)
    c.append(r)

ans = 0

from copy import deepcopy
import numpy as np

for b in range(2**(h+w)):
    m = deepcopy(c)
    key = bin(b)[2:].zfill(h+w)
    for row in range(h):
        if key[:h][row] == '1':
            for col in range(w):
                m[row][col] = 0
    for col in range(w):
        if key[h:][col] == '1':
            for row in range(h):
                m[row][col] = 0
    if np.sum(m) == k:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

H, W, K = map(int, input().split())
c = [['.' for j in range(6)] for i in range(6)]
for i in range(H):
    tmp = str(input())
    for j in range(len(tmp)):
        c[i][j] = tmp[j]
    
hp = list(itertools.product([0,1], repeat=H))
wp = list(itertools.product([0,1], repeat=W))

hl = []
for elem in hp:
    hl.append([i for i, x in enumerate(list(elem)) if x == 1])
wl = []
for elem in wp:
    wl.append([i for i, x in enumerate(list(elem)) if x == 1])

def func(hli, wli, c):
    tmp = 0
    for i in range(len(hli)):
        for j in range(len(wli)):
            if c[hli[i]][wli[j]] == '#':
                tmp += 1 
            
    return tmp

ans  = 0
for hli in hl:
    for wli in wl:
        if func(hli, wli, c) == K:
            ans += 1

print(ans)