Problem:


Score : 300 points

Problem Statement

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

Consider doing the following operation:

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

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

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

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

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

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

Sample Output 4

208



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


Sample output:
5

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
c = [list(input()) for _ in range(h)]
cnt = 0
for i in range(h):
    cnt += c[i].count("#")
ans = 0
for bit_i in range(2 ** h):
    h_check = []
    h_cnt = 0
    for i in range(h):
        if bit_i >> i & 1:
            h_cnt += c[i].count("#")
            h_check.append(i)
    for bit_j in range(2 ** w):
        w_cnt = 0
        for j in range(w):
            if bit_j >> j & 1:
                for y in range(h):
                    if c[y][j] == "#" and  y not in h_check:
                        w_cnt += 1
        if h_cnt + w_cnt == cnt - k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
H,W,K = map(int,input().split())
C = list()
HL = list(itertools.product(range(2), repeat=H))
WL = list(itertools.product(range(2), repeat=W))
for i in range(H):
    tmp = input()
    C.append(tmp)

ret = 0
for h in HL:
    for w in WL:
        count = 0
        for i in range(H):
            if h[i] == 1:
                for j in range(W):
                    if w[j] == 1 and C[i][j] == '#':
                        count += 1
        if count == K:
            ret += 1
print(ret)

Submission status: Accepted

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

tate = [0 for _ in range(w)]
yoko = [0 for _ in range(h)]
sumblack = 0
for i in range(h):
    for j in range(w):
        if color[i][j] == '#':
            tate[j] += 1
            yoko[i] += 1
            sumblack += 1

# print(tate)
# print(yoko)
ans = 0
for i in range(2**h):
    for j in range(2**w):
        tmp = sumblack 
        for a in range(h):
            if (i >> a) & 1:
                tmp -= yoko[a]
        for b in range(w):
            if (j >> b) & 1:
                tmp -= tate[b]
                for aa in range(h):
                    if (i>>aa)&1 and color[aa][b]=='#':
                        tmp += 1
        if tmp == k:
            # print(i,j)
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from itertools import accumulate
import copy


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline()[:-1] for _ in range(line)]


H, W, K = zz()
C = []
for h in range(H):
    tmp = S()
    value = []
    for _tmp in tmp[:-1]:
        if (_tmp == '#'):
            value.append(1)
        else:
            value.append(0)
    C.append(value)

C = np.array(C)
ans = 0
for h in itertools.product([0, 1], repeat=H):
    for w in itertools.product([0, 1], repeat=W):
        tmp_C = copy.copy(C)

        for i, _h in enumerate(h):
            if (_h == 1):
                tmp_C[i, :] = 0
        for i, _w in enumerate(w):
            if (_w == 1):
                tmp_C[:, i] = 0
        if (np.sum(tmp_C) == K):
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key
from copy import deepcopy as dc

INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    H, W, K = mulinputs()
    cs = []
    for _ in range(H):
        cs.append(input())

    def count(arr):
        _cnt = 0
        for line in arr:
            for ch in line:
                if ch != '#':
                    continue
                _cnt += 1
        return _cnt

    for i in range((1<<H)-1):
        for j in range((1<<W)-1):
            h, w, _i, _j = [], [], i, j
            while _i > 0:
                h.append(_i%2)
                _i >>= 1
            while _j > 0:
                w.append(_j%2)
                _j >>= 1
            _cs = dc(cs)
            if h:
                for idx, _h in enumerate(h):
                    _cs[idx] = 'r' * W if _h else _cs[idx]
            if w:
                for idx, _w in enumerate(w):
                    if not _w:
                        continue
                    for cidx in range(len(_cs)):
                        tmp = ''
                        for ii, ch in enumerate(_cs[cidx]):
                            tmp += 'r' if ii == idx else ch
                        _cs[cidx] = tmp
            if count(_cs) == K:
                cnt += 1

    # 出力
    print(cnt)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
import copy
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    h, w, K = mi()
    c = [list(input().rstrip()) for _ in range(h)]
    count = 0
    for i in range(h):
        for j in range(w):
            if c[i][j] == "#":
                c[i][j] = 1
                count += 1
            else:
                c[i][j] = 0
    
    ans = 0
    for i in range(1<<h):
        for j in range(1<<w):
            tmp = copy.deepcopy(c)
            for k in range(h):
                if i>>k & 1:
                    for l in range(w):
                        tmp[k][l] = 0
            for k in range(w):
                if j>>k & 1:
                    for l in range(h):
                        tmp[l][k] = 0
            s = 0
            for t in tmp:
                s += sum(t)
            if s == K:
                ans += 1

    print(ans)

    return

