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:
H, W, K = [int(x) for x in input().split()]
c = [input() for x in range(H)]

import itertools
HH = list(range(H))
WW = list(range(W))
ans = 0
totalblack = sum([x.count('#') for x in c])

HHH = [list(itertools.combinations(HH, i)) for i in range(H+1)]
WWW = [list(itertools.combinations(WW, i)) for i in range(W+1)]

for hh in HHH:
    for ww in WWW:
        for h in hh:
            count = 0
            for i in h:
                count += c[i].count('#')
            
            for w in ww:
                ccount = 0
                for j in w:
                    for i, l in enumerate(c):
                        if i in h:
                            continue
                        ccount += l[j] == '#'
                ans += totalblack - (count+ccount) == K

print(ans)

Submission status: Accepted

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

ans = 0

for row_bin in range(2**h):
  for col_bin in range(2**w):
    cnt = 0
    for i in range(h):
      for j in range(w):
        if c[i][j] == '#' and ((row_bin >> i) & 1 and (col_bin >> j) & 1):
          cnt += 1
    if cnt == k:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
h, w, k = list(map(int, input().split()))
a = np.zeros((h, w))
c = 0
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] ==  '#':
            a[i, j] = 1
for i in itertools.product([0, 1], repeat = h):
    for j in itertools.product([0, 1], repeat = w):
        if sum(sum((a.T * i).T * j)) == k:
            c += 1
print(c)

Submission status: Accepted

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

ans = 0
for mask_h in range(2**h):
    for mask_w in range(2**w):
        ctr = 0
        for i in range(h):
            for j in range(w):
                if((mask_h >> i) &1) ==0 and ((mask_w >> j) &1) ==0 \
                    and c[i][j]=='#':
                    ctr +=1
        if ctr == k:
            ans+=1

print(ans)

Submission status: Accepted

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

# 全探索
ans = 0
for i in range(1 << H):
    for j in range(1 << W):
        black = 0
        for h in range(H):
            for w in range(W):
                if i >> h & 1:
                    continue
                if j >> w & 1:
                    continue
                if matrix[h][w] == "#":
                    black += 1
        if black == K:
            ans += 1
print(ans)

Submission status: Accepted

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

c = []
ans = 0
c = [list(input()) for _ in range(h)]
# print(c)
ans = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        cnt = 0
        for m in range(h):
            for n in range(w):
                if ((i >> m) & 1 == 0) and ((j >> n) & 1 == 0):
                    if c[m][n] == '#':
                        cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
li_color = []
b_max = 0
for i in range(H):
    li_color.append(input())
    b_max = b_max + li_color[-1].count("#")

proc_cnt = 0

for w_bin in range(2**W):
    for h_bin in range(2**H):
        b_cnt = 0
        for w in range(W):
            for h in range(H):
                if (h_bin & (1 << h)) or (w_bin & (1 << w)) :
                    if "#" == li_color[h][w] : b_cnt = b_cnt + 1
        if b_max - b_cnt == K:
            proc_cnt = proc_cnt + 1

print(proc_cnt)

Submission status: Accepted

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

count = 0
for row in range(2 ** h):
    for col in range(2 ** w):
        s = 0
        for i in range(h):
            for j in range(w):
                if (row >> i) & 1 == 0 and (col >> j) & 1 == 0 and c[i][j] == "#":
                    s += 1
        if s == k:
            count += 1
print(count)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0

for rowb in product(range(2),repeat = H):
    for colb in product(range(2),repeat = W):
        count = 0
        
        for r in range(H):
            for w in range(W):
                #print(rowb[r],colb[w])
                if c[r][w] == '#' and (rowb[r] and colb[w]):
                    count += 1
                    
        if count == K:
            ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    H,W,K = map(int,input().split())
    grid = []
    for _ in range(H):
        row = input().strip()
        grid.append(row)
    
    ans = 0
    
    for maskH in range((1<<H)-1):
        for maskW in range((1<<W)-1):
            blacks = 0
            for i in range(H):
                for j in range(W):
                    if (maskH >> i & 1)==0 and (maskW >> j & 1)==0 and grid[i][j] == '#':
                        blacks += 1
            if blacks == K:
                ans += 1
    print(ans)
    
    
