Problem:


Score : 300 points

Problem Statement

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

Consider doing the following operation:

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

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

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

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

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

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

Sample Output 4

208



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


Sample output:
5

Submission status: Accepted

Solution code:
from functools import reduce

def numofbits(x):
    ret = 0
    while x > 0:
        ret += (x & 1)
        x >>= 1
    return ret

H,W,K = map(int, input().split())
c = []
bk = 0
for i in range(H):
    c.append(reduce(lambda x,y: 2*x+y, map(lambda x: 1 if x == '#' else 0, input())))
#print(c)

def f(x):
    ret = 0
    for j in range(2**W):
        r = 0
        for i in x:
            r += numofbits(i & j)
        if r == K:
            #print(x,bin(j))
            ret += 1
    return ret

ans = 0
for i in range(2**H):
    x = []
    for j in range(H):
        if i & 2**j:
            x.append(c[j])
    #print("@",bin(i),x)
    ans += f(x)

print(ans)

Submission status: Accepted

Solution code:
h,*c=open(0)
h,w,k=map(int,h.split())
print(sum(k==sum(y>>w+z//w&y%2**w>>z%w&1and'.'>c[z//w][z%w]for z in range(h*w))for y in range(1<<h+w)))

Submission status: Accepted

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

for i in range(2 ** H):
    for j in range(2 ** W):
        c_c = copy.deepcopy(c)
        for k in range(H):
            if (i >> k) & 1:
                c_c[k] = ["r" for _ in range(W)]
        for l in range(W):
            if (j >> l) & 1:
                for u in range(H):
                    c_c[u][l] = "r"
        cnt = 0
        for k in range(H):
            cnt += c_c[k].count("#")
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
import copy

h, w, k = map(int, input().split())
ans = 0
c = [list(input()) for _ in range(h)]
for i in range(1<<h):
    for j in range(1<<w):
        black = 0
        for l in range(h):
            for m in range(w):
                if c[l][m] == '#' and (i>>l & 1 == 0 and j>>m & 1 == 0):
                    black += 1
        if black == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,*c=open(0)
h,w,k=map(int,h.split())
print(sum(k==sum(y>>w>>z//w&y%2**w>>z%w&1and'.'>c[z//w][z%w]for z in range(h*w))for y in range(1<<h+w)))

Submission status: Accepted

Solution code:
import numpy as np

HWK=np.array(input().split(" "),dtype=np.int64)
H=HWK[0]
W=HWK[1]
K=HWK[2]

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

count=0

for maskR in range((1<<H)):
    for maskC in range((1<<W)):
        black=0
        for i in range(H):
            for j in range(W):
                if(((maskR>>i)&1)==0) and (((maskC>>j)&1)==0) and C[i][j]=="#":
                    black+=1
        if(black==K):
            count+=1

print(count)

Submission status: Accepted

Solution code:
from itertools import combinations
H, W, K = map(int, input().split())
C = [input() for _ in range(H)]
res = 0
for i in range(1 << H):
    for j in range(1 << W):
        tmp = 0
        for h in range(H):
            if (i >> h) & 1:
                continue
            for w in range(W):
                if (j >> w) & 1:
                    continue
                tmp += C[h][w] == '#'
        if tmp == K:
            res += 1
print(res)

Submission status: Accepted

Solution code:
h,*c=open(0)
h,w,k=map(int,h.split())
print(sum(k==sum(y//2**w>>z//w&y%2**w>>z%w&1and'.'>c[z//w][z%w]for z in range(h*w))for y in range(1<<h+w)))

Submission status: Accepted

Solution code:
import itertools
def resolve():
    H,W,K = map(int,input().split())
    bi = []
    bj = []
    for i in range(H):
        row = input()
        for j in range(W):
            if row[j]=='#':
                bi.append(i)
                bj.append(j)
    
    dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]
    # 行を削除してみる
    count = 0

    row_iters = [itertools.combinations(range(H), i) for i in range(0,H+1)]
    for row_iter in row_iters:
        for target_rows in row_iter:
            row_del_position = [i_position for i_position, i in enumerate(bi) for target_row in target_rows if i == target_row]
            #new_bi = dellist(bi, row_del_position)
            new_bj = dellist(bj, row_del_position)
            if len(new_bj)>=K:
                #print('bi>=K')
                #print(target_rows)
                #print(new_bi, new_bj)
                column_iters = [itertools.combinations(range(W), i) for i in range(0,W+1)]
                for column_iter in column_iters:
                    for target_columns in column_iter:
                        column_del_position = [j_position for j_position, j in enumerate(new_bj) for target_column in target_columns if j == target_column]
                        #new_bi2 = dellist(new_bi, column_del_position)
                        new_bj2 = dellist(new_bj, column_del_position)
                        
                        if len(new_bj2) == K:
                            #print('bi==K')
                            #print(target_columns)
                            count +=1
    print(count)
resolve()

Submission status: Accepted

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

for i in range(2**(H+W)):
  flag=[[True for _ in range(W)] for u in range(H)]
  for j in range(H):
    if ((i>>j)&1)==1:
      flag[j]=[False for _ in range(W)]
  for j in range(W):
    if ((i>>(j+H))&1)==1:
      for k in range(H):
        flag[k][j]=False
  num=0
  for i in range(H):
    for j in range(W):
      if flag[i][j] and C[i][j]=="#":
        num+=1
  if num==K:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
h,*c=open(0)
h,w,k=map(int,h.split())
v=2**w
print(sum(k==sum(y//v>>z//w&y%v>>z%w&1and'.'>c[z//w][z%w]for z in range(h*w))for y in range(2**h*v)))

Submission status: Accepted

Solution code:
import sys

def S(): return sys.stdin.readline().rstrip()
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

H,W,K = map(int,S().split())
c = [LS2() for i in range(H)]
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            c[i][j] = 0
        else:
            c[i][j] = 1

from copy import deepcopy

# bit全探索

ans = 0
for i in range(2**H):
    A = []
    for k in range(H):
        if (i >> k) & 1:
            A.append(k)
    for j in range(2**W):
        B = []
        for l in range(W):
            if (j >> l) & 1:
                B.append(l)
        d = deepcopy(c)
        for k in range(H):
            for l in range(W):
                if k in A or l in B:
                    d[k][l] = 0
        if sum(sum(d[k]) for k in range(H)) == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
#DEBUG = True
DEBUG = False
if DEBUG:
    f=open("202007_1st/C_input.txt")
else:
    f=sys.stdin
WHITE='.'
BLACK='#'
def count_black(H_index,W_index):
    count_tmp=0
    for _ in range(H):
        if _ in H_index:
            continue
        for __ in range(W):
            if __ in W_index:
                continue
            if S[_][__]==BLACK:
                count_tmp+=1
    return count_tmp
ans=0
H,W,K=map(int,f.readline().split())
S=[f.readline().strip() for _ in range(H)]
H_indices=[_ for _ in range(0,H)]
W_indices=[_ for _ in range(0,W)]
combi_list_H=[[-1]]
combi_list_W=[[-1]]
for _ in range(1,H):
    combi_list_H.extend(list(combinations(H_indices,_)))
for _ in range(1,W):
    combi_list_W.extend(list(combinations(W_indices,_)))
for _ in combi_list_H:
    for __ in combi_list_W:
        if count_black(_,__)==K:
            ans+=1
print(ans)
f.close()

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
C = []
for _ in range(h):
    C.append(input())
ans = 0
for hbit in range(1<<h): # red row bit
    for wbit in range(1<<w): # red col bit
        c = 0
        for i in range(h):
            for j in range(w):
                if hbit>>i & 1 and wbit>>j & 1:
                    if C[i][j] =='#': c += 1
        if c == k: ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

H, W, K = map(int, input().split(' '))
s = [input() for i in range(H)]
ans = 0
for i in product([0, 1], repeat=H + W):
    h = list(i[:H])
    w = list(i[H:])
    tmp = 0
    for j in range(H):
        for k in range(W):
            if h[j] == w[k] == 0 and s[j][k] == "#":
                tmp += 1
    if tmp == 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 h in range(2**H):
    for w in range(2**W):
        tmp=0
        for i in range(H):
            for j in range(W):
                if h>>i&1 and w>>j&1 and c[i][j]=="#":
                    tmp+=1
        if tmp==K:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0
for row in product([0,1], repeat=h):
    for col in product([0,1], repeat=w):
        cnt = 0
        for i in range(h):
            if row[i] == 1:
                continue
            for j in range(w):
                if col[j] == 1:
                    continue
                if grid[i][j] == '#':
                    cnt += 1
        if cnt == k:
            ans += 1

print(ans)

Submission status: Accepted

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

ans = 0

for cols in range(1 << H):
  for rows in range(1 << W):
    black = 0
    for i in range(H):
      if (cols >> i) & 1:
        continue
      for j in range(W):
        if (rows >> j) & 1:
          continue
        if a[i][j] == "#":
          black += 1
    if black == K:
      ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
H,W,K = (int(X) for X in input().split())
Tile = np.zeros((H,W),dtype=bool)
for T in range(0,H):
    Tile[T,:] = np.array([True if X=='#' else False for X in list(input())])

Count = 0
for R in range(0,pow(2,H)):
    DrawR = [int(X) for X in list(('{:0'+str(H)+'b}').format(R,'b'))]
    
    TileR = np.copy(Tile)
    for RB in range(0,H):
        if DrawR[RB]:
            TileR[RB] = False
            
    for C in range(0,pow(2,W)):
        TileC = np.copy(TileR)
        DrawC = [int(X) for X in list(('{:0'+str(W)+'b}').format(C,'b'))]
        for CB in range(0,W):
            if DrawC[CB]:
                TileC[:,CB] = False
        if np.sum(TileC)==K:
            Count += 1
print(Count)

Submission status: Accepted

Solution code:
def resolve():
    import numpy as np
    import itertools
    import copy

    H, W, K = map(int, input().split())
    table = []
    for _ in range(H):
        s = list(input())
        table.append(s)

    ans = 0
    for i in range(2**H):
        mask_h = format(i, '0{}b'.format(H))
        for j in range(2**W):
            mask_w = format(j, '0{}b'.format(W))
            black = 0
            for di in range(H):
                for dj in range(W):
                    if mask_h[di] == '0' and mask_w[dj] == '0' and table[di][dj] == "#":
                        black += 1
            if black == K:
                ans += 1
    print(ans)

resolve()

Submission status: Accepted

Solution code:
h,w,x=map(int,input().split())
c=[input() for _ in [0]*h]
print(sum(x==sum(i>>k&1 and j>>l&1 and c[k][l]=='#' for k in range(h) for l in range(w)) for i in range(2**h) for j in range(2**w)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

    ans = 0
    for i in range(H + 1):
        for j in range(W + 1):
            for n in itertools.combinations(list(range(H)), i):
                for m in itertools.combinations(list(range(W)), j):
                    count = 0
                    for a in n:
                        for b in m:
                            if C[a][b] == "#":
                                count += 1
                    if count == K:
                        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
##a = int(stdin.readline().rstrip())
##b, c = [int(x) for x in stdin.readline().rstrip().split()]
##s = stdin.readline().rstrip()
##a = list(set(b))  重複を削除
##a = list(map(int,[int(x) for x in stdin.readline().rstrip().split()])) a[0, 1, 2, ...]
##a = [[0] * 2 for _ in range(n)]  a[0,0]
##v = [s[i: i+2] for i in range(0, len(s), 2)]
##  s="12345678" を v=["12","34","56","78"] にするイメージ
##s = "".join(list)リストを文字列に変換[""]は区切り文字
##a.sort(key=itemgetter(1))リストをソートできるよ(from operator import itemgetterが必要)
##sort_p = sorted(p) 昇順ソート

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
import numpy as np
import random
import bisect
import copy
# stdin = open("sample.txt")


MOD = 1000000007
INF = float('inf')
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

def keta(kazu): # 入力されたintを桁ごとに分解，リストで出力
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers): # 最小公倍数
    return reduce(math.gcd, numbers)

def combination(m,n): # mCn
    
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def pow_k(x,n):  # (x**n)の計算の高速化
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x

def fact(n): # nの素因数分解の結果を辞書で出力 fuct(24) → {2: 3, 3: 1}
    arr = {}
    temp = n
    for i in range(2,int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
    if temp != 1:
        arr[temp] = 1
    if arr == {}:
        arr[n] = 1
    return arr


    
def main():
    h, w, k = [int(x) for x in stdin.readline().rstrip().split()]
    board = []
    kuro = 0
    pattern_h = [[0]*h for _ in range(2 ** h)]
    pattern_w = [[0]*w for _ in range(2 ** w)]
    ans = 0
    nokori = 0
    
    for _ in range(h):
        s = stdin.readline().rstrip()
        v = [s[i] for i in range(0, len(s))]
        kuro += v.count("#")
        board.append(v)
    memo = copy.deepcopy(board)
    
    for i in range(2 ** h):
        for j in range(h):
            if (i >> j) & 1:
                pattern_h[i][j] = j + 1
    for i in range(2 ** w):
        for j in range(w):
            if (i >> j) & 1:
                pattern_w[i][j] = j + 1
                
    for i in range(2 ** w):
        for j in range(w):
            if pattern_w[i][j] != 0:
                for l in range(h):
                    memo[l][j] = "x"
        for i2 in range(2 ** h):
            for j2 in range(h):
                if pattern_h[i2][j2] == 0:
                    nokori += memo[j2].count("#")
            if k == nokori:
                ans += 1
            nokori = 0
        memo = copy.deepcopy(board)
                        
    print(ans)
                                        
main()

Submission status: Accepted

Solution code:
from collections import Counter
import copy
from itertools import combinations


def A(x):
  return 1000 - x % 1000 if x % 1000 != 0 else 0


def B(n, ss):
  keys_values = Counter(ss)
  orders = ['AC', 'WA', 'TLE', 'RE']
  for order in orders:
    if order in keys_values:
      print("{} x {}".format(order, keys_values[order]))
    else:
      print("{} x {}".format(order, 0))


def _get_num_black(c_list, r_list, h, w, g):
  num_black = 0
  for i in range(h):
    if i in r_list:
      continue
    for j in range(w):
      if j in c_list:
        continue
      num_black += (1 if g[i][j] == '#' else 0)
  return num_black


def C(h, w, k, g):
  num_choice = 0
  for i in range(k + 1):
    for j in range(k - i + 1):
      for c_list in list(combinations(range(w), j)):
        for r_list in list(combinations(range(h), i)):
          if _get_num_black(c_list, r_list, h, w, g) == k:
            num_choice += 1
  return num_choice


def C2(H, W, K, g):
  """All copied."""
  c = []
  for i in range(H):
    c.append([])
    for j in range(W):
      c[i].append(g[i][j])

  ans = 0
  for h in range(H + 1):
    for w in range(W + 1):
      for h2 in combinations(list(range(H)), h):
        for w2 in combinations(list(range(W)), w):
          paint = copy.deepcopy(c)
          for h3 in h2:
            for i in range(W):
              paint[h3][i] = "r"
          for i in range(H):
            for w3 in w2:
              paint[i][w3] = "r"
          count_black = 0
          for i in range(H):
            count_black += paint[i].count("#")
            #print(count_black,paint[i])
          if count_black == K:
            ans += 1

  return ans


def C3(h, w, k, g):
  """
  - Change the calculation of count_black.
  - Change the name of variables.
  - Change the expression of combinations.
  """
  num_choice = 0
  for i in range(h + 1):
    for j in range(w + 1):
      for c_list in list(combinations(range(w), j)):
        for r_list in list(combinations(range(h), i)):
          if _get_num_black(c_list, r_list, h, w, g) == k:
            num_choice += 1
  return num_choice


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


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
import math
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math as M
#####################################
def convert(x):
    if x==0:
        return "0"
    s=""
    while(x):
        r=x%2
        x//=2
        s=str(r)+s
    return s
def binary(m,size):
    s=convert(m)
    s=(size-len(s))*"0"+s
    return s
r,c,k=INPUT()
A=[]
for i in range(r):
    x=input()
    A.append(list(x))

rowblack=[]#all the sum of the rows r
for i in range(r):
    sum=0
    for j in range(c):
        if A[i][j]=="#":
            sum+=1
    rowblack.append(sum)
columnblack=[]
for i in range(c):
    sum=0
    for j in range(r):
        if A[j][i]=="#":
            sum+=1
    columnblack.append(sum)

Rows=[]
for i in range(2**r):
    Rows.append(binary(i,r))
Columns=[]
for j in range(2**c):
    Columns.append(binary(j,c))

ans=0
def count(l,m,A):
    c=0
    for i in range(len(l)):
        if int(l[i])==0:
            for j in range(len(m)):
                if int(m[j])==0:
                    if A[i][j]=="#":
                        c+=1
    #print(c)
    return c

for i in range(len(Rows)):
    for j in range(len(Columns)):
        if count(Rows[i],Columns[j],A)==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
c = []
for i in range(h):
    c.append(input())
ans = 0
# 0から1<<Hまで
for i in range(1<<h):
    # 0から1<<Wまで
    for j in range(1<<w):
        count = 0
        for l in range(h):
            # l行目が選んだ行か調べる
            if not (i>>l)&1:
                for m in range(w):
                    # m列目が選んだ列か調べる
                    if not (j>>m)&1:
                        if c[l][m]=='#':
                            count += 1
        # 黒のマスがKと一致したら1足す
        if count==k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
s = [list(input()) for i in range(h)]
ans = 0
for i in range(2**h-1):
    for j in range(2**w-1):
        cnt = 0
        for x in range(h):
            for y in range(w):
                if (i>>x)&1==0 and (j>>y)&1==0 and s[x][y]=='#':
                    cnt+=1
        if cnt==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
time1 = [0 for _ in range(h)]
time2 = [0 for _ in range(w)]
raw = []
for _ in range(h):
  raw.append(input())
def nex(time):
  l = len(time)
  for i in range(l):
    if time[i] == 0:
      time[i] = 1
      return time
    else:
      time[i] = 0
  else:
    return 'over'
ans = 0
while time1 != 'over':
  while time2 != 'over':
    cnt = 0
    for i in range(h):
      for j in range(w):
        if raw[i][j] == '#' and time1[i] == 0 and time2[j] == 0:
          cnt += 1
    if cnt == k:
      ans += 1
    time2 = nex(time2)
  time1 = nex(time1)
  time2 = [0 for _ in range(w)]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def powerset(iterable):
    for mask in range(2 ** len(iterable)):
        yield {elem for i, elem in enumerate(iterable) if mask >> i & 1}

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    h, w, k = map(int, input().split())
    c = [input() for _ in range(h)]
    ans = 0
    for ys in powerset(range(h)):
        for xs in powerset(range(w)):
            count = 0
            for y in set(range(h)) - ys:
                for x in set(range(w)) - xs:
                    if c[y][x] == "#":
                        count += 1
            if count == k:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
ans = 0
h, w, k = map(int, input().split())
C = [input() for _ in range(h)]
for i in range(2**h):
    for j in range(2**w):
        c = 0
        for y in range(h):
            for x in range(w):
                if C[y][x] == ".":
                    continue
                if i>>y & 1:
                    continue
                if j>>x & 1:
                    continue
                c += 1
        if c == k:
            ans += 1
print(ans)

Submission status: Accepted

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

cells_org = []
CH = [()]
CW = [()]
ans = 0

for i in range(1, H+1) :
  CH = CH + list(itertools.combinations(range(H),i))

for i in range(1, W+1) :
  CW = CW + list(itertools.combinations(range(W),i))

for i in range(H) :  
  cells_org.append(list(str(input())))
  
cells = copy.deepcopy(cells_org)

for i, j in itertools.product(CH, CW):
  for k in list(i) :
    for l in range(W):
      cells[k][l] = "x"
  
  for m in list(j) :
    for n in range(H):
      cells[n][m] = "x"
  
  num = 0
  for x in range(H) :
    num += cells[x].count("#")
   
  if K == num :
    ans += 1

  cells = copy.deepcopy(cells_org)
  
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
C=[[] for i in range(H)]
for i in range(H):
    C[i]=input()
sum_=0
for i in range(H):
    for j in range(W):
        if C[i][j]=="#":
            sum_+=1
r = [i for i in range(H)]
c = [i for i in range(W)]
count=0
for i in range(2 ** H):
    for j in range(2 ** W):
        P=sum_
        a = []
        b = []
        for k in range(H):
            if ((i >> k) & 1):
                a.append(r[k])
        for l in range(W):
            if ((j >> l) & 1):
                b.append(c[l])
        for m in a:
            for n in range(W):
                if C[m][n]=="#":
                    P-=1
        for m in range(H):
            for n in b:
                if C[m][n]=="#":
                    P-=1
        for m in a:
            for n in b:
                if C[m][n]=="#":
                    P+=1
        if P==K:
            count+=1
print(count)

Submission status: Accepted

Solution code:
from collections import Counter
import copy
from itertools import combinations


def A(x):
  return 1000 - x % 1000 if x % 1000 != 0 else 0


def B(n, ss):
  keys_values = Counter(ss)
  orders = ['AC', 'WA', 'TLE', 'RE']
  for order in orders:
    if order in keys_values:
      print("{} x {}".format(order, keys_values[order]))
    else:
      print("{} x {}".format(order, 0))


def _get_num_black(c_list, r_list, h, w, g):
  num_black = 0
  for i in range(h):
    if i in r_list:
      continue
    for j in range(w):
      if j in c_list:
        continue
      num_black += (1 if g[i][j] == '#' else 0)
  return num_black


def C(h, w, k, g):
  num_choice = 0
  for i in range(k + 1):
    for j in range(k - i + 1):
      for c_list in list(combinations(range(w), j)):
        for r_list in list(combinations(range(h), i)):
          if _get_num_black(c_list, r_list, h, w, g) == k:
            num_choice += 1
          # print(h, i, r_list, w, j, c_list, num_black, k)
  return num_choice


def C2(H, W, K, g):
  """All copied."""
  c = []
  for i in range(H):
    c.append([])
    for j in range(W):
      c[i].append(g[i][j])

  ans = 0
  for h in range(H + 1):
    for w in range(W + 1):
      for h2 in combinations(list(range(H)), h):
        for w2 in combinations(list(range(W)), w):
          paint = copy.deepcopy(c)
          for h3 in h2:
            for i in range(W):
              paint[h3][i] = "r"
          for i in range(H):
            for w3 in w2:
              paint[i][w3] = "r"
          count_black = 0
          for i in range(H):
            count_black += paint[i].count("#")
            #print(count_black,paint[i])
          if count_black == K:
            ans += 1

  return ans


def C3(h, w, k, g):
  """
  - Change the calculation of count_black.
  - Change the name of variables.
  """
  num_choice = 0
  for i in range(h + 1):
    for j in range(w + 1):
      for h2 in combinations(list(range(h)), i):
        for w2 in combinations(list(range(w)), j):
          if _get_num_black(w2, h2, h, w, g) == k:
            num_choice += 1
  return num_choice


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


if __name__ == '__main__':
  main()

Submission status: Accepted

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

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

#print(masme)

h_p = []
for h in range(pow(2,H)):
    h_p.append(str(bin(h))[2:].zfill(H))

#print(h_p)

w_p = []
for w in range(pow(2,W)):
    w_p.append(str(bin(w))[2:].zfill(W))

#print(w_p)

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

def delete_row(mas, i):
    ilist = list(i)
    #print(ilist)
    ans = []
    for n in range(H):
        #print(ilist[n])
        if ilist[n] == "0":
            ans.append(mas[n])
            #print(ans)
    return ans

def delete_column(mas, i):
    ilist = list(i)
    ans = []
    for row in mas:
        #print(row)
        tmp_row=[]
        for n in range(W):
            if(ilist[n] == "0"):
                tmp_row.append(row[n])
        #print(tmp_row)
        ans.append(tmp_row)
    return ans


ans_cnt = 0
for h in h_p:
    for w in w_p:
        tmp = delete_row(masme, h)
        tmp2= delete_column(tmp, w)
        cnt = count(tmp2)
        if(cnt == K):
            ans_cnt += 1

print(ans_cnt)

Submission status: Accepted

Solution code:
import copy
H, W, K = map(int, input().split())
li = []
black = 0
result = 0

for i in range(H):
    li.append(list(input()))
    black += li[i].count("#")

for j in range(2 ** H):
    sum_h = 0
    li_a = copy.copy(li)
    for k in range(H):
        if j & (1 << k):
            sum_h += li[k].count("#")
            li_a[k] = ["r"]*len(li_a[k])
    for l in range(2 ** W):
        sum_w = 0
        for m in range(W):
            if (1 << m) & l:
                for n in range(H):
                    if li_a[n][m] == "#": 
                        sum_w += 1
        if sum_h + sum_w == black - K:
            result += 1

print(result)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
c = []
b = 0
ans = 0
count = [[0] * w for i in range(h)]
for i in range(h):
    ci = input()
    c.append(ci)
    b += ci.count("#")
    for j in range(w):
        count[i][j] += (ci[j] == "#")

for i in range(2**(h + w)):
    x, y = [], []
    for j in range(h + w):
        if (i >> j) & 1:
            if j <= h - 1:
                y.append(j)
            else:
                x.append(j - (h - 1) - 1)
    n = 0
    for xi in x:
        n += sum([ci[xi] for ci in count])
    for yi in y:
        n += sum(count[yi])
    for yi in y:
        for xi in x:
            if count[yi][xi]:
                n -= 1
    ans += (b - n == k)
print(ans)

Submission status: Accepted

Solution code:
import copy
h,w,k = map(int, input().split())
lc = []
for _ in range(h):
  ch = [1 if c == "#" else 0 for c in input()]
  lc.append(ch)

ans = 0

for i1 in range(2**h):
  for j1 in range(2**w):
    lc_tmp = copy.deepcopy(lc) 
    for i2 in range(h):
      if (i1 >> i2) &1 == 1:
        for j in range(w):
          lc_tmp[i2][j] = 0

    for j2 in range(w):
      if (j1 >> j2) &1 == 1:
        for i in range(h):
          lc_tmp[i][j2] = 0

    cnt = 0
    for i in range(h):
      cnt += sum(lc_tmp[i])
    ans += 1 if cnt == k else 0
print(ans)