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 numpy as np
H, W, K = map(int, input().split())
C = [[w=='#' for w in input()] for _ in range(H)]

def count(h_slice, w_slice):
    cnt = 0
    for i in range(H):
        if h_slice[i] == 0:
            continue
        for j in range(W):
            if w_slice[j] == 0:
                continue
            cnt += C[i][j]
    return cnt

ans = 0
for h_slice in itertools.product([0, 1], repeat=H):
    h_slice = np.array(h_slice).astype(bool)
    for w_slice in itertools.product([0, 1], repeat=W):
        w_slice = np.array(w_slice).astype(bool)
        ans += count(h_slice, w_slice) == K
print(ans)

Submission status: Accepted

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

row_count = [c_row.count("#") for c_row in c_list]
column_count = [[c_low[i] for c_low in c_list].count("#") for i in range(w)]
all_count = sum(row_count)

def bit_tansaku(num):
    list_num = list(range(num))
    list_num_all = []
    for i in range(2**len(list_num)):
        list_temp = []
        for j in range(len(list_num)):
            if (i >> j) &1 == 1:
                list_temp.append(list_num[j])
        list_num_all.append(list_temp)
    return list_num_all

def reducible_num(row_list,column_list,row_count,column_count,c_list):
    count = sum([row_count[i] for i in row_list])+sum([column_count[i] for i in column_list])
    for i in row_list:
        for j in column_list:
            if c_list[i][j] == "#":
                count -= 1
    return count
list_h_all = bit_tansaku(h)
list_w_all = bit_tansaku(w)

count = 0
for list_h_i in list_h_all:
    for list_w_j in list_w_all:
        if all_count - reducible_num(list_h_i,list_w_j,row_count,column_count,c_list)==k:
            count+=1
print(count)

Submission status: Accepted

Solution code:
from itertools import combinations
import copy
H,W,K = map(int,input().split())
cs = [list(input()) for i in range(H)]
HC = [i for i in range(H)]
WC = [i for i in range(W)]
fBlackCount=0
for i in range(H):
  fBlackCount += cs[i].count('#')
cBlackCount=fBlackCount
c=0
for i in range(H+1):
  for j in range(W+1):
    for selectRows in combinations(HC,i):
      for selectCols in combinations(WC,j):
        #print(selectRows)
        #print(selectCols)
        cBlackCount=fBlackCount
        for m in range(H):
          for n in range(W):
            if cs[m][n] == '#':
              if m in selectRows or n in selectCols:
                cBlackCount-=1
        if cBlackCount == K:
          #print(i)
          #print(j)
          #print(selectRows)
          c+=1
print(c)

Submission status: Accepted

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

def black_cnt(List):
  cnt = 0
  for c in List:
    cnt += c.count("#")
  return cnt

ans = 0

for i in range(2 ** (H+W)):
  cc = copy.deepcopy(cs)
  cnt = 0
  # print(bin(i))
  for j in range(H+W):
    if ((i >> j) & 1):
      if j < H:
        cc[j] = ["@"]*W
      else:
        for h in range(H):
          cc[h][j-H] = "@"
  # print(*cc)
  if black_cnt(cc) == K:
    # print("OK")
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
import copy

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


def count(target_list: list, target_str: str):
    cnt = 0
    for target in target_list:
        cnt += target.count(target_str)
    return cnt