main()

Submission status: Accepted

Solution code:
import itertools

h, w, k = map(int, input().split())
lst = []
for _ in range(h):
  lst.append(input())
#
data = [0, 1]
all_lists = list(itertools.product(data, repeat=h+w))
#print(all_lists)
count = 0
for each in all_lists:
  #print(each)
  x_list = []
  y_list = []
  number = 0
  for i in range(h + w):
    if each[i] == 1:
      if i < h:
        x_list.append(i)
      elif i < h + w:
        y_list.append(i - h)
  #print(x_list)
  #print(y_list)
  for i in range(h):
    if i not in x_list:
      lst_h = lst[i]
      for j in range(w):
        if j not in y_list:
          lst_hw = lst_h[j]
          if lst_hw == '#':
            number += 1
  #print(number)
  if number == k:
    count += 1
print(count)

Submission status: Accepted

Solution code:
import numpy as np

H, W, K = [int(i) for i in input().split()]
A = np.zeros([H, W], dtype=bool)
for i in range(H):
    A[i] = np.array([False if i=="." else True for i in input()])

T = A.sum()
T_row = A.sum(1)
T_col = A.sum(0)

def calc(I, J):
    return T - T_row[I].sum() - T_col[J].sum() + A[I][:,J].sum()

def repr(i, W):
    s = np.binary_repr(i, width=W)[::-1]
    return [i for i, j in enumerate(s) if j == "1"]

count = 0
for i in range(2**H-1):
    for j in range(2**W-1):
        row = repr(i, H)
        col = repr(j, W)
        if calc(row, col) == K:
            count += 1

print(count)

Submission status: Accepted

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

ans=0

M=[]

yoko=[0 for i in range(H)]
tate=[0 for i in range(W)]

for i in range(H):
    l=list(input())
    cnt=0
    for j in range(W):
        if l[j]=="#":
            cnt+=1
    M.append(l)
    yoko[i]=cnt

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

B=sum(yoko)

for i in range(2**H):
    for j in range(2**W):
        num=B
        y=[]
        t=[]
        for a in range(H):
            if i>>a&1:
                num-=yoko[a]
                y.append(a)
                
        for b in range(W):
            if j>>b&1:
                num-=tate[b]
                t.append(b)
        
        for a in range(len(y)):
            for b in range(len(t)):
                if M[y[a]][t[b]]=="#":
                    num+=1
        if num==K:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
import copy
H, W, K=list(map(int,input().split()))
def conv(m):
    if m=='#':
        return 1
    else:
        return 0
c=[]
for i in range(H):
    c.append([conv(s) for s in input()])
items = [(0,i) for i in range(H)]+[(1,j) for j in range(W)]
subsets=[]
for i in range(len(items) + 1):
    for e in combinations(items, i):
        subsets.append(e)
count=0
for e in subsets:
    M=copy.deepcopy(c)
    for p in e:
        if p[0]==0:
            for j in range(W):
                M[p[1]][j]=0
        else:
            for i in range(H):
                M[i][p[1]]=0
    if sum([sum(u) for u in M])==K:
        count+=1
print(count)

Submission status: Accepted

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

    counter = 0
    for mask_row in range(int(1 << H) - 1):
        for mask_col in range(int(1 << W) - 1):
            black = 0
            for x in range(H):
                if f'{mask_row:b}'.zfill(H)[x] == '1':
                    continue
                for y in range(W):
                    if f'{mask_col:b}'.zfill(W)[y] == '1':
                        continue
                    if c[x][y] == '#':
                        black += 1
            if black == K:
                counter += 1
    print(counter)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# abc173_c.py