main()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product


def main():
    h, w, k = map(int, input().split())
    grid = np.full((h, w), False, dtype=bool)
    for i in range(h):
        line = input()
        for j in range(w):
            if line[j] == '#':
                grid[i][j] = True
    ans = 0
    for e in product((True, False), repeat=h + w):
        grid_copy = np.copy(grid)
        for i in range(h):
            if e[i]:
                grid_copy[i, :] = False
        for j in range(w):
            if e[h + j]:
                grid_copy[:, j] = False
        if np.sum(grid_copy) == k:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import collections

    h,w,k = map(int,input().split())
    c = []
    total = 0
    for i in range(h):
        cc = list(input())
        c.append(cc)
        total += collections.Counter(cc)['#']
    from itertools import combinations
    r = list(range(0,h))
    col = list(range(0,w))
    # t = collections.Counter(c)
    # total = t['#']
    ans = 0

    for i in range(h+1):
        for row in list(combinations(r, i)):
            rcnt = collections.Counter(row)
            for j in range(w+1):
                for co in list(combinations(col, j)):
                    ccnt = collections.Counter(co)

                    sumr = 0
                    for kk in row:
                        for l in c[kk]:
                            if l == '#':
                                sumr+=1

                    for kk in co:
                        for l in range(h):
                            if c[l][kk] == '#' and l not in row:
                                sumr+=1
                    
                    if total - sumr == k:
                        ans += 1
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[]
for _ in range(h): c+=[input()]
ch,cw=[0]*h,[0]*w
for i in range(h):
  ch[i]=c[i].count('#')
for i in range(w):
  for j in range(h):
    cw[i]+=(c[j][i]=='#')
x=sum(ch)-k
a=0
for i in range(2**h):
  for j in range(2**w):
    t=0
    for k in range(h):
      if i>>k&1:
        t+=ch[k]
        for l in range(w):
          if j>>l&1: t-=(c[k][l]=='#')
    for l in range(w):
      if j>>l&1: t+=cw[l]
    if t==x: a+=1
print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h,w,k = list(map(int,input().split()))
c = [list(input()) for _ in range(h)]
black_total  = 0
row_black_cnt = []
col_black_cnt = []
for ci in c:
    row_black_cnt.append(ci.count("#"))
    black_total+=ci.count("#")

for cj in zip(*c):
    col_black_cnt.append(cj.count("#"))

cc = []
for i in c:
    tmp = []
    for j in i:
        if j =="#":
            tmp.append(1)
        else:
            tmp.append(0)
    cc.append(tmp)
from itertools import product
row_itrt = list(product([0,1],repeat=h))
col_itrt = list(product([0,1],repeat=w))

ret = 0
for row_ptn in row_itrt:
    row_ptn = [i for i,v in enumerate(row_ptn) if v==1]
    for col_ptn in col_itrt:
        cnt = black_total
        col_ptn = [i for i,v in enumerate(col_ptn) if v==1]
        for r in row_ptn:
            for c in col_ptn:
                cnt += cc[r][c]
        for r in row_ptn:
            cnt -= row_black_cnt[r]
        for c in col_ptn:
            cnt -= col_black_cnt[c]
        if cnt==k:
            ret+=1

print(ret)

Submission status: Accepted

Solution code:
from copy import deepcopy

h,w,K=map(int,input().split())
lst=[]
for i in range(h):
    c=list(input())
    lst.append(c)
ans=0
for i in range(2**(h+w)):
    nuri=[[],[]]
    count_h=0
    count_w=0
    for j in range(h+w):
        if ((i>>j)&1):
            if j<h:
                nuri[0].append(j)
                count_h+=1
            else:
                nuri[1].append(j-h)
                count_w+=1
    c_lst=deepcopy(lst)
    for j in range(count_h):
        for k in range(w):
            if c_lst[nuri[0][j]][k]=="#":
                c_lst[nuri[0][j]][k]="."
    for j in range(count_w):
        for k in range(h):
            if c_lst[k][nuri[1][j]]=="#":
                c_lst[k][nuri[1][j]]="."
    num_shapu=0
    for j in c_lst:
        for k in j:
            if k=="#":
                num_shapu+=1
    if num_shapu==K:
        ans+=1
print(ans)

Submission status: Accepted

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