# 実装を行う関数
def resolve(test_def_name=""):
    h, w, k = map(int, input().split())
    data = [list(list(input())) for i in range(h)]

    ans = 0
    for i in range(1 << (h + w)):
        table = copy.deepcopy(data)
        for j in range(h):
            if i & 1 << j:
                table[j] = ["." for aaaa in range(w)]

        for jj in range(w):
            target = j + jj + 1
            if i & 1 << target:
                for aaaa in table:
                    aaaa[jj] = "."

        if count(table, "#") == k:
            ans += 1

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """2 3 2
..#
###"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """2 3 4
..#
###"""
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """2 2 3
##
##"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """6 6 8
..##..
.#..#.
#....#
######
#....#
#....#"""
        output = """208"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

    h_bin = 1 << h
    w_bin = 1 << w

    ans = 0
    for i_h in range(h_bin):
        for i_w in range(w_bin):
            now_count = 0

            for i_line in range(h):
                now_line = 1 << i_line
                if i_h & now_line == 0:
                    continue

                for j_raw in range(w):
                    now_raw = 1 << j_raw
                    if i_w & now_raw == 0:
                        continue

                    if c[i_line][j_raw] == '#':
                        now_count += 1
                    
                    if now_count > k:
                        break

            if now_count == k:
                ans += 1

    print(ans)
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Accepted

Solution code:
import numpy as np


# read
h, w, K = map(int, input().split())
data = []
for i in range(h):
    data.append(list(input()))
data = np.array(data)

# count
ans = 0
for i in range(2**h):
    h_indexs = []
    for k in range(h):
        if (i >> k) & 1:
            h_indexs.append(k)
    
    for j in range(2**w):
        w_indexs = []
        for k in range(w):
            if (j >> k) & 1:
                w_indexs.append(k)
        d = np.copy(data)
        # coloring
        for h_index in h_indexs:
            d[h_index, :] = 'r'
        for w_index in w_indexs:
            d[:, w_index] = 'r'
        num = (d == '#').sum()
        if num == K:
            ans += 1
        
print(ans)

Submission status: Accepted

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

cells = []
rowBlack = []
columnBlack = [0] * w
for _ in range(h):
    ipt = input()
    rowBlack.append(ipt.count("#"))
    cells.append(ipt)

for cell in cells:
    for i in range(w):
        if cell[i] == "#":
            columnBlack[i] += 1

total = sum(columnBlack)
cnt = 0
for hbit in range(2**h):
    for wbit in range(2**w):
        decBlack = 0

        hlis = []
        for he in range(h):
            if not hbit >> he & 1: continue
            decBlack += rowBlack[he]
            hlis.append(he)

        for we in range(w):
            if not wbit >> we & 1: continue
            decBlack += columnBlack[we]
            for he in hlis:
                if cells[he][we] == "#":
                    decBlack -= 1

        if total - decBlack == k:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
moto=0
l=[]
for i in range(h):
  ll=input()
  l.append(ll)
  moto+=ll.count('#')
sa=moto-k

ans=0
import itertools
for p in itertools.product([0,1],repeat=h):
  for q in itertools.product([0,1],repeat=w):
    cnt=0
    for hh in range(h):
      if p[hh]==1:
        cnt+=l[hh].count('#')
    for ww in range(w):
      if q[ww]==1:
        for ll in l:
          if ll[ww]=='#':
            cnt+=1
    for hh in range(h):
      for ww in range(w):
        if p[hh]==q[ww]==1 and l[hh][ww]=='#':
          cnt-=1
    if cnt==sa:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
# 黒マスの数をカウントして返す
def count(il,jl):
    cnt = 0
    for k in range(h):
        for l in range(w):
            if il[k] == 0 and jl[l] == 0:
                if c[k][l] == "#":
                    cnt += 1
    return cnt


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):
    il = [0] * h
    for ii in range(h):
        if i>>ii & 1:
            il[ii] = 1
    for j in range(2**w):
        jl = [0] * w
        for jj in range(w):
            if j>>jj & 1:
                jl[jj] = 1
        # print(il)
        # print(jl)
        # print("-------")
        if k == count(il, jl):
            ans += 1

print(ans)

Submission status: Accepted

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

table = []

for _ in range(H):
    s = input()
    inst_s = []
    for x in s:
        inst_s.append(x)
    table.append(inst_s)

#print(table)

#Hで消すところの組み合わせ
del_H = []
l = [i for i in range(H)]
for x in range(1,H+1):
	for v in itertools.combinations(l,x):
		del_H.append(v)

#W方向で消すところ
del_W = []
l = [i for i in range(W)]
for x in range(1,W+1):
	for v in itertools.combinations(l,x):
		del_W.append(v)

"""
print(del_H)
print(del_W)
"""
ans = 0

#まずは使うところタプルの組み合わせ
for tuple_h in del_H:
    for tuple_w in del_W:
        count = 0
        for h in tuple_h:
            for w in tuple_w:
                count += table[h][w].count("#")
        
        if count == K:
            ans += 1

print(ans)

Submission status: Accepted

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

H = 2 ** H - 1
W = 2 ** W - 1

for I in range(H+1):
    for J in range(W+1):
        count = 0
        for i, row in enumerate(C):
            for j, elem in enumerate(row):
                if 2 ** i & I and 2 ** j & J and elem == '#':
                    count += 1
        if count == K:
            Count += 1

print(Count)

Submission status: Accepted

Solution code:
import itertools
import copy


def nuri(a, b, _):
    # 行の塗り替え
    if len(a)!=0:
        for aa in a:
            for i in range(w):
                _[aa][i] = 0
    # 列の塗り替え
    if len(b)!=0:
        for bb in b:
            for i in range(h):
                _[i][bb] = 0
    return sum(map(sum, _))


h, w, k = map(int, input().split())
c = []  # 0:白, 1:黒
for i in range(h):
    s = input()
    _ = []
    for j in range(w):
        if s[j] == ".":
            _.append(0)
        else:
            _.append(1)
    c.append(_)

iterh = [i for i in range(h)]
iterw = [i for i in range(w)]

count = 0
for i in range(h):
    lih = itertools.combinations(iterh, i)
    for lih_ in lih:
        for j in range(w):
            liw = itertools.combinations(iterw, j)
            for liw_ in liw:
                _ = copy.deepcopy(c)
                if nuri(lih_, liw_, _) == k:
                    count += 1
print(count)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
l = []
ans = 0
for i in range(H):
    l.append(input())
Hblack = []
Wblack = []
for i in range(W):
    Hblack.append(0)
    for j in range(H):
        if l[j][i] == '#':
            Hblack[-1] += 1
for i in range(H):
    Wblack.append(0)
    for j in range(W):
        if l[i][j] == '#':
            Wblack[-1] += 1
ALL = sum(Hblack)
#print(Hblack)
for i in range(2 ** H):
    t1 = i
    Hl = [False] * H
    for j in range(H):
        if t1 & 1:
            Hl[j] = True
        t1 = t1 >> 1
    #print(Hl)
    T = ALL
    for j in range(H):
        if Hl[j]:
            T -= Wblack[j]
    #print(T)
    for j in range(2 ** W):
        T2 = T
        t2 = j
        for k in range(W):
            if t2 & 1:
                T2 -= Hblack[k]
                for m in range(H):
                    if Hl[m] and l[m][k] == '#':
                        T2 += 1
            t2 = t2 >> 1
        #print(T2)
        if T2 == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
h, w, k = map(int, input().split())
C = [['']*w for _ in range(h)]
for i in range(h):
    C[i] = list(input())

ans = 0
for i in range(2**h-1):
    for j in range(2**w-1):
        _C = deepcopy(C)
        H = bin(i)[2:].zfill(h)
        W = bin(j)[2:].zfill(w)
        for _k,_h in enumerate(H):
            if _h == '1':
                for _w in range(w):
                    _C[_k][_w] = 'x'
        for _k,_w in enumerate(W):
            if _w == '1':
                for _h in range(h):
                    _C[_h][_k] = 'x'
        tmp = []
        _ = [tmp.extend(c) for c in _C]
        if tmp.count('#')==k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    h, w, K = i_map()
    str_list = s_row_list(h)

    count = 0

    for h_bit in list(product([0,1], repeat=h)):
        for w_bit in list(product([0,1], repeat=w)):
            copy_list = deepcopy(str_list)

            for i in range(h):
                if h_bit[i] == 0:
                    continue
                copy_list[i][0] = '.' * w

            for i in range(w):
                if w_bit[i] == 0:
                    continue
                for k in range(h):
                    tmp = ''
                    for l in range(w):
                        if l == i:
                            tmp += '.'
                        else:
                            tmp += copy_list[k][0][l]
                    copy_list[k][0] = tmp
            tmp_count = 0
            for aaa in range(h):
                for bbb in range(w):
                    if copy_list[aaa][0][bbb] == '.':
                        continue
                    tmp_count += 1
            if tmp_count == K:
                count += 1

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

Submission status: Accepted

Solution code:
# 2020/07/05
# AtCoder Beginner Contest 173 - C

import copy

def dfs(hi, wi, wc, wh, ww, wk, d):
    if d == 0 and wi >= ww:
        d = 1
    elif d == 1 and hi >= wh:
        d = 2

    if d == 0:
        newc = copy.deepcopy(wc)
        for i in range(wh):
            newc[i][wi] = '.'
        rval = dfs(hi, wi+1, wc, wh, ww, wk, d)
        rval += dfs(hi, wi+1, newc, wh, ww, wk, d)
        return rval
    elif d == 1:
        newc = copy.deepcopy(wc)
        for i in range(ww):
            newc[hi][i] = '.'
        rval = dfs(hi+1, wi, wc, wh, ww, wk, d)
        rval += dfs(hi+1, wi, newc, wh, ww, wk, d)
        return rval
    else:
        cnt = 0
        for i in range(wh):
            for j in range(ww):
                if wc[i][j] == '#':
                    cnt = cnt + 1
        if cnt == wk:
            return 1
        else:
            return 0

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

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

ans = dfs(0, 0, c, h, w, k, 0)

# Output
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
c = [input() for i in range(H)]
ans = 0
for hn in range(2**H):
    hp = list("{:0>{}b}".format(hn,H))
    for wn in range(2**W):
        wp = list("{:0>{}b}".format(wn,W))
        kuronum = 0
        for hc in range(H):
            if hp[hc] == "1":
                continue
            for wc in range(W):
                if wp[wc] == "0" and c[hc][wc] == "#":
                    kuronum += 1
        if kuronum == 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(input())
D = copy.deepcopy(C)
count = 0
for j in range(2**(H+W)):
    a = str(bin(j))[2:]
    a = '0'*(H+W-len(a))+a
    for k in range(H):
        if a[k] == '0':
            C[k] = 'r'*W
    for l in range(W):
        if a[H+l] == '0':
            for q in range(H):
                C[q] = C[q][:l] + 'r' + C[q][l+1:]
    b = 0
    for t in range(H):
        b += C[t].count('#')
    if b == K:
        count += 1
    C = copy.deepcopy(D)
print(count)

Submission status: Accepted

Solution code:
import copy

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

ans = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        cnt = 0
        x = copy.deepcopy(ls)
        for g in range(h):
            for l in range(w):
                if (i >> g) & 1:
                    x[g] = ['.' for _ in range(w)]
                if (j >> l) & 1:
                    for y in range(h):
                        x[y][l] = '.'
        for z in x:
            for m in z:
                if m == '#':
                    cnt += 1
        if k == cnt:
            ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

for h in range(0, 2**H):
  for w in range(0, 2**W):
    h_str = format(h, 'b').zfill(H)
    w_str = format(w, 'b').zfill(W)
    test = deepcopy(board)
    for i in range(H):
      if h_str[i] == '1':
        test[i] = 'r'*W
      for j in range(W):
      	if w_str[j] == '1':
          test[i] = test[i][:j] + 'r' + test[i][j+1:]
    counter = 0
    for row in test:
      counter += row.count('#')
    if counter == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
#C
from itertools import combinations
H,W,K=map(int,input().split())
C=[input() for i in range(H)]
cnt=0
for i in range(H):
    for j in range(W):
        if C[i][j]=="#":
            cnt+=1
combH=[]
combW=[]
for h in range(H+1):
    combH+=combinations(list(range(H)),h)
for w in range(W+1):
    combW+=combinations(list(range(W)),w)
    
ans=0
for h in combH:
    for w in combW:
        cou=0
        flag=[[True for i in range(W)] for j in range(H)]
        for i in h:
            for j in range(W):
                if flag[i][j]:
                    if C[i][j]=="#":
                        cou+=1
                        flag[i][j]=False
        for i in range(H):
            for j in w:
                if flag[i][j]:
                    if C[i][j]=="#":
                        cou+=1
                        flag[i][j]=False
        if cnt-cou==K:
            ans+=1
print(ans)

Submission status: Accepted

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

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

ans = 0

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


print(ans)

Submission status: Accepted

Solution code:
# ####################################################################
# import io
# import sys

# _INPUT = """\
# 2 3 4
# ..#
# ###