# https://atcoder.jp/contests/abc173/tasks/abc173_c
# C - H and V /
# 実行時間制限: 1 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# H行 W 列に並ぶマスからなるマス目があります。
# 上から i 行目、左から j 列目 (1≤i≤H,1≤j≤W) のマスの色は文字 ci,j として与えられ、ci,jが . のとき白、# のとき黒です。

# 次の操作を行うことを考えます。
# 行を何行か選び (0行でもよい)、列を何列か選ぶ (0列でもよい)。
# そして、選んだ行に含まれるマスと、選んだ列に含まれるマスをすべて赤く塗る。

# 正の整数 Kが与えられます。操作後に黒いマスがちょうど K個残るような行と列の選び方は何通りでしょうか。
# ここで、二つの選び方は、一方においてのみ選ばれる行または列が存在するときに異なるとみなされます。

# 制約
#     1≤H,W≤6
#     1≤K≤HW
#     ci,jは . または #

# 入力
# 入力は以下の形式で標準入力から与えられる。
# H W K
# c1,1c1,2...c1,W
# c2,1c2,2...c2,W
# :
# cH,1cH,2...cH,W

# 出力
# 条件を満たす行と列の選び方の個数を表す整数を出力せよ。

# 入力例 1
# 2 3 2
# ..#
# ###

# 出力例 1
# 5

# 以下の 5通りの選び方が条件を満たします。
#     1行目、1列目
#     1行目、2列目
#     1行目、3列目
#     1列目、2列目
#     3列目

# 入力例 2
# 2 3 4
# ..#
# ###

# 出力例 2
# 1

# 何も選ばないという 1通りの選び方が条件を満たします。

# 入力例 3
# 2 2 3
# ##
# ##

# 出力例 3
# 0

# 入力例 4
# 6 6 8
# ..##..
# .#..#.
# #....#
# ######
# #....#
# #....#

# 出力例 4
# 208


# 解答
def abc173_c(lines):
    H, W, K = map(int, lines[0].split(' '))
    pattern_h = get_pattern(H)
    pattern_w = get_pattern(W)
    answers = 0
    for h in pattern_h:
        for w in pattern_w:
            tmp = list()
            for i in range(1, len(lines)):
                tmp.append(lines[i])
            # 行単位の指定時は行全体を指定
            for n_row in range(H):
                if h[n_row] == '1':
                    tmp[n_row] = '*' * W
            for n_col in range(W):
                if w[n_col] == '1':
                    for n_row in range(H):
                        tmp[n_row] = replace_string_xy(tmp[n_row], n_col, '*')
            if count_char_from_lines(tmp, '#') == K:
                answers += 1
    return [answers]


# 指定位置の文字を置き換える
def replace_string_xy(line, pos, char):
    ret = ''
    for i, x in enumerate(line):
        if i == pos:
            ret += char
        else:
            ret += line[i]
    return ret


# 文字を数える
def count_char_from_line(line, char):
    n_char = 0
    for i in line:
        if i == char:
            n_char += 1
    return n_char


# 文字を数える
def count_char_from_lines(lines, char):
    n_char = 0
    for line in lines:
        n_char += count_char_from_line(line, char)
    return n_char


# パターン取得
def get_pattern(n):
    _, patter = get_pattern_internal(n-1, ['0', '1'])
    return patter


# パターン取得(再起処理内部)
def get_pattern_internal(n, lst):
    if n == 0:
        return 0, lst
    else:
        ret = list()
        for item in lst:
            ret.append('0' + item)
            ret.append('1' + item)
        m, ret = get_pattern_internal(n-1, ret)
        return m, ret