x = [i.count('#') for i in c]
y = [[i[j] for i in c].count('#') for j in range(w)]
z = sum(x)
r = 0
for i in range(2**h):
    s = []
    num = i
    for _i in range(h):
        if num%2==1:
            s.append(_i)
        num >>= 1
    for j in range(2**w):
        num = j
        t = []
        for _j in range(w):
            if num%2==1:
                t.append(_j)
            num >>= 1
        if s==[] and t==[]:
            if k == z:
                r += 1
        elif s == []:
            counter = sum(y[n] for n in t)
            if z-counter == k:
                r += 1
        elif t == []:
            counter = sum(x[n] for n in s)
            if z-counter == k:
                r += 1
        else:
            counter = sum(x[n] for n in s) + sum(y[m] for m in t)
            for nn in s:
                for mm in t:
                    if c[nn][mm] == '#':
                        counter -= 1
            if z-counter == k:
                r += 1

print(r)

Submission status: Accepted

Solution code:
import sys

H, W, K = map(int, sys.stdin.readline().strip().split())
grid = []
for _ in range(H):
    grid.append(list(sys.stdin.readline().strip()))
# print(grid)

ans = 0
for i in range(2**H):
    for j in range(2**W):
        tmp = 0
        for y in range(H):
            for x in range(W):
                if ((j >> x) & 1) or ((i >> y) & 1):
                    # print(x, j, y, i) 
                    continue
                # if i == 0 or j == 0:
                #     print("(0,0)", i, j)
                if grid[y][x] == "#":
                    tmp += 1
        # print(i, j, tmp)
        if tmp == K:
            # print(i, j)
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools


hwk = input().split(' ')

h = int(hwk[0])
w = int(hwk[1])
k = int(hwk[2])

mat = np.zeros([h, w])

for i in range(h):
  tmp_row_str = input()
  tmp_row = np.array([1 if tmp_row_str[j] == '#' else 0 for j in range(w)])
  mat[i] = tmp_row

count = 0

sum_rows = mat.sum(axis=0)
sum_cols = mat.sum(axis=1)

sum_total = mat.sum()

row_combs = itertools.product([0, 1], repeat=h)
col_combs = list(itertools.product([0, 1], repeat=w))

count = 0


for row_comb in row_combs:
  #col_combs = itertools.product([0, 1], repeat=w)
  for col_comb in col_combs:
    tmp_mat = mat.copy()
    tmp_mat[np.array(row_comb).astype('bool')] = 0
    tmp_mat[:, np.array(col_comb).astype('bool')] = 0

    
    if tmp_mat.sum() == k:
      count += 1

print(count)

"""
while True:
  if sum_total == k:
    print(1)
    break
  #まず列から
"""

Submission status: Accepted

Solution code:
import sys
import numpy as np

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7

H, W, K = map(int, sys.stdin.readline().rstrip().split())
C = []
for _ in range(H):
    C.append([0 if s == "." else 1 for s in sys.stdin.readline().rstrip()])

A = np.array(C)
# print(A, A.sum())

ans = 0
for i in range(2**H):
    for j in range(2**W):
        A = np.array(C)

        for row in range(H):
            if (i >> row) & 1 == 1:
                A[row, :] = 0

        for col in range(W):
            if (j >> col) & 1 == 1:
                A[:, col] = 0

        # print(i,j)
        # print(A, A.sum())

        if A.sum() == K:
            ans += 1

print(ans)

Submission status: Accepted

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

ans = 0

def cnt(a, h, w):
    global ans
    ret = 0
    for i,s in enumerate(a):
        if h[i]!=0:
            continue
        for j,c in enumerate(s):
            if w[j] !=0:
                continue
            ret += 1 if c == "#" else 0
    if K == ret:
        ans += 1

def hf(h):
    if len(h) == H:
        wf(h,[])
        return
    hf(h+[0])
    hf(h+[1])

def wf(h,w):
    if len(w) == W:
        cnt(c, h, w)
        return
    wf(h, w+[0])
    wf(h, w+[1])

hf([])
print(ans)

Submission status: Accepted

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

c = [[] for _ in range(H)]
s = [[] for _ in range(H)]
t = [[] for _ in range(W)]

for i in range(H):
    c[i] = input()
for i in range(H):
    s[i] = c[i].count("#")

num_total = 0

for j in range(W):
    t[j] = 0
    for i in range(H):
        if c[i][j] == "#":
            t[j] += 1
            num_total += 1


ans = 0
for i in range(2**len(s)):
    num0 = 0
    for j in range(len(s)):
        if ((i >> j) & 1):
            num0 += s[j]
    for k in range(2**len(t)):
        num = num0
        for l in range(len(t)):
            if ((k >> l) & 1):
                num += t[l]
                for j in range(len(s)):
                    if ((i >> j) & 1):
                        if c[j][l] == "#":
                            num -= 1
        if num_total - num == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
