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

ans = 0
for h_selected in itertools.product(*[(0, 1)]*H):
  for w_selected in itertools.product(*[(0, 1)]*W):
    count = 0
    for h in range(H):
      if h_selected[h]:
        continue
      for w in range(W):
        if w_selected[w]:
          continue
        if c[h][w] == '#':
          count+=1
    #print(h_selected, w_selected, count)
    if count == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

H, W, K = map(int, input().split())
Map = [[0] * W for _ in range(H)]
ans = 0
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            Map[i][j] = 1

Columns = []
Rows = []
for i in range(H):
    Columns.append(i)
for i in range(W):
    Rows.append(i)

for i in range(H + 1):
    for j in range(W + 1):
        for c in combinations(Columns, i):
            for r in combinations(Rows, j):
                black = 0
                for y in c:
                    for x in r:
                        if Map[y][x]:
                            black += 1
                if black == K:
                    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import time
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(hl, wl):
  cnt = 0
  for h in range(H):
    if h in hl:
      continue
    for w in range(W):
      if w in wl:
        continue
      if grid[h][w] == "#":
        cnt += 1
  if cnt == K:
    return True
  else:
    return False

H,W,K = IL()
grid = [list(S()) for i in range(H)]

ans = 0
for i in range(1<<H):
  a = []
  for ii in range(H):
    if (i >> ii) & 1 == 1:
      a.append(ii)
  for j in range(1<<W):
    b = []
    for jj in range(W):
      if (j >> jj) & 1 == 1:
        b.append(jj)
    if tami(a, b):
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

area = np.zeros([h, w], dtype=int)

for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "#":
            area[i, j] = 1


ans = 0

for i in range(2**(h+w)):
    area_ = area.copy()

    for j in range(h+w):
        if ((i >> j) & 1):
            if j < h:
                area_[j, :] = 0
            else:
                area_[:, j-h] = 0
    
    if np.sum(area_) == k:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def m():
    H, W, K = map(int, input().split())
    G = [list(input()) for _ in range(H)]
    ans = 0
    for y in range(2 ** H):
        for x in range(2 ** W):
            y_mask = bin(y)[2:].zfill(H)
            x_mask = bin(x)[2:].zfill(W)
            black_cnt = 0
            for j in range(H):
                for i in range(W):
                    if y_mask[j] == '1':
                        continue
                    if x_mask[i] == '1':
                        continue
                    if G[j][i] == '#':
                        black_cnt += 1
            if black_cnt == K:
                ans += 1
    return ans


print(m())

Submission status: Accepted

Solution code:
from itertools import combinations
h, w, k = map(int, input().split())

C = [list(input()) for _ in range(h)]

ans = 0

for p in range(h):
    h_combs = list(combinations(list(range(h)), p))
    for q in range(w):
        w_combs = list(combinations(list(range(w)), q))
        for h_comb in h_combs:
            for w_comb in w_combs:
                cnt = 0
                for i in range(h):
                    for j in range(w):
                        if i not in h_comb and j not in w_comb and C[i][j] == '#':
                            cnt += 1
                if cnt == k:
                    ans += 1
print(ans)

Submission status: Accepted

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

G = [list(input()) for _ in range(H)]

def calc(lst1, lst2):
    tmp = 0
    for h in range(H):
        for w in range(W):
            if G[h][w] == '#' and lst1[h] == 0 and lst2[w] == 0:
                tmp += 1
    # print (lst1, lst2, tmp)
    return tmp



ans = 0
for i in range(2 ** H):
    lst1 = [0] * H
    for j in range(H):
        if (i >> j) & 1:
            lst1[j] = 1
    for k in range(2 ** W):
        lst2 = [0] * W
        for l in range(W):
            if (k >> l) & 1:
                lst2[l] = 1
        if calc(lst1, lst2) == K:
            # print (lst1, lst2)
            ans += 1

print (ans)
# print (G)

Submission status: Accepted

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

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

input_H_list = []
for i in range(2 ** H):
    para_ = i
    temp_ = []
    for k in range(H):
        if para_ % 2 == 0:
            temp_.append(0)
        else:
            temp_.append(1)
        para_ = para_ // 2
    input_H_list.append(temp_)

input_W_list = []
for i in range(2 ** W):
    para_ = i
    temp_ = []
    for k in range(W):
        if para_ % 2 == 0:
            temp_.append(0)
        else:
            temp_.append(1)
        para_ = para_ // 2
    input_W_list.append(temp_)

