Problem:


Score : 300 points

Problem Statement

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

Consider doing the following operation:

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

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

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

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

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

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

Sample Output 4

208



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


Sample output:
5

Submission status: Accepted

Solution code:

from itertools import chain,combinations
from itertools import product
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

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

    rows = []
    for h in range(H):
        rows.append(input())
    
    row_choices = list(powerset(range(H)))
    col_choices = list(powerset(range(W)))

    ans = 0
    for r_set, c_set in product(row_choices, col_choices):
        selected_rows = [r for i, r in enumerate(rows) if i not in r_set]
        n_blacks = 0
        for r in selected_rows:
            n_blacks += len([c for j, c in enumerate(r) if j not in c_set and c == '#'])
        
        if n_blacks == K:
            ans += 1

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
H,W,K = map(int,input().split())
C = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  C.append(temp)
#print(C)
#p,qを答えとする
def count(X):
  ret = 0
  for i in range(H):
    for j in range(W):
      if X[i][j] == "#":
        ret +=1
  return ret
ans = 0
for p in range(2**H):
  for q in range(2**W):
    D = copy.deepcopy(C)
    for i in range(H):
      if(p>>i)&1==1:
        D[i] = ["1" for _ in range(W)]
    for j in range(W):
      if(q>>j)&1==1:
        for t in range(H):
          D[t][j] = "1"
    #print(D,p,q,count(D))
    if count(D) == K:
      ans += 1
print(ans)

Submission status: Accepted

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

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

h_l = [i for i in range(H)]
w_l = [i for i in range(W)]

ans = 0
for i in range(2 ** H):
    for j in range(2 ** W):
        count = 0
        for h in range(H):
            for w in range(W):
                if ((i >> h) & 1) and ((j >> w) & 1):
                    if c[h][w] == "#":
                        count += 1
        if count == K:
            ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for b1 in range(2 ** h):
  for b2 in range(2 ** w):
    CC = [c[:] for c in C]
    for i in range(h):
      if (b1 >> i) & 1:
        for ww in range(w):
          CC[i][ww] = "."
    for j in range(w):
      if (b2 >> j) & 1:
        for hh in range(h):
          CC[hh][j] = "."
    bl = 0
    for line in CC:
      bl += line.count("#")
    if bl == k:
      ans += 1
print(ans)

Submission status: Accepted

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

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

for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '.':
            grid[i][j] = 1

ans = 0

for i in range(2**h):
    draw_row = [0 for k in range(h)]
    c = i
    for k in range(h):
        if c % 2 == 1:
            draw_row[k] = 1
        c >>= 1
    for j in range(2**w):
        draw_col = [0 for k in range(w)]
        c = j
        for k in range(w):
            if c % 2 == 1:
                draw_col[k] = 1
            c >>= 1

        count = 0
        for row in range(h):
            for col in range(w):
                if draw_row[row] == 0 and draw_col[col] == 0 and grid[row][col] == 0:
                    count += 1
        if count == k_num:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w,k=mp()
rh=[i for i in range(h)]
rw=[i for i in range(w)]
grid=[]
for i in range(h):
    grid.append(input())
lh=[]
lw=[]
for i in range(h):
    lh.extend(list(itertools.combinations(rh, i)))
for i in range(w):
    lw.extend(list(itertools.combinations(rw, i)))



ans=0

for x in lh:
    for y in lw:



        ch=[[0]*w for i in range(h)]
        for i in range(h):
            for j in range(w):
                if i in x or j in y:
                    ch[i][j]=1
        c=0
        for i in range(h):
            for j in range(w):
                if ch[i][j]==0 and grid[i][j]=="#":
                    c+=1


        if c==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    h,w,k = map(int,input().split())
    c = [list(input()) for _ in range(h)]
    ans = 0
    for n1 in range(h+1):
        for e1 in combinations(range(h),n1):
            for n2 in range(w+1):
                for e2 in combinations(range(w),n2):
                    cc = copy.deepcopy(c)
                    for x in e1:
                        for j in range(w):
                            cc[x][j] = '.'
                    for x in e2:
                        for i in range(h):
                            cc[i][x] = '.'
                    cnt = 0
                    for i in range(h):
                        for j in range(w):
                            if cc[i][j] == '#':
                                cnt += 1
                    if cnt == k:
                        ans += 1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

c = []
n_black = 0
for i in range(H):
  c.append(input().strip())
  n_black += c[-1].count("#")


def rec_col(count, n):
  if n == len(c):
    yield count
  else:
    yield from rec_col(list(count), n+1)
    for i, color in enumerate(c[n]):
      if color == "#":
        count[i] += 1
    yield from rec_col(list(count), n+1)

def rec_row(result, count, n):
  if n == len(count):
    yield result
  else:
    yield from rec_row(result + count[n], count, n+1)
    yield from rec_row(result, count, n+1)

import collections
ans = collections.Counter()
for count in rec_col([0] * W, 0):
  ans.update(rec_row(0, count, 0))
print(ans[K])

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    
    h, w, k = mi()
    grid = [li() for _ in range(h)]
    ans = 0

    for h_pattern in product([True, False], repeat=h):
        for w_pattern in product([True, False], repeat=w):
            painted = deepcopy(grid)
            for i in range(h):
                if h_pattern[i]:
                    for j in range(w):
                        painted[i][j] = 'R'
            for j in range(w):
                if w_pattern[j]:
                    for i in range(h):
                        painted[i][j] = 'R'
            if sum([line.count('#') for line in painted]) == k:
                # print(h_pattern, w_pattern)
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))


h,w,k = mp()
ans = 0
grid = []
for i in range(h):
    grid.append(list(input()))
h_pat = []
w_pat = []
for i in range(2**h):
    p = bin(i)[2:].zfill(h)
    h_pat.append(p)
for i in range(2**w):
    p = bin(i)[2:].zfill(w)
    w_pat.append(p)
import copy
for i in range(len(h_pat)):
    for j in range(len(w_pat)):
        tar_g = copy.deepcopy(grid)
        cnt = 0
        h_tar = h_pat[i]
        w_tar = w_pat[j]
        for v in range(len(h_tar)):
            if h_tar[v] == "1":
                tar_g[v] = ["R"]*w
        tar_g = [list(x) for x in zip(*tar_g)]
        for v in range(len(w_tar)):
            if w_tar[v] == "1":
                tar_g[v] = ["R"]*h
        for v in range(w):
            cnt += tar_g[v].count("#")
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
h,w ,k = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
for row in range(2**h):
    for column in range(2**w):
        grid_a =[[True for i in range(w)] for j in range(h)]
        count = 0
        for p in range(h):
            if (row >> p) & 1:
                for i in range(w):
                    grid_a[p][i] = False
        for p in range(w):
            if (column >> p) & 1:
                for i in range(h):
                    grid_a[i][p] = False
        for i in range(h):
            for j in range(w):
                if grid_a[i][j] and grid[i][j] == '#':
                    count+=1
        if count == k:
            ans += 1
print(ans)

Submission status: Accepted

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

res = 0
for i in range(2**H):
    a = bin(i)[2:].zfill(H)
    for j in range(2**W):
        b = bin(j)[2:].zfill(W)

        c = 0

        for (p, x) in enumerate(X):
            for (q, y) in enumerate(x):
                if a[p] != '1' and b[q] != '1' and y == '#':
                    c += 1

        if c == K:
            res += 1

print(res)

Submission status: Accepted

Solution code:
lis = []
H, W, K = tuple(int(x) for x in input().strip().split())
for _ in range(H):
    lis.append(tuple(1 if x == '#' else 0 for x in input().strip()))
lis = tuple(lis)

selectH = [False for _ in range(H)]
selectW = [False for _ in range(W)]
cnt = 0

def judge(h, w):
    ret = 0
    for i in range(H):
        if (h >> i) & 1:
            for j in range(W):
                if (w >> j) & 1:
                    ret += lis[i][j]
    return ret
            
if __name__ == '__main__':
    cnt = 0
    for h in range(1 << H):
        for w in range(1 << W):
            if judge(h, w) == K:
                cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
HW = [0] * H
for i in range(H):
  HW[i] = str(input())
ans = 0

for i in range(2 ** (H + W)):
  now = 0
  hh = [0] * H
  ww = [0] * W
  for j in range(H):
    if ((i >> j) & 1):
      hh[j] = 1
  for k in range(W):
    if (i >> (k + H)) & 1:
      ww[k] = 1
   
  for j in range(H):
    for k in range(W):
      if (hh[j] == 1) and (ww[k] == 1):
        if HW[j][k] == "#":
          now += 1
  #print(i, hh, ww, now)
  if now == K:
    ans += 1
    
print(ans)

Submission status: Accepted

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

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

black = 0
for i in range(h):
  s = input()
  for j in range(w):
    if s[j] == "#":
      c[i][j] = 1
      black += 1

ans = 0
for i in range(2 ** h):
  for j in range(2 ** w):
    _black = black
    for _i in range(h):
      for _j in range(w):
        if (i & (2 ** _i)) != 0 or (j & (2 ** _j)) != 0:
          _black -= c[_i][_j]
    if _black == k:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product, chain
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    H, W, K = readnums()
    c = [readstr() for _ in range(H)]
    b = sum([x.count('#') for x in c])

    ans = 0
    for p in product([0, 1], repeat=H):
        ch = [c[i] for i, a in enumerate(p) if a]
        for q in product([0, 1], repeat=W):
            tmp = []
            for i, qq in enumerate(q):
                tmp.append([chw[i] for chw in ch if qq])
            tmp = list(chain.from_iterable(tmp))
            if tmp.count('#') == K:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

H, W, K = input().split()
a = [list(input()) for l in range(int(H))]

h_l = [i for i in range(int(H))]
w_l = [i for i in range(int(W))]

re_h = []
re_w = []
for n in range(len(h_l)+1):
    for comb in itertools.combinations(h_l, n):
        re_h.append(list(comb))
for n in range(len(w_l)+1):
    for comb in itertools.combinations(w_l, n):
        re_w.append(list(comb))
sum_c = 0
for r_h in re_h:
    for r_w in re_w:
        nokori_h = list(set(h_l) - set(r_h))
        nokori_w = list(set(w_l) - set(r_w))
        count = 0
        for no_h in nokori_h:
            for no_w in nokori_w:
                if a[no_h][no_w] == "#":
                    count += 1
        if count == int(K):
            sum_c += 1
print(sum_c)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
for yb in range(2 ** h):
    for xb in range(2 ** w):
        n = 0
        for y in range(h):
            for x in range(w):
                if yb & (1 << y) != 0 and xb & (1 << x) != 0 and c[y][x] == '#':
                    n += 1
        if n == k:
            ans += 1
print(ans)

Submission status: Accepted

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

M = [input().strip() for _ in range(H)]


def count(m):
    res = 0
    for j in range(H):
        for i in range(W):
            if m[j][i] == "#":
                res += 1
    return res


ans = 0

for j in range(2 ** H):
    for i in range(2 ** W):
        tmp = []
        for m in range(len(M)):
            tmp.append(M[m])

        for m in range(6):
            if j >> m & 1 == 1:
                tmp[m] = "r" * W

        for m in range(6):
            if i >> m & 1 == 1:
                for h in range(H):
                    tmp[h] = tmp[h][0:m] + "r" + tmp[h][m+1:]
        if count(tmp) == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
L=[]
for i in range(H):
    s=list(input())
    for j in range(W):
        if s[j]=="#":
            s[j]=1
        else:
            s[j]=0
    L.append(s)
#print(L)

import copy
ans=0
l=[0 for i in range(W)]
for h in range(2**H):
    A=copy.deepcopy(L)
    Y=h+0
    for y in range(H):
        if Y&1==0:
            A[y]=l
        Y=Y>>1
    #print(A)
    
    for w in range(2**W):
        X=w+0
        cnt=0
        for x in range(W):
            if X&1==1:
                for z in range(H):
                    cnt+=A[z][x]
            X=X>>1
        #print(cnt)
        if cnt==K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy

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


#bit全探索
S = 0
for i in range(2 ** (H+W)):
    field = copy.deepcopy(c)
    bag = []
    for j in range(H+W):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            if j < W:
                for y in range(H):
                    field[y][j] = "."
            else:
                for x in range(W):
                    field[j-W][x] = "."
    #print(field)
    #print()
    Sum = 0
    for x in range(W):
        for y in range(H):
            if field[y][x] == "#":
                Sum += 1

    if Sum == K:
        S += 1

print(S)

Submission status: Accepted

Solution code:
import numpy as np
h,w,k = map(int,input().split())
c = np.zeros((h,w), dtype="int")
f = lambda x: 1 if x=="#" else 0
for i in range(h):
    l=list(map(f,list(input())))
    c[i] = l

sum_=(c.sum())
cc=0
for i in range(2 ** h):
    l=[]
    for j in range(h):
        if ((i >> j) & 1): 
            l.append(j)
            
    for ii in range(2 ** w):
        ll=[]
        for jj in range(w):
            if ((ii >> jj) & 1): 
                ll.append(jj)
        if l and ll:
            ans = (c[l].sum()+c[:,ll].sum()-c[l][:,ll].sum())
        elif l and (not ll):
            ans = (c[l].sum())
        elif ll and (not l):
            ans = (c[:,ll].sum())
        else:
            ans = (0)
        #print(l,ll,ans)
        if sum_-k == ans:
            cc+=1
print(cc)

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W,K=mi()
    C = [[""]*H for _ in range(W)]
    for h in range(H):
        t = list(input())
        for w in range(W):
            C[w][h] = t[w]
    
    WL = []
    for i in range(2**W):
        w_l = set()
        for j in range(W): 
            if ((i >> j) & 1):
                w_l.add(j)
        WL.append(w_l)

    HL = []
    for i in range(2**H):
        h_l = set()
        for j in range(H): 
            if ((i >> j) & 1):
                h_l.add(j)
        HL.append(h_l)


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

        return cnt

    def refill_and_count(wl,hl):
        newC = [[""]*H for _ in range(W)]
        for h in range(H):
            for w in range(W):
                if w in wl or h in hl:
                    newC[w][h] = "r"
                else:
                    newC[w][h] = C[w][h]

        # print(newC)
        return count(newC)

    ans = 0
    for wl in WL:
        for hl in HL:
            # print(wl,hl)
            black = refill_and_count(wl,hl)
            # print(black)
            if black == K:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#from bisect import bisect_right
#from collections import deque
import itertools
import numpy as np

def main():
    H, W, K = tuple(int(c) for c in input().split())
    C = np.zeros((H,W))
    for h in range(H):
        line = input()
        for w in range(len(line)):
            if line[w]=='#':
                C[h,w] = 1
    #bit全探索
    ans = 0
    for p_h in itertools.product([True,False], repeat=H):
        for p_w in itertools.product([True,False], repeat=W):
            C_t = C.copy()
            C_t[p_h, :] = 0
            C_t[:, p_w] = 0
            if C_t.sum() == K:
                #print(C_t)
                ans += 1
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    H, W, K = MI()
    graph = [None] * H
    black_cnt = 0
    dic = defaultdict(int)
    ans = 0

    for i in range(H):
        s = S()
        graph[i] = s

        for j in range(len(s)):
            if s[j] == '#':
                dic[(i, j)] += 1
                black_cnt += 1

    N = H + W
    for i in range(2 ** N):
        row = []
        col = []
        for j in range(N):
            if ((i >> j) & 1):
                if j < H:
                    row.append(j)
                else:
                    col.append(j - H)

        current_cnt = black_cnt
        visited = defaultdict(int)
        for i in row:
            for j in range(W):
                visited[(i, j)] += 1
                if (i,j) in dic:
                    current_cnt -= 1

        for i in range(H):
            for j in col:
                if (i,j) in visited:
                    continue
                visited[(i, j)] += 1
                if (i,j) in dic:
                    current_cnt -= 1

        if current_cnt == K:
            ans += 1
        # print('row', row)
        # print('col', col)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

C = [input() for i in range(H)]

import itertools

ans = 0
for i in itertools.product([0, 1], repeat=H):
    for j in itertools.product([0, 1], repeat=W):
        count = 0
        for h in range(H):
            for w in range(W):
                if i[h] != 1 and j[w] != 1 and C[h][w] == "#":
                    count += 1
        if count == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
c = [list(input().strip()) for _ in range(H)]
b = 0
for y in range(H):
    for x in range(W):
        if c[y][x] == "#":
            b += 1

ans = 0
for row in range(2 ** H):
    rows = []
    for h in range(H):
        if row & (1 << h):
            rows.append(h)
    for col in range(2 ** W):
        rc = {}
        cols = []
        for w in range(W):
            if col & (1 << w):
                cols.append(w)

        for y in rows:
            for x in range(W):
                rc[(y, x)] = c[y][x]
        for x in cols:
            for y in range(H):
                rc[(y, x)] = c[y][x]

        tb = b
        for v in rc.values():
            if v == "#":
                tb -= 1
        if tb == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int, input().split())
A=[]
for i in range(H):
  a=input()
  A.append(a)
  
import itertools
B=list(itertools.product([0,1], repeat=H))
C=list(itertools.product([0,1], repeat=W))
ans=0
for b in B:
  for c in C:
    cnt=0
    for i in range(H):
      for j in range(W):
        if A[i][j]=='#' and b[i]==0 and c[j]==0:
          cnt+=1
    if cnt==K:
      ans+=1
print(ans)

Submission status: Accepted

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

def solve():
    H, W, K = map(int, readline().split())
    C = [[1 if c == '#' else 0 for c in readline().rstrip()] for i in range(H)]

    def f(v, h):
        brd = [list(C[i]) for i in range(H)]
        i = 0
        while v > 0:
            if v & 1:
                for j in range(W):
                    brd[i][j] = 0
            v >>= 1
            i += 1
        
        j = 0
        while h > 0:
            if h & 1:
                for i in range(H):
                    brd[i][j] = 0
            h >>= 1
            j += 1
        
        ret = sum(sum(row) for row in brd)
        return ret

    ans = 0
    for v in range(2 ** H):
        for h in range(2 ** W):
            if f(v, h) == K:
                ans += 1
    
    print(ans)


solve()

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
c = []
for i in range(H):
  tmp = input()
  c.append(tmp)
ans = 0
for h in range(2**H):
  h_list = []
  for i in range(H):
    if ((h >> i) & 1):
      h_list.append(i)
  for w in range(2**W):
    w_list = []
    for j in range(W):
      if ((w >> j) & 1):
        w_list.append(j)
    tmp = 0
    for i in range(H):
      for j in range(W):
        if i in h_list:
          continue
        if j in w_list:
          continue
        if c[i][j] == '#':
          tmp += 1
    if tmp == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

init_B=0
for i in range(h):
    cnt = l[i].count('#')
    init_B+=cnt

from itertools import *

ans=0
for hs in product([True,False], repeat=h):
    for ws in product([True,False], repeat=w):

        cnt=0
        for i in range(h):
            tmp = hs[i]
            if tmp: # check
                cnt += l[i].count("#")
        for j in range(w):
            tmp = ws[j]
            if tmp: # check
                for i in range(h):
                    if l[i][j] == "#" and not hs[i]:
                        cnt+=1

        if (init_B-cnt)==k:
            ans+=1
print(ans)

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 selection in product([True, False], repeat=H + W):
    row_sel = selection[:H]
    col_sel = selection[H:]
    count = 0
    for i, j in product(range(H), range(W)):
        if C[i][j] == "#" and row_sel[i] and col_sel[j]:
            count += 1
    if count == K:
        ans += 1

print(ans)