# 2 3 2
# ..#
# ###
# """
# sys.stdin = io.StringIO(_INPUT)
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################


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

M = list( list(input()) for _ in range(H) )

def fCntM(A):
  cnt = 0
  for h in range(H):
    for w in range(W):
      if A[h][w] == "#": cnt += 1
  return cnt


ans = 0

# if fCntM(M) == K: ans += 1

for h in range(1 << H):
  for w in range(1 << W):

    A = [ ["_"]*W for _ in range(H) ]
    for i in range(H):
      for j in range(W):
        if ( (h >> i) & 1 ) or ( (w >> j) & 1 ):
          A[i][j] = "R"
        else:
          A[i][j] = M[i][j]

    if fCntM(A) == K: ans += 1
    # _p("h,w = ", h,w, "ans=",ans)
    # _pa(A)


print(ans)

Submission status: Accepted

Solution code:
import copy

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


def count(c):
    cnt = 0
    for i in range(len(c)):
        for j in range(len(c[i])):
            if "#" == c[i][j]:
                cnt += 1
    return cnt


def pattenrs(i, n, str, lst):
    if i == n:
        lst.append(str)
        return
    pattenrs(i + 1, n, str + "0", lst),
    pattenrs(i + 1, n, str + "1", lst)


patterns_i = []
pattenrs(0, h, "", patterns_i)