ans_count = 0    
    
for H_list in input_H_list:
    for W_list in input_W_list:
        not_black_counter = 0
        for i in range(H):
            if H_list[i] == 1:
                not_black_counter += W
            else:
                
                for j in range(W):
                    if W_list[j] == 1:
                        not_black_counter += 1
                    else:
                        if input_data[i][j] == ".":
                            not_black_counter += 1
        if not_black_counter + K  == H * W:
            ans_count += 1
print(ans_count)

Submission status: Accepted

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

h, w, k = map(int, input().split())
s = ['' for _ in range(h)]
ans = 0
for i in range(h):
    s[i] = input()
for xi in range(2**h):
    t = deepcopy(s)
    b = [0 for _ in range(w)]
    for i in range(h):
        if ((xi >> i)&1):
            t[i] = ''
            for j in range(w):
                t[i] += '.'
    for i in range(h):
        for j in range(w):
            if t[i][j] == '#':
                b[j] += 1
    for xj in range(2**w):
        sumv = 0
        for j in range(w):
            if ((xj >> j)&1):
                sumv += b[j]
        if sumv == k: ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**H):
    i_format = "0"+str(H)+"b"
    i_bin = format(i, i_format)
    for j in range(2**W):
        j_format = "0"+str(W)+"b"
        j_bin = format(j, j_format)
        count = 0
        for n in range(H):
            row = c[n]
            if i_bin[n] == "0":
                for m in range(W):
                    if j_bin[m] == "0":
                        if row[m] == "#":
                            count += 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 h in range(2**H):
    hbit = bin(h)[2:].zfill(H)
    hselect = set()
    for hi, hb in enumerate(hbit):
        if hb == '1':
            hselect.add(hi)
    for w in range(2**W):
        wbit = bin(w)[2:].zfill(W)
        wselect = set()
        for wi, wb in enumerate(wbit):
            if wb == '1':
                wselect.add(wi)

        tmp = 0
        for i in range(H):
            if i in hselect:
                continue
            for j in range(W):
                if j in wselect:
                    continue
                if S[i][j] == '#':
                    tmp += 1

        if tmp == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
raw = []
for _ in range(h):
  tmp = input()
  add = []
  for j in range(w):
    if tmp[j] == '.':
      add.append(0)
    else:
      add.append(1)
  raw.append(add)
ans = 0
time1 = [0 for i in range(h)]
time2 = [0 for j in range(w)]
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'
from copy import deepcopy as dc
while time1 != 'over':
  use = dc(raw)
  for i in range(h):
    if time1[i] == 1:
      for j in range(w):
        use[i][j] = 0
  while time2 != 'over':
    now = dc(use)
    for j in range(w):
      if time2[j] == 1:
        for i in range(h):
          now[i][j] = 0
    cnt = 0
    for i in range(h):
      cnt += sum(now[i])
    #print(time1,time2,cnt)
    if cnt == k:
      ans += 1
    time2 = nex(time2)
  time1 = nex(time1)
  time2 = [0 for _ in range(w)]
print(ans)
#print(raw)

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
c = [list(input()) for i in range(h)]
d = [[0 if j == "." else 1 for j in i] for i in c]
ans = 0
for i in range(2 ** h):
    a = [0] * h
    for j in range(h):
        if (i >> j) & 1:
            a[j] = 1
    for I in range(2 ** w):
        b = [0] * w
        kuro = 0
        for J in range(w):
            if (I >> J) & 1:
                b[J] = 1
        for k1,v1 in enumerate(d):
            if a[k1]:
                continue
            for k2,v2 in enumerate(v1):
                if b[k2]:
                    continue
                kuro += v2
        if kuro == k:
            ans += 1
print(ans)

Submission status: Accepted

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

def cnt(table):
    ret = 0
    for row in range(h):
        for col in range(w):
            ret += (table[row][col] == "#")
    return ret

ans = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        c_copy = deepcopy(c)
        for row in range(h):
            if ((i >> row) & 1):
                for col in range(w):
                    c_copy[row][col] = ":"
        for col in range(w):
            if ((j >> col) & 1):
                for row in range(h):
                    c_copy[row][col] = ":"
        ans += (cnt(c_copy) == k)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import Counter