# 引数を取得
def get_input_lines_1stline1stblock_as_n_lines():
    lines = list()
    lines.append(input())
    H, W, K = map(int, lines[0].split(' '))
    for _ in range(H):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['2 3 2', '..#', '###']
        lines_export = [5]
    elif pattern == 2:
        lines_input = ['2 3 4', '..#', '###']
        lines_export = [1]
    elif pattern == 3:
        lines_input = ['2 2 3', '##', '##']
        lines_export = [0]
    elif pattern == 4:
        lines_input = ['6 6 8', '..##..', '.#..#.', '#....#', '######', '#....#', '#....#']
        lines_export = [208]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines_1stline1stblock_as_n_lines()
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = abc173_c(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import copy
# スペース区切りの整数の入力
H, W, K = map(int, input().split())
table = []
for i in range(H):
    table.append(list(input()))
# print(table)
ans_cnt = 0
for deh in range(2 ** H):
    htable = copy.deepcopy(table)
    # print("deepcopy", htable)
    for h in range(H):
        if deh & (1 << h):
            for ch in range(W):
                htable[h][ch] = "."
    for dew in range(2 ** W):
        wtable = copy.deepcopy(htable)
        for w in range(W):
            if dew & (1 << w):
                for cw in range(H):
                    wtable[cw][w] = "."
        cnt = 0
        for cnth in range(H):
            for cntw in range(W):
                if wtable[cnth][cntw] == "#":
                    cnt = cnt + 1
        if cnt == K:
            ans_cnt = ans_cnt + 1
        # print(bin(deh), bin(dew))
        # print(cnt, wtable)
print(ans_cnt)

Submission status: Accepted

Solution code:
def main():
    H, W, K = map(int, input().split())
    c=[input() for i in range(H)]
    c=list(map(list,c))
    ans = 0
    #print(c)
    number = 0
    for i in range(H):
        for j in range(W):
            if c[i][j] == '#':
                number += 1
    #print(number)
    for i in range(2**H):
        for j in range(2**W):
            count = 0
            for l in range(H):
                for m in range(W):
                    #print(l,m)
                    if not i>>l&1 and not j>>m&1 and c[l][m] == "#":
                        #print(i,j,l,m)
                        count+=1

            if count==K:
                #print(i,j)
                ans+=1
    print(ans)

main()

Submission status: Accepted

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

ans = 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 cList[i][j] == '#':
          black += 1
    if black == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
ans = 0
# H列W行の入力
# K個だけ#を残す
C = [list(input()) for _ in range(H)]
# bit全探索
for i in range(2**H):
    for j in range(2**W):
        cnt = 0
        for h in range(H):
            for w in range(W):
                if 2**h & i > 0 and 2**w & j > 0:
                    if C[h][w] == "#":
                        cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K=map(int,input().split())
x=[input() for i in range(H)]
x=list(map(list,x))
ans=0
for i in range(2**H):
  for j in range(2**W):
    count=0
    for l in range(H):
      for m in range(W):
        if i>>l&1 and j>>m&1 and x[l][m]=="#":
          count+=1
    if count==K:
      ans+=1
print(ans)

Submission status: Accepted

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

cols = ([input() for i in range(h)])

ans = 0

for col_mask in range(1 << (h + 1) - 1):
    for row_mask in range(1 << (w + 1) - 1):
        black = 0
        for i in range(h):
            for j in range(w):
                if ((1 << i) & col_mask) == 0 and ((1 << j) & row_mask) == 0 and cols[i][j] == '#':
                        black = black + 1
        if black == k:
            ans = ans + 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product as pd

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

ans = 0
for i, j in pd(range(1 << h), range(1 << w)):
    temp = 0
    for x, y in pd(range(h), range(w)):
        if 1 << x & i and 1 << y & j:
            if c[x][y] == "#":
                temp += 1
    ans += temp == k
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy as dc

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

ans = 0
for h_i in range(2 ** h):
    temp = dc(c)
    for h_j in range(h):
        if (h_i >> h_j) & 1:
            temp[h_j] = ["+"] * w
    for w_i in range(2 ** w):
        temp2 = dc(temp)
        for w_j in range(w):
            if (w_i >> w_j) & 1:
                for i in range(h):
                    temp2[i][w_j] = "+"
        temp_ans = 0
        for i in range(h):
            temp_ans = temp_ans + "".join(temp2[i]).count("#")
        if temp_ans == k:
            ans = ans + 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import copy


# 引数が一つだけのやつ
# n = int(input())
# 引数が複数あるやつ（全部数字）
target_1 = [int(x) for x in input().split()]

H = target_1[0]
W = target_1[1]
K = target_1[2]

# 引数が複数あるやつ（そうじゃないの）
# target = [int(x) for x in input().split()]

# number = int(input())
# 複数行を受け取って処理するやつ
target = [list(input()) for i in range(H)]

# 関数
def count_sharp(target):
    return sum([x.count("#") for x in target])


def bin_code(value, keta):
    return list(("{:0" + str(keta) + "b}").format(value))


# 初期
result = 0

for i in range(2 ** H):
    for j in range(2 ** W):
        bin_i = bin_code(i, H)
        bin_j = bin_code(j, W)
        tmp = copy.deepcopy(target)
        # 色塗り
        for idx_i, ik in enumerate(bin_i):
            if ik == "1":
                tmp[idx_i] = [0] * W
            for idx_j, jk in enumerate(bin_j):
                if jk == "1":
                    tmp[idx_i][idx_j] = 0

        # カウント
        if count_sharp(tmp) == K:
            result += 1
            # print(tmp)


# 出力
print(result)

Submission status: Accepted

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

import copy

ar = [[0 for _ in range(w)] for _ in range(h)]


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

#print(ar)
d = {}
for i in range(h):
    for j in range(w):
        d[(i+1,j+1)] = ar[i][j]

#print(d)
sm = 0
for i in d.values():
    if(i == "#"):
        sm += 1

gl = sm - k
#print("gl",gl)

ans = 0
def ch_red(x):
    d_tmp = copy.deepcopy(d)
    #print(d_tmp)
    cnt = 0
    x_ar_bin = [0 for _ in range(h+w)]
    v = h+w
    for i in range(h+w):
        x_ar_bin[i] = int(bin(x >> i),2)%2
    
    #print(x_ar_bin)

    for i in range(h):
        if(x_ar_bin[i] == 0):
            continue
        else:
            for j in range(w):
                key = (i+1,j+1)
                if(d_tmp[key] == "#"):
                    d_tmp[key] = "$"
                    cnt += 1
    
    for i in range(h,h+w):
        if(x_ar_bin[i] == 0):
            continue
        else:
            for j in range(h):
                key = (j+1,i+1-h)
                if(d_tmp[key] == "#"):
                    d_tmp[key] = "$"
                    cnt += 1
    
    
    if(cnt == gl):
        return 1
    else:
        return 0

    #print(cnt)

mx = 2**(h+w)

#print(mx)
for i in range(mx):
    ans += ch_red(i)

print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
C = [list(input()) for _ in range(h)]
cnt = 0
for I in range(2 ** h):
    I_lst = []
    for i in range(h):
        if (not((I >> i) & 1)):
            I_lst.append(i)
    for J in range(2 ** w):
        J_lst = []
        sum_black = 0
        for j in range(w):
            if (not((J >> j) & 1)):
                J_lst.append(j)
        # print(I, I_lst, J_lst)
        for I_nokori in I_lst:
            for J_nokori in J_lst:
                if C[I_nokori][J_nokori] == '#':
                    sum_black += 1
        if sum_black == k:
            cnt += 1
            # print('aaaaa', I, I_lst, J_lst)

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
h,w,k = map(int, input().split())
c = np.array([list(input()) for _ in range(h)])

p = itertools.product([True,False],repeat = h+w)
ans = 0
for i in p:
    c_cut = c[np.ix_(i[:h],i[h:])]
    if np.count_nonzero(c_cut == '#') == k:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
H, W, K = map(int, input().split())
C = []
for i in range(H):
    C.append(list(input()))
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 h in range(H):
            for w in range(W):
                if tmp[h][w] == "#":
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:

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

ans = 0
for i in range((1 << H)):
    for j in range((1 << W)):
        black = 0
        for k in range(H):
            for l in range(W):
                if ((i >> k) & 1) == 0 and ((j >> l) & 1) == 0 and C[k][l] == '#':
                    black += 1
        if black == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
def getCombList(xList):
  N = len(xList)
  result = []
  for n in range(1,N+1):
    for conb in itertools.combinations(xList, n):
      result.append(list(conb)) #タプルをリスト型に変換
  #print(result)
  return result

import numpy as np
L1 = input()
H, W, K = map(int, L1.split(" "))
mat = np.zeros([H,W], dtype="int32")
for i in range(H):
  Li = input()
  for j, s in enumerate(Li):
    if s == "#":
      mat[i,j] = 1

if np.sum(np.sum(mat)) < K:
  print(0)
else:
  if np.sum(np.sum(mat)) == K:
    c = 1
  else:
    c = 0
  matp = mat.copy()
  HList = list(range(H))
  WList = list(range(W))
  HcombList = getCombList(HList)
  WcombList = getCombList(WList)
  for Hcomb in HcombList:
    for Wcomb in WcombList:
      matp[Hcomb, :] = 0
      matp[:, Wcomb] = 0
      if np.sum(np.sum(matp)) == K:
        c = c + 1
      matp = mat.copy()
      
  for Hcomb in HcombList:
    matp[Hcomb, :] = 0
    if np.sum(np.sum(matp)) == K:
      c = c + 1
    matp = mat.copy()

  for Wcomb in WcombList:
    matp[:, Wcomb] = 0
    if np.sum(np.sum(matp)) == K:
      c = c + 1
    matp = mat.copy()

  print(c)

Submission status: Accepted

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

ans = 0
for row_bit in product(range(2), repeat=H):
    for col_bit in product(range(2), repeat=W):
        cnt = 0
        for row in range(H):
            for col in range(W):
                if C[row][col] == "#" and (not (row_bit[row] or col_bit[col])):
                    cnt += 1
        
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

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

ans = 0
hw_bits = product([False, True], repeat=H+W)
for hw_ in hw_bits:
    h_ = list(hw_[:H])
    w_ = list(hw_[H:])
    if sum(list(h_))!=0 and sum(list(w_))!=0:
        x = np.sum(C[h_].T[w_] == '#')
        if x == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools


def resolve(in_):
    h, w, k = map(int, next(in_).split())
    c = [row.strip() for row in in_]
    # for i in range(h):
    #     print(c[i].decode())

    ans = 0
    black_char = ord(b'#')
    red_mask = itertools.product(
        itertools.product((True, False), repeat=h),
        itertools.product((True, False), repeat=w),
    )
    for not_red_row, not_red_col in red_mask:
        black_n = 0
        # print(not_red_row, not_red_col)
        for i, j in itertools.product(range(h), range(w)):
            # print(f'  {i=} {j=}')
            if c[i][j] == black_char and not_red_row[i] and not_red_col[j]:
                black_n += 1
                if black_n > k:
                    break
        else:
            if black_n == k:
                ans += 1

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#/usr/bin/python

def solve():
    h, w, k = map(int, input().split())
    c = [list(input()) for i in range(h)]
    ans = 0
    for ii in range(1<<h):
        for jj in range(1<<w):
            cnt = 0
            for i in range(h):
                for j in range(w):
                    if ii>>i & 1:
                        continue
                    if jj>>j & 1:
                        continue
                    if c[i][j] == '#':
                        cnt += 1
            if cnt == k:
                ans += 1
    return ans

print(solve())

Submission status: Accepted

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

c = [[0 for j in range(w)] for i in range(h)]

for i in range(h):
    line = input()
    for j in range(w):
        c[i][j] = line[j]

ans = 0

for il in range(1<<h):
    for jl in range(1<<w):
        count = 0
        for i in range(h):
            for j in range(w):
                if il>>i&1: continue
                if jl>>j&1: continue
                if c[i][j] == '#': count += 1
        if count == k: ans += 1

print(ans)

Submission status: Accepted

Solution code:
def prov(maskHor, maskVert):
    kol = 0
    for i in range(h):
        for j in range(v):
            if m[i][j] == '#':
                b = 0
                for hor in maskHor:
                    if hor == i:
                        b = 1
                for vert in maskVert:
                    if vert == j:
                        b = 1
                if b == 0:
                    kol += 1
    #tmh = maskHor
    #for i in range(len(tmh)):
    #    tmh[i] = str(tmh[i])
    #tmv = maskVert
    #for i in range(len(tmv)):
    #    tmv[i] = str(tmv[i])
    #print('!', ' '.join(tmh), '!', ' '.join(tmv), '!', kol)
    if kol == k:
        global ans
        ans += 1


def genMaskVert(pos, mask, maskHor):
    if (pos == v):
        prov(maskHor, mask)
        #if not len(mask) == 0:
        #    mask.pop()
        return
    else:
        genMaskVert(pos + 1, mask, maskHor)
        temp = mask
        temp.append(pos)
        genMaskVert(pos + 1, temp, maskHor)
        if not len(mask) == 0:
            mask.pop()
        return


def genMaskHor(pos, mask):
    if (pos == h):
        genMaskVert(0, [], mask)
        #if not len(mask) == 0:
        #    mask.pop()
        return
    else:
        genMaskHor(pos + 1, mask)
        mask.append(pos)
        genMaskHor(pos + 1, mask)
        if not len(mask) == 0:
            mask.pop()
        return


h, v, k = input().split()
h = int(h)
v = int(v)
k = int(k)
ans = 0
m = []
for i in range(h):
    m.append(input())
genMaskHor(0, [])
print(ans)

Submission status: Accepted

Solution code:
import copy
h,w,k=map(int,input().split())
L=[list(input()) for i in range(h)]
r=0
for i in range(1<<h):
    for j in range(1<<w):
        T=copy.deepcopy(L)
        for l in range(h):
            if i & (1<<l):
                for a in range(w):
                    T[l][a]='.'
        for m in range(w):
            if j & (1<<m):
                for b in range(h):
                    T[b][m]='.'
        c=0
        for d in range(h):
            for e in range(w):
                if T[d][e]=='#':
                    c+=1
        if c==k:
            r+=1
print(r)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
c = [input() for _ in range(H)]
ybla = [0]*H
xbla = [0]*W
all_black = 0
for i in range(H):
    all_black += c[i].count('#')
    ybla[i] += c[i].count('#')
    for j in range(W):
        if c[i][j] == '#':
            xbla[j] += 1

# print(ybla, xbla)
ans = 0
for i in range(2**H):
    y = []
    total1 = 0
    for j in range(H):
        if (i >> j) & 1:
            y.append(j)
            total1 += ybla[j]
    # print(y, total)
    for k in range(2**W):
        x = []
        total2 = 0
        for l in range(W):
            if (k >> l) & 1:
                # print(bin(k), l)
                x.append(l)
                total2 += xbla[l]
        total = total1 + total2
        if len(y) and len(x):
            for yy in y:
                for xx in x:
                    if c[yy][xx] == '#':
                        total -= 1
        # print(y, x, total, total1, total2)
    
        if all_black == K + total:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

columns = [i for i in range(w)]
rows = [i for i in range(h)]

ans = 0
for c in range(w+1):
    for r in range(h+1):
        for column in combinations(columns, c):
            for row in combinations(rows, r):
                cnt = 0
                for x in range(w):
                    for y in range(h):
                        if not (x in column or y in row):
                            if C[y][x] == '#':
                                cnt += 1
                if cnt == k:
                    ans += 1

print(ans)