C = [[0 for i in range(W)] for j in range(H)]
for j in range(H):
  c = input()
  for i in range(W):
    if c[i] == "#":
      C[j][i] = 1
ans = 0
P = [0 for k in range(H + W)]

while 1:
  S = 0
  for j in range(H):
    for i in range(W):
      if P[j] == 0 and P[H + i] == 0:
        S += C[j][i]
  if S == K:
    ans += 1
  if sum(P) == H + W:
    break
  a = 1
  for k in range(H+W):
    b = (P[k] + a) // 2
    P[k] = (P[k] + a) % 2
    a = b
print(ans)

Submission status: Accepted

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

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

ans = 0
for bit_h in range(1, 1 << H):
    b_h = [i for i in range(H) if bit_h & (1 << i)]

    for bit_w in range(1, 1 << W):
        b_w = [i for i in range(W) if bit_w & (1 << i)]
        acc = (C[b_h][:, b_w] == "#").sum()
        if acc == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

data = [0, 1]

h, w, k = map(int, input().split())
countA = 0
gyoL = [0]*h  # 1gyo, 2gyo...
retuL = [0]*w  # 1retu, 2retu...
cL = []
for i in range(h):
    inputL = list(input())
    countSum = 0
    for l in range(w):
        if inputL[l] == "#":
            countA+=1
            countSum += 1
            retuL[l] += 1
    gyoL[i] = countSum
    cL.append(inputL)

gyo = list(itertools.product(data, repeat=h))
retu = list(itertools.product(data, repeat=w))

ansC = 0
for tG in gyo:
    for tR in retu:
        count = countA
        gOneL = []
        rOneL = []
        for index1 in range(len(tG)):
            if tG[index1] == 1:
                count-=gyoL[index1]
                gOneL.append(index1)
        for index2 in range(len(tR)):
            if tR[index2] == 1:
                count-=retuL[index2]
                rOneL.append(index2)
        for g in gOneL:
            for r in rOneL:
                if cL[g][r] == "#":
                    count += 1
        if count == k:
            ansC+=1
print(ansC)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np
from itertools import combinations as comb
h, w, k = map(int, input().split())
a = np.array([list(input()) for _ in [None]*h])
cnt = 0
for j1 in range(h):
    for i1 in comb(range(h), j1):
        for j2 in range(w):
            for i2 in comb(range(w), j2):
                c = np.copy(a)
                c = np.delete(c, list(i1), 0)
                c = np.delete(c, list(i2), 1)
                cnt += np.count_nonzero(c == '#') == k
print(cnt)

Submission status: Accepted

Solution code:
aa=input("").split(" ")
a=[]
for i in range(3):
    a+=[int(aa[i])]
    
    
b=[]
for i in range(a[0]):
    b+=[input("")]
c=[]
for i in range(a[0]):
    d=[]
    for k in b[i]:
        if (k=="."):
            d+=[0]
        else:
            d+=[1]
    c+=[d]
def count(n,m):
    s=0
    for i in range(a[0]):
        for k in range(a[1]):
            if (c[i][k]==1 and n[i]==1 and m[k]==1):
                s+=1
    return s
ss=0
for ii in range(2**a[0]):
    for kk in range(2**a[1]):
        d=ii
        e=kk
        n=[]
        m=[]
        for iii in range(a[0]):
            n+=[d%2]
            d=int((d/2))
        for kkk in range(a[1]):
            m+=[e%2]
            e=int(e/2)
        if (count(n,m)==a[2]):
            ss+=1
print(ss)

Submission status: Accepted

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

for i in range(2 ** (h+w)):
    ans = 0
    a,b = [],[]
    for j in range(h+w):
        if ((i >> j) & 1):
            if j < h:
                a.append(j)
            else:
                b.append(j-h)
    for k in range(h):
        for l in range(w):
            if c[k][l] == '#' and k in a and l in b:
                ans += 1
    if ans == K:
        count += 1
print(count)

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):
    bin_i = format(i, f'0{H}b')
    for j in range(2**W):
        bin_j = format(j, f'0{W}b')
        count = 0
        for ii in range(H):
            if bin_i[ii] == '1':
                continue
            for jj in range(W):
                if bin_j[jj] == '1':
                    continue
                if c[ii][jj] == '#':
                    count+=1
        if count == K:
            ans+=1
print(ans)

Submission status: Accepted

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

n=h + w
b=[]
for s in range(2**n):
    a=[1 if s >> i &1 else 0 for i in range(n)] 
    b.append(a)

from copy import deepcopy
count = 0

for part_b in b:
    m =0
    d = deepcopy(c)
    row = part_b[:h]
    col = part_b[h:]
    for i in range(len(row)):
        flg = row[i]
        if flg:
            d[i] = ["赤" for _ in range(w)]
    
    for i in range(len(col)):
        flg = col[i]
        if flg:
            for j in range(h):
        
                d[j][i]= "赤"
                
    for i in range(h):
        for j in range(w):
            if d[i][j] == "#":
                m +=1
    if m==k:
        count +=1
print(count)

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	h,w,k=MI()
	G=[]
	for _ in range(h):
		G.append(list(input()))
	#print(G)
	ans=0

	for i in range(1<<h):
		for j in range(1<<w):
			cnt=0
			for ii in range(h):
				for jj in range(w):
					#print(i,j,ii,jj,)
					if i&1<<ii and j&1<<jj and G[ii-1][jj-1]=="#":
						#print(1<<i)
						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 = [ "" for _ in range(H) ]
cx = [ 0 for _ in range(H) ]
cy = [ 0 for _ in range(W) ]
for i in range(H):
  C[i] = input()
  for j in range(W):
    if C[i][j] == "#":
      cx[i] |= 1 << j
ans = 0
for y in range( 1<<H ):
  for x in range( 1<<W ):
    total = 0
    for i in range(H):
      if ( (y & (1<<i)) != 0 ):
        for j in range(W):
          if ((cx[i] & x) & (1<<j)) != 0:
            total += 1
    if total == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
"""
AtCoder :: Beginner Contest 173 :: H and V
https://atcoder.jp/contests/abc173/tasks/abc173_c
"""
import sys
from itertools import chain, combinations


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():
    """Main program."""
    height, width, target = (int(i) for i in sys.stdin.readline().split())
    grid = [[0 for _ in range(width)] for _ in range(height)]
    total_black = 0
    for row in range(height):
        for col, color in enumerate(sys.stdin.readline().strip()):
            if color == '#':
                grid[row][col] = 1
                total_black += 1

    soln = 0
    for rows_selected in powerset(range(height)):
        for cols_selected in powerset(range(width)):
            if len(cols_selected) == width:
                continue

            selected_black = 0
            for row in rows_selected:
                selected_black += sum(grid[row])

            for col in cols_selected:
                for row in range(height):
                    if row not in rows_selected:
                        selected_black += grid[row][col] 

            if total_black - selected_black == target:
                soln += 1
    print(soln)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
#======================================================#
def main():
    h, w, k = MII()
    cc = [IS() for _ in range(h)]
    all_blacks = 0
    for c in cc:
        all_blacks += sum(1 for s in c if s == '#')
    cnt = 0
    for hbit in range(1<<h):
        blacks = all_blacks
        hb = []
        # 行を選ぶ
        for i in range(h):
            if hbit & (1<<i):
                hb.append(i)
        # 選んだ行の黒を取り除く
        for hbi in hb:
            blacks -= sum([1 for s in cc[hbi] if s == '#'])
        # すでにk個以下であればskip
        if blacks < k:
            continue

        # 列を選択
        for wbit in range(1<<w):
            wb = []
            for i in range(w):
                if wbit & (1<<i):
                    wb.append(i)
            # 列の黒を取り除く（ただし横で選んだ部分は重複させない）
            wblack = 0
            for wbi in wb:
                for i in range(h):
                    # 行で選ばれている場合はスキップ
                    if i in hb:
                        continue
                    if cc[i][wbi] == '#':
                        wblack += 1
            if blacks - wblack == k:
                cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W, K = mapint()

rows = [0]*H
query = []
allcnt = 0
for h in range(H):
    Cs = list(input())
    query.append(Cs)
    cnt = sum([1 if i=='#' else 0 for i in Cs])
    rows[h] = cnt
    allcnt += cnt
ans = 0
for i in range(1<<H):
    skip = set()
    num = 0
    for h in range(H):
        if (i>>h)&1:
            skip.add(h)
            num += rows[h]
    for j in range(1<<W):
        num2 = num
        for w in range(W):
            if (j>>w)&1:
                for h2 in range(H):
                    if h2 in skip:
                        continue
                    if query[h2][w]=='#':
                        num2 += 1
        if allcnt-num2==K:
            ans += 1
print(ans)