h,w,k = map(int,stdin.readline().split())
bl = 0
arr = [list(stdin.readline()) for _ in range(h)]
row = Counter()
col = Counter()
for i in range(h):
    for j in range(w):
        if arr[i][j] == '#':
            bl += 1
            row[i] += 1
            col[j] += 1
ans = 0
for i in range(2**h):
    for j in range(2**w):
        x,y = bin(i)[2:],bin(j)[2:]
        val = bl
        for bit in range(len(x)-1,-1,-1):
            if x[bit] == '1':
                val -= row[len(x)-1-bit]
                for bit1 in range(len(y)-1,-1,-1):
                    if y[bit1] == '1':
                        val += (arr[len(x)-1-bit][len(y)-1-bit1]=='#')
        for bit in range(len(y)-1,-1,-1):
            if y[bit] == '1':
                val -= col[len(y)-1-bit]
        if val==k:
            ans += 1
print(ans)

Submission status: Accepted

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

# 各行・各列を選ぶか選ばないかで全列挙してbit

ans = 0

for hn in range(2**H):
    hbit = bin(hn)[2:].zfill(H)
    for wn in range(2**W):
        wbit = bin(wn)[2:].zfill(W)
        count = 0
        # hbit[h] == "1" and wbit[w] == "1" の場合は "#" が残ると考える
        for h in range(H):
            for w in range(W):
                if hbit[h] == "1" and wbit[w] == "1" and c[h][w] == "#":
                    count += 1
        if count == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
h, w, v = map(int, input().split())
mas = [list(input()) for i in range(h)]

ans = 0
for i in range(2**h):
  for j in range(2**w):
    res = 0
    hlist = []
    wlist = []
    for k in range(h):
      if (i >> k) & 1:
        hlist.append(k)
    for k in range(w):
      if (j >> k) & 1:
        wlist.append(k)
    
    for k in range(h):
      if k in hlist:
        continue
      for l in range(w):
        if l in wlist:
          continue
        if mas[k][l] == "#":
          res += 1
    if res == v:
      ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

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



lst=list(product(range(2),repeat=H+W))
nlst=set()
a=0
for l in lst:
    _C=copy.deepcopy(C)
    for h in range(H):
        if l[h]:
            for w in range(W):
                _C[h][w]="R"
    for w in range(W):
        if l[H+w]:
            for h in range(H):
                _C[h][w]="R"
    #print(_C,C)
    if sum([_C[h].count("#") for h in range(H)])==K:
    #    print(_C)
        s=""
        for h in range(H):
            s+="".join(_C[h])
        if not s in nlst:
            a+=1
            nlst.add(s)
print(a)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
C = []

for i in range(H):
    c = input()
    C.append(c)

ans = 0

for i in range(2**H):
    for j in range(2**W):
        cnt = 0
        for k in range(H):
            for l in range(W):
                if ((i >> k) & 1) and ((j >> l) & 1) and C[k][l] == "#":
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

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

import copy
import itertools


def solve(h, w, k, stage):
    res = 0
    is_sel_rs = itertools.product((False, True), repeat=h)
    is_sel_cs = itertools.product((False, True), repeat=w)
    for irs, ics in itertools.product(is_sel_rs, is_sel_cs):
        st = copy.deepcopy(stage)
        for r0, ir in enumerate(irs):
            if ir:
                for c in range(w):
                    st[r0][c] = "*"
        for c0, ic in enumerate(ics):
            if ic:
                for r in range(h):
                    st[r][c0] = "*"
        num_blacks = 0
        for r, c in itertools.product(range(h), range(w)):
            if st[r][c] == "#":
                num_blacks += 1
        if num_blacks == k:
            res += 1
    return res


def main():
    h, w, k = (int(z) for z in input().split())
    stage = [list(input()) for _ in range(h)]
    res = solve(h, w, k, stage)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from itertools import product

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

    tot = 0

    rows = []
    for row in G:
        rows.append((cnt := row.count('#')))
        tot += cnt

    cols = []
    for col in zip(*G):
        cols.append(col.count('#'))

    ans = 0
    for row_conds in product([0, 1], repeat=H):
        t = tot
        for r, row_cond in enumerate(row_conds):
            if row_cond:
                t -= rows[r]
        for col_conds in product([0, 1], repeat=W):
            s = t
            for c, col_cond in enumerate(col_conds):
                if col_cond:
                    s -= cols[c]
                    for r2, row_cond2 in enumerate(row_conds):
                        if row_cond2 and G[r2][c] == '#':
                            s += 1
            if s == K:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w,K = na()