patterns_j = []
pattenrs(0, w, "", patterns_j)

total_black = count(c)
res = 0
for pattern_i in patterns_i:
    for pattern_j in patterns_j:
        copied = copy.deepcopy(c)
        cnt = total_black
        i_list = list(map(int, pattern_i))
        j_list = list(map(int, pattern_j))
        for i in range(len(i_list)):
            for j in range(len(j_list)):
                if 1 == i_list[i] or 1 == j_list[j]:
                    cnt -= 1 if "#" == copied[i][j] else 0
        res += 1 if cnt == k else 0

print(res)

Submission status: Accepted

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

def getset(n):
    l = []
    curr = 0
    while n:
        if n & 1:
            l.append(curr)
        curr += 1
        n //= 2
    return l

for hSet in range(2 ** H):
    hL = getset(hSet)
    for cSet in range(2 ** W):
        cL = getset(cSet)
        cnt = 0
        for i in hL:
            for j in cL:
                if c[i][j] == '#':
                    cnt += 1
        if cnt == K:
            out += 1
print(out)

Submission status: Accepted

Solution code:
import sys
import itertools

import numpy as np


def main():
    def readline() -> str:
        s = sys.stdin.readline()
        return s.rstrip()

    h, w, k = map(int, readline().split())  # type: int, int, int
    field: np.ndarray = np.array(
        tuple(
            tuple(0 if c == "." else 1 for c in readline()) for _ in range(h)
        )
    )

    answer: int = 0

    for pattern_num in range(2 ** (h + w)):
        test_field = field.copy()
        pattern_num_bin = format(pattern_num, f"0{h+ w}b")
        h_bin: str = pattern_num_bin[:h]
        w_bin: str = pattern_num_bin[h:]

        for row in range(h):
            if h_bin[row] == "1":
                test_field[row] = np.ones((w,)) * 2

        for column in range(w):
            if w_bin[column] == "1":
                test_field[:, column] = np.ones((h,)) * 2

        if np.sum(test_field == 1) == k:
            answer += 1

    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    h,w,k = [int(v) for v in input().split()]
    c = []
    for _ in range(h):
        c.append(int('0b'+input().replace('#','1').replace('.','0'),0))
    imax = 1 << w
    bc = [0] * imax
    for i in range(imax):
        bc[i] = len([v for v in list(bin(i)) if v=='1'])

    sum = 0
    for ih in range(1<<h):
        for iw in range(1<<w):
            cnt = 0
            for j in range(h):
                if ih & (1 << j):
                    cnt += bc[c[j] & iw]   
            if cnt==k:
                sum += 1
    
    print(sum)

main()

Submission status: Accepted

Solution code:
import itertools
import copy

h, w, k = map(int, input().split())
C = [[False] * w for i in range(h)]
for i in range(h):
    C[i] = list(input())

result = 0
product = itertools.product(range(2), repeat=(h + w))
for p in product:
    operation_target = copy.deepcopy(C)
    rows = p[:w]
    cols = p[w:]
    for idx, i in enumerate(rows):
        if i == 1:
            for j in range(h):
                operation_target[j][idx] = '.'
    for idx, i in enumerate(cols):
        if i == 1:
            for j in range(w):
                operation_target[idx][j] = '.'
    counter = 0
    for i in range(h):
        for j in range(w):
            if operation_target[i][j] == '#':
                counter += 1
    if counter == k:
        result += 1
print(result)

Submission status: Accepted

Solution code:
import itertools
import copy

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

cnt = 0
h_l = list(range(0,h,1))
w_l = list(range(0,w,1))

for inum in range(h):
    for ilis in itertools.combinations(h_l, inum):
        ilis = list(ilis)

        for jnum in range(w):
            for jlis in itertools.combinations(w_l, jnum):
                jlis = list(jlis)
                c_list = copy.copy(c)

                if len(ilis) != 0:
                    for i in ilis:
                        c_list[i] = '0' * w
                if len(jlis) != 0:
                    for j in jlis:
                        for i in range(h):
                            if not c_list[i] == '0' * w:
                                c_list[i] = c_list[i][0:j] + '0' + c_list[i][j+1:]
                c_str = ''.join(c_list)
                if c_str.count('#') == k:
                    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import copy
n, *masu = [i.split() for i in open(0)]
h, w, k = map(int, n)
c = 0
masu = [list(*i) for i in masu]
for i in range(2**h):
    hi = []
    for j in range(h):
        if i>>j &1:
            hi.append(j)
    for p in range(2**w):
        wi = []
        for q in range(w):
            if p>>q &1:
                wi.append(q)
        d = copy.deepcopy(masu)
        for r in hi:
            d[r] = ["."] * w

        for r in wi:
            for o in range(h):
                d[o][r] = "."
        if k == sum(s == "#" for s in sum(d, [])):
            c += 1
print(c)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

result = 0

for y in range(1 << H):
    for x in range(1 << W):
        count = 0
        for i,d1 in enumerate(data):
            if (y >> i) & 1:
                continue
            for j,d2 in enumerate(d1):
                if (x >> j) & 1:
                    continue
                if d2 == '#':
                    count += 1
        if count == K:
            result += 1

print(result)

Submission status: Accepted

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

total = 0
for s in S:
    total += s.count("#")

ans = 0

def check(h_l,w_l):
    S_copy = []
    for s in S:
        S_copy.append(s[:])
    for h,b1 in enumerate(h_l):
        if b1: continue
        for i in range(W):
            S_copy[h][i] = 'r'

    for w,b1 in enumerate(w_l):
        if b1: continue
        for i in range(H):
            S_copy[i][w] = 'r'

    c = 0
    for s in S_copy:
        c += s.count("#")
    return c == K





def bit(N):
    r = []
    for i in range(2**N):
        ret = []
        for j in range(N):
            ret.append(i>>j & 1 == 1)
        r.append(ret)
    return r

H_L = bit(H)
W_L = bit(W)

ans = 0
for h_l in H_L:
    S_c = S[:]
    for w_l in W_L:
        if check(h_l,w_l):
            ans += 1
print(ans)

Submission status: Accepted

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

counter = 0
for i in range(2**w):
    for j in range(2**h):
        read=[]
        for l in range(h):
            if j >> l & 1:
                read.append([True]*w)
            else:
                read.append([False]*w)
        for k in range(w):
            if i >> k & 1:
                for m in range(h):
                    read[m][k] = False
        tmpcounter=0
        for a in range(h):
            for b in range(w):
                if clist[a][b] == '#' and read[a][b]:
                    tmpcounter += 1
        if tmpcounter == K:
            counter += 1
print(counter)