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 sys
input = sys.stdin.readline
from collections import *

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

for i in range(H):
    cnt = 0
    
    for j in range(W):
        if c[i][j]=='#':
            cnt += 1
    
    row.append(cnt)

col = []

for i in range(W):
    cnt = 0
    
    for j in range(H):
        if c[j][i]=='#':
            cnt += 1
    
    col.append(cnt)

total = sum(row)
ans = 0

for s1 in range(1<<H):
    for s2 in range(1<<W):
        l1, l2 = [], []
        
        for i in range(H):
            if (s1>>i)&1:
                l1.append(i)
        
        for i in range(W):
            if (s2>>i)&1:
                l2.append(i)
    
        now = total
        
        for l1i in l1:
            now -= row[l1i]
        
        for l2i in l2:
            now -= col[l2i]
            
        for l1i in l1:
            for l2i in l2:
                if c[l1i][l2i]=='#':
                    now += 1
        
        if now==K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
from copy import deepcopy as copy
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations, chain
setrecursionlimit(100000)

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))

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    H, W, K = map(int, input().split())
    MAP = [list(input()) for _ in range(H)]
    ans = 0
    for cols in powerset(range(H)):
        for rows in powerset(range(W)):
            MMAP = copy(MAP)
            for c in cols:
                for k in range(W):
                    MMAP[c][k] = 'r'
            for r in rows:
                for k in range(H):
                    MMAP[k][r] = 'r'
            # print(cols, rows)
            # for row in MMAP: print(*row)
            count = 0
            for i in range(H):
                for j in range(W):
                    if MMAP[i][j] == '#':
                        count += 1
            # print(count, K, ans)
            if count == K:
                ans += 1
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
def main():
    H, W, K = map(int, input().split())
    C = []
    for _ in range(H):
        c = input()
        C.append(c)
    r = 0
    for i in product(range(2), repeat=H):
        for j in product(range(2), repeat=W):
            t = 0
            for ii in range(H):
                for jj in range(W):
                    if i[ii] == 0 and j[jj] == 0 and C[ii][jj] == '#':
                        t += 1
            if t == K:
                r += 1
    return r
print(main())

Submission status: Accepted

Solution code:
from itertools import product

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

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

ans = 0
for h_bits in product((True, False), repeat=H):
    for w_bits in product((True, False), repeat=W):
        blacks = 0
        for i in range(H):
            for j in range(W):
                if h_bits[i] and w_bits[j] and C[i][j] == '#':
                    blacks += 1
        if blacks == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
def main():
    h, w, k = map(int, input().split())
    cs = [input() for _ in range(h)]
    ans = 0
    for a in product([True, False], repeat=h):
        for b in product([True, False], repeat=w):
            cnt = 0
            for i in range(h):
                if a[i]:
                    continue
                for j in range(w):
                    if b[j]:
                        continue
                    if cs[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 = [list(map(str, input())) for _ in range(h)]

ans = 0
for i in range(2**h):
    for j in range(2**w):
        H = [0]*h
        for k in range(h):
            if (i >> k) & 1:
                H[k] = 1
        W = [0]*w
        for l in range(w):
            if (j >> l) & 1:
                W[l] = 1
        cnt = 0
        for p in range(h):
            for q in range(w):
                if H[p] != 1 and W[q] != 1 and C[p][q] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
# @author 

import sys

class CHAndV:
    def solve(self, tc=0):
        h, w, k = [int(_) for _ in input().split()]
        g = []
        for i in range(h):
            g.append(list(input().strip()))

        ans = 0
        for mrow in range(1 << h):
            for mcol in range(1 << w):
                new_g = [line[:] for line in g]
                for i in range(h):
                    for j in range(w):
                        if (mrow >> i) & 1 or (mcol >> j) & 1:
                            new_g[i][j] = '0'

                cnt = 0
                for line in new_g:
                    cnt += line.count('#')

                if cnt == k:
                    ans += 1

        print(ans)




solver = CHAndV()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
for i in range(1 << h):
    for j in range(1 << w):
        t = []
        for row in s:
            t.append(row[:])
        for p in range(h):
            if (i >> p) & 1:
                for a in range(w):
                    t[p][a] = '.'
        for p in range(w):
            if (j >> p) & 1:
                for a in range(h):
                    t[a][p] = '.'
        res = 0
        for row in t:
            res += row.count('#')
        if res == k:
            ans += 1
print(ans)

Submission status: Accepted

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


ans=0
for h_bit in range(1<<H):
    for w_bit in range(1<<W):
        h_set=set()
        w_set=set()
        for i in range(H):
            if h_bit>>i&1:
                h_set.add(i)
        for i in range(W):
            if w_bit>>i&1:
                w_set.add(i)

        black=0
        for i in range(H):
            for j in range(W):
                if i not in h_set and j not in w_set and grid[i][j]=="#":
                    black+=1
        if black==K:
            ans+=1
print(ans)

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):
    for j in range(2**w):
        cnt = 0
        for ii in range(h):
            if((i >> ii)& 1):
                for jj in range(w):
                    if((j >> jj)& 1):
                        cnt += (c[ii][jj]=='#')
        ans += (cnt==k)

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import product

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

    ans = 0

    for row_bit in product(range(2), repeat=h):
        for col_bit in product(range(2), repeat=w):
            cnt = 0
            for row in range(h):
                for col in range(w):
                    if c[row][col] == "#" and (row_bit[row] and col_bit[col]):
                        cnt += 1
            if cnt == k:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product


def count(C, H, W, hselect, wselect):
    cnt = 0
    for i in range(H):
        if hselect[i]:
            continue
        for j in range(W):
            if wselect[j]:
                continue
            if C[i][j] == "#":
                cnt += 1
    return cnt


def main():
    H, W, K = map(int, input().split())
    C = [input() for _ in range(H)]
    ans = 0
    for hselect in product([True, False], repeat=H):
        for wselect in product([True, False], repeat=W):
            if count(C, H, W, hselect, wselect) == K:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    H, W, K = mi()
    c = [list(input()) for i in range(H)]
    cnt = 0

    for row in range(2**H):
        for column in range(2**W):
            tmp = [['.']*W for i in range(H)]
            for i in range(H):
                for j in range(W):
                    if (row>>i)&1 or (column>>j)&1:
                        tmp[i][j] = 'r'
                    else:
                        tmp[i][j] = c[i][j]
            s = 0
            for i in range(H):
                for j in range(W):
                    if tmp[i][j] == '#':
                        s += 1
            if s == K:
                cnt += 1
    
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

answer = 0

for hreps in range(h + 1):
    for hchosen in itertools.combinations(range(h), hreps):
        for wreps in range(w + 1):
            for wchosen in itertools.combinations(range(w), wreps):
                count = 0
                for y in hchosen:
                    for x in wchosen:
                        if C[y][x] == '#':
                            count += 1
                if count == k:
                    answer += 1

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from itertools import combinations
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    H, W, K = MAP()
    c = [input() for i in range(H)]
    ans = 0
    for wmask in range(1 << W):
        for hmask in range(1 << H):
            cnt = 0
            for w in range(W):
                if wmask & (1 << w):
                    continue
                for h in range(H):
                    if hmask & (1 << h):
                        continue
                    if c[h][w] == "#":
                        cnt += 1
            if cnt == K:
                ans += 1
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ANS=0
for i in range(1<<H):
    for j in range(1<<W):

        A=0

        for k in range(H):
            if i & (1<<k)!=0:
                continue
            for l in range(W):
                if j & (1<<l)!=0:
                    continue
                if MAP[k][l]=="#":
                    A+=1
        if A==K:
            ANS+=1
print(ANS)

Submission status: Accepted

Solution code:
import copy

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

ans = 0

N = 2 ** H
M = 2 ** W

for i in range(N):
  for j in range(M):
    cp = copy.deepcopy(c)
    for k in range(H):
      if (i >> k) & 1:
        for n in range(W):
          cp[k][n] = "."
    for k in range(W):
      if (j >> k) & 1:
        for n in range(H):
          cp[n][k] = "."
    cnt = 0
    for n in range(H):
      for m in range(W):
        if cp[n][m] == "#":
          cnt += 1
    if cnt == K:
      ans += 1

print(ans)

Submission status: Accepted

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


for i in range(2**h):
    for j in range(2**w):
        A = [[0] * w for i in range(h)]
        for ii in range(h):
            for jj in range(w):
                if C[ii][jj] == "#":
                    A[ii][jj] = 1

        # print(A)
        
        ib = format(i,"b").zfill(h)
        jb = format(j,"b").zfill(w)
        # print(ib,jb)

        for ii in range(h):
            for jj in range(w):
                if ib[ii] == "1" or jb[jj] == "1":
                    A[ii][jj] = 0

        ans0 = sum([sum(A[ii]) for ii in range(h)])
        if ans0 == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W, K = map(int, readline().split())
C = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W]

C = 1 * (C == b'#')

def f(C, x, y):
    D = C.copy()
    for i in range(H):
        if x & (1 << i):
            D[i] = 0
    for i in range(W):
        if y & (1 << i):
            D[:, i] = 0
    return D.sum() == K

ans = 0
for x in range(1 << H):
    for y in range(1 << W):
        ans += f(C, x, y)
print(ans)

Submission status: Accepted

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

grid = np.array([list(map(lambda x: x == '#',input())) for _ in range(H)])

from itertools import product

res = 0
for p in product(range(2),repeat=H+W):
    ngrid = grid.copy()
    ngrid[:,[i for i,v in enumerate(p[:W]) if v]] = 0
    ngrid[[i for i,v in enumerate(p[W:]) if v],:] = 0
    if ngrid.sum() == K:
        res += 1

print(res)

Submission status: Accepted

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

ans = 0
for tate in itertools.product([0,1], repeat=h):
    for yoko in itertools.product([0,1], repeat=w):
        cnt = 0
        for i in range(h):
            for j in range(w):
                if tate[i] or yoko[j]:continue
                cnt += C[i][j] == "#"
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
board = [list(map(lambda x: int(x=="#"), input())) for i in range(h)]

ans = 0
for i in range(1<<h):
    for j in range(1<<w):
        nboard = [board[i][:] for i in range(h)]
        for x in range(h):
            if i & (1<<x):
                for z in range(w):
                    nboard[x][z] = 0
        for y in range(w):
            if j & (1<<y):
                for z in range(h):
                    nboard[z][y] = 0
        if sum(sum(x) for x in nboard) == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

h,w,k=map(int,input().split())
c=[input() for i in range(h)]
ans=0
for gyo in product(range(2),repeat=h):
    for retsu in product(range(2),repeat=w):
            cnt=0
            # print(gyo)
            # print(retsu)
            for i in range(h):
                for j in range(w):
                    if gyo[i]==0 and retsu[j]==0 and c[i][j]=="#":
                        cnt+=1
            if cnt==k:
                ans+=1
print(ans)
# print(64*64*36)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
board = []
for _ in range(H):
    board.append(list(input()))
ans = 0
for bh in range(1 << H):
    for bw in range(1 << W):
        num = 0
        for y in range(H):
            if (bh >> y) & 1 == 0:
                continue
            for x in range(W):
                if (bw >> x) & 1 == 0:
                    continue
                if board[y][x] == '#':
                    num += 1
        if num == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

B = [[] for _ in range(H)]

for h in range(H):
    B[h] = list(input())

ans = 0
for i in range(1 << H):
    for j in range(1 << W):
        cnt = 0
        for h in range(H):
            for w in range(W):
                if ((i >> h) & 1) == 1 or ((j >> w) & 1) == 1:
                    continue
                if B[h][w] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
s = [str(input()) for i in range(h)]
ans = 0
for i in range(2 ** w):
    for j in range(2 ** h):
        a = format(i,"b").zfill(w)
        b = format(j,"b").zfill(h)
        cnt = 0
        for f in range(w):
            for g in range(h):
                if b[g] == "0" and a[f] == "0" and s[g][f] == "#":
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for rows in range(1<<H):
    for columns in range(1<<W):
        num = 0
        for i in range(H):
            for j in range(W):
                if (rows>>i) & 1 and (columns>>j) & 1:
                    if css[i][j] == '#':
                        num += 1
        if num == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W, K = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    ans = 0
    from itertools import combinations
    for i in range(H+1):
        for j in range(W+1):
            for sh in combinations(range(H), i):
                for sw in combinations(range(W), j):
                    v = 0
                    for h in sh:
                        for w in sw:
                            if c[h][w] == "#":
                                v += 1
                    if v == K:
                        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy
H,W,K=map(int,input().split())
c=[list(input()) for i in range(H)]
ans=0
for i in range(2**H):
        for k in range(2**W):
            G=deepcopy(c)
            cnt=0
            for j in range(H):
                if i>>j&1:
                    for x in range(W):
                        G[j][x]='@'
            for f in range(W):
                if k>>f&1:
                    for y in range(H):
                        G[y][f]='@'
            for j in range(H):
                for f in range(W):
                    if G[j][f]=='#':
                        cnt+=1
            if cnt==K:
                ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

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

ans = 0
for i in range(1 << H):
    for j in range(1 << W):
        val = 0
        for y in range(H):
            if i & 1 << y > 0:
                continue
            for x in range(W):
                if j & 1 << x > 0:
                    continue
                if C[y][x] == '#':
                    val += 1
        if val == 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 nh in range(2**H):
    for nw in range(2**W):
        count = 0
        for h in range(H):
            for w in range(W):
                if 2**h&nh!=2**h and 2**w&nw!=2**w and c[h][w]=='#':
                    count += 1
        if count==K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W, K = MAP()
c = [list(input()) for _ in range(H)]

ans = 0
for y in product([0, 1], repeat=H):
    for x in product([0, 1], repeat=W):
        c_copy = deepcopy(c)
        for i in range(H):
            if y[i]:
                for j in range(W):
                    c_copy[i][j] = "R"
        for i in range(W):
            if x[i]:
                for j in range(H):
                    c_copy[j][i] = "R"
        cnt = 0
        for i in range(H):
            for j in range(W):
                if c_copy[i][j] == "#":
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
H, W, K = map(int, input().split())
black = 0
C = []
for _ in range(H):
    s = input()
    black += s.count("#")
    C.append(s)

ans = 0
row = tuple(product(range(2), repeat=H))
col = tuple(product(range(2), repeat=W))

for r in row:
    for c in col:
        cnt = 0
        for i in range(H):
            for j in range(W):
                if r[i] or c[j]:
                    cnt += int(C[i][j] == "#")
        if black - cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
c=[list(map(int,list(input().replace('.','0').replace('#','1')))) for _ in range(H)]
ans=0
for i in range(2**H):
    for k in range(2**W):
        d=[c[i][:] for i in range(H)]
        for j in range(H):
            if (i>>j)&1:
                d[j]=[0]*W
        for l in range(W):
            if (k>>l)&1:
                for m in range(H):
                    d[m][l]=0
        cnt=0
        for j in range(H):
            cnt+=sum(d[j])
        ans+=cnt==K
print(ans)

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):
    for j in range(2**W):
        res = [[0 for y in range(W)] for x in range(H)]
        for x in range(H):
            for y in range(W):
                if C[x][y] == '#':
                    res[x][y] = 1
        for x in range(H):
            if (i >> x) & 1:
                for y in range(W):
                    res[x][y] = 0
        for y in range(W):
            if (j >> y) & 1:
                for x in range(H):
                    res[x][y] = 0
        tmp = 0
        for x in range(H):
            for y in range(W):
                if res[x][y]:
                    tmp += 1
        if tmp == K:
            ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for hp in product(range(2), repeat=H):
    for wp in product(range(2), repeat=W):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if hp[i] and wp[j] and C[i][j] == "#":
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

cs = [list(map(lambda c: 1 if c == '#' else 0, input())) for _ in range(H)]

count = 0
for hbits in range(1<<H):
    for wbits in range(1<<W):
        cs_copy = deepcopy(cs)
        for i in range(H):
            if (1 << i) & hbits:
                for j in range(W):
                    cs_copy[i][j] = 0
        for j in range(W):
            if (1 << j) & wbits:
                for i in range(H):
                    cs_copy[i][j] = 0
        blacks = sum(map(sum, cs_copy))
        if blacks == K:
            count += 1

print(count)

Submission status: Accepted

Solution code:
import copy
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def is_nth_bit_set(x, n):
    if x & (1 << n):
        return True
    else:
        return False


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

    return res


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

    ans = 0
    for h_pattern in range(2 ** H):
        for w_pattern in range(2 ** W):
            tmp = copy.deepcopy(C)

            for h in range(H):
                if not is_nth_bit_set(h_pattern, h):
                    continue

                for w in range(W):
                    tmp[h][w] = "r"

            for w in range(W):
                if not is_nth_bit_set(w_pattern, w):
                    continue

                for h in range(H):
                    tmp[h][w] = "r"

            c = count(tmp, H, W)
            if c == K:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

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

ans = 0
for i in range(1<<h):
    for j in range(1<<w):
        ct = 0
        for k in range(h):
            for l in range(w):
                if i>>k&1:
                    if j>>l&1:
                        if mp[k][l] == "#":
                            ct += 1
        if ct == kk:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
from copy import deepcopy
h,w,k=map(int,input().split())
c=[list(input().rstrip()) for _ in range(h)]
ans=0

for H in range(2**h):
    for W in range(2**w):
        b=deepcopy(c)
        nowh=bin(H)[2:].zfill(h)
        noww=bin(W)[2:].zfill(w)
        for hi in range(h):
            if nowh[hi]=="1":
                for i in range(w):b[hi][i]="r"
        for wi in range(w):
            if noww[wi]=="1":
                for i in range(h):b[i][wi]="r"
        cnt=0
        for i in b:
            cnt+=i.count("#")
        if cnt==k:ans+=1
print(ans)

Submission status: Accepted

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

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    h,w,k = get_nums_l()
    grid_s = [input() for _ in range(h)]

    ans = 0
    for by in range(2**h):
        for bx in range(2**w):
            c = 0

            for y in range(h):
                for x in range(w):
                    if 2**y & by == 0 and 2**x & bx == 0 and grid_s[y][x] == "#":
                        c += 1

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


main()

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
c=[input() for i in range(H)]
a=0
from itertools import product
for i in product([0,1], repeat=H):
    for j in product([0,1],repeat=W):
        t=0
        for k in range(H):
            for l in range(W):
                if i[k] and j[l] and c[k][l]=="#":
                    t+=1
        if t==K:
            a+=1
print(a)

Submission status: Accepted

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

ans = 0
for bit_h in range(1 << h):
    for bit_w in range(1 << w):
        cnt = 0
        for i in range(h):
            for j in range(w):
                if (bit_h >> i) & 1 == 1 or (bit_w >> j) & 1 == 1:
                    continue
                if c[i][j] == '#':
                    cnt += 1
        if cnt == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

H,W,K = map(int,readline().split())
grid = [readline().rstrip() for i in range(H)]
ans = 0
for i in range(2**H):
    for j in range(2**W):
        cnt = 0
        for h in range(H):
            for w in range(W):
                if (i>>h)&1 and (j>>w)&1 and grid[h][w] == '#':
                    cnt += 1
        if K == cnt:
            ans += 1
print(ans)