g = []
for i in range(h):
    g.append(ns())

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

print(ans)

Submission status: Accepted

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

ans = 0
for h_mask in product([False, True], repeat=H):
    for w_mask in product([False, True], repeat=W):
        count = 0
        for h in range(H):
            for w in range(W):
                # 赤く塗られた=False
                if h_mask[h] and w_mask[w] and c[h][w] == "#":
                    count += 1
        if count == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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


ans = 0
for i in range(2 ** H):
    row = []
    for j in range(H):
        if ((i >> j) & 1):
            row.append(j)
    for k in range(2 ** W):
        column = []
        for l in range(W):
            if ((k >> l) & 1):
                column.append(l)
        cnt = 0
        for r in row:
            for c in column:
                if cells[r][c] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

area = []
ans = 0
for i in range(h):
    x = list(input())
    area.append(x)

for i in range(2**(h+w)):
    num = format(i, 'b').zfill(h+w)
    cnt = 0
    for j in range(h):
        for l in range(w):
            if num[j] == '1' or num[h+l] == '1':
                continue
            else:
                if area[j][l] == '#':
                    cnt += 1
    if cnt == k:
        ans += 1

print(ans)

Submission status: Accepted

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

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

if black < K:
    print(0)
else:
    for i in range(1 << H):
        for j in range(1 << W):
            cnt = 0
            watched = [[False for _ in range(W)] for __ in range(H)]
            for h in range(H):
                if 1 << h & i:
                    for w in range(W):
                        if S[h][w] == "#":
                            cnt += 1
                            watched[h][w] = True

            for w in range(W):
                if 1 << w & j:
                    for h in range(H):
                        if S[h][w] == "#" and watched[h][w] == False:
                            cnt += 1
                            watched[h][w] = True

            if black - cnt == K:
                ans += 1

    print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from itertools import product
H, W, K = map(int, input().split())
ls = []
for i in range(H):
    s = list(input())
    ls.append(s)
ans = 0
for x in product([0, 1], repeat=H):
    for y in product([0, 1], repeat=W):
        p = deepcopy(ls)
        num = 0
        for i, j in enumerate(x):
            if j == 1:
                for w in range(W):
                    p[i][w] = '?'
        for i, j in enumerate(y):
            if j == 1:
                for h in range(H):
                    p[h][i] = '?'
        for k in p:
            for l in k:
                if l == '#':
                    num += 1
        if num == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,k=LI()
  field=[S() for _ in range(h)]

  ans=0
  for i in range(1<<(h+w)):
    hh=[False]*h
    ww=[False]*w
    for j in range(h+w):
      if i&(1<<j):
        if j<h:
          hh[j]=True
        else:
          ww[j-h]=True

    cnt=0
    for j in range(h):
      if hh[j]:
        continue
      for _k in range(w):
        if ww[_k]:
          continue

        if field[j][_k]=='#':
          cnt+=1

    if cnt==k:
      ans+=1

  return ans

# main()
print(main())

Submission status: Accepted

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

from itertools import chain, combinations

def subsets(iterable, low=0, high=None):
    "subsets([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    if high is None:
        high = len(s)
    return chain.from_iterable(combinations(s, r) for r in range(low, high+1))

H, W, K = input().split(' ')

H = int(H)
W = int(W)
K = int(K)

A = []

for _ in range(H):
    row = input()
    A += [row]

# print(f"A={A}")

ret = 0

def ok(rows, cols, A):
    A = [list(row) for row in A]
    for x in rows:
        for y in range(W):
            A[x][y] = '.'
    for y in cols:
        for x in range(H):
            A[x][y] = '.' 
    
    return K == sum(sum(1 for r in row if r == '#') for row in A)

for h in subsets(range(0, H)):
    for w in subsets(range(0, W)):
        if ok(h, w, A):
            ret += 1        
            # print(f"{h} {w}")

print(ret)

Submission status: Accepted

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

ans = 0
for i in range(1<<H):
    for j in range(1<<W):
        count = 0
        for h in range(H):
            for w in range(W):
                if ((i&(1<<h)==0) and (j&(1<<w)==0) and C[h][w]=="#"):
                    count += 1
        if(count == 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)]
for i in range(h):
    c[i] = list(input())

ans = 0

for i in range(2**(h+w)):
    m = copy.deepcopy(c)
    for j in range(w):
        if i&(1<<j):
            for x in range(h):
                if m[x][j] == '#':
                    m[x][j] = 'r'
    for j in range(w, w+h):
        if i&(1<<j):
            for x in range(w):
                if m[j-w][x] == '#':
                    m[j-w][x] = 'r'
    cur = 0
    for x in range(h):
        for j in range(w):
            if m[x][j] == '#':
                cur += 1
    if cur == 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)]

a = [i for i in range(h)]
b = [i for i in range(w)]


def cnt(i, j):
    ret = 0
    for k in range(len(i)):
        for t in range(len(j)):
            if i[k] == 0 or j[t] == 0:
                continue
            if grid[k][t] == "#":
                ret += 1

    return ret

ans = 0
for i in product([0, 1], repeat=h):
    for j in product([0, 1], repeat=w):
        if cnt(i, j) == 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())
field = np.array([[int(c == "#") for c in input()] for _ in range(H)])

ans = 0
for hs in product([0, 1], repeat=H):
    for ws in product([0, 1], repeat=W):
        test_field = field.copy()
        for i, h in enumerate(hs):
            if h == 1:
                test_field[i] = 0
        for j, w in enumerate(ws):
            if w == 1:
                test_field[:, j] = 0
        if test_field.sum() == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    H, W, K = LI()
    maze = SR(H)
    ans = 0
    for h in range(H+1):
        for w in range(W+1):
            for painted_row in itertools.combinations(range(H), h):
                for painted_col in itertools.combinations(range(W), w):
                    black = 0
                    for i in range(H):
                        for j in range(W):
                            if (i not in painted_row) and (j not in painted_col) and maze[i][j] == "#":
                                black += 1
                    if black == K:
                        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    H, W, K = map(int, input().split())
    C = [input() for _ in range(H)]
    ans = 0
    for row in range(1 << H):
        for col in range(1 << W):
            cnt = 0
            for i in range(H):
                for j in range(W):
                    if (row & (1 << i)) or (col & (1 << j)): continue
                    if C[i][j] == '#':
                        #print(i, j)
                        cnt += 1
            #print("row={}, col={}, cnt={}".format(row, col, cnt))
            if cnt == K:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()

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):
  sr=set([])
  for hi in range(h):
    if (i>>hi)&1:
      sr.add(hi)
  for j in range(2**w):
    sc=set([])
    for wi in range(w):
      if (j>>wi)&1:
        sc.add(wi)
    cnt=0
    for hi in range(h):
      for wi in range(w):
        if hi not in sr and wi not in sc and c[hi][wi]=='#':
          cnt+=1
    if cnt==k:
      ans+=1
      #print(sc,sr)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    h, w, k = geta(int)
    c = []
    for _ in range(h):
        c.append(gete())

    ans = 0
    for b in range(2**(h+w)):
        ih = []
        iw = []
        for i in range(h):
            ih.append(b & 1 == 1)
            b >>= 1
        for i in range(w):
            iw.append(b & 1 == 1)
            b >>= 1

        rem = 0
        for i in range(h):
            if ih[i]:
                continue
            for j in range(w):
                if iw[j]:
                    continue
                if c[i][j] == "#":
                    rem += 1

        if rem == k:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def ct(arr,rows,cols):
	ret = 0
	for i in range(len(arr)):
		for j in range(len(arr[0])):
			if(rows[i]=='0' and cols[j]=='0' and arr[i][j]=='#'):
				ret+=1
	return ret
h,w,k = list(map(int,input().split()))
arr = []
for i in range(h):
	l = input()
	arr.append(l)
	# for j in range(w):
		# arr[i][j] = l[j]
ans = 0
for i in range(2**h-1,-1,-1):
	for j in range(2**w-1,-1,-1):
		if ct(arr,(bin(i)[2:]).zfill(h),(bin(j)[2:]).zfill(w))==k:
			ans+=1
print(ans)

Submission status: Accepted

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

cnt = 0
for h in range(2**H):
    h_bits = [j for j in range(H) if (h >> j &1)]
    for w in range(2**W):
        w_bits = [j for j in range(W) if (w >> j &1)]
        blacks = 0
        for hi in h_bits:
            for wi in w_bits:
                blacks += 1 if table[hi][wi] == "#" else 0
        cnt += 1 if blacks == K else 0

print(cnt)