Problem:


Score : 300 points

Problem Statement

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

Consider doing the following operation:

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

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

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

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

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

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

Sample Output 4

208



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


Sample output:
5

Submission status: Accepted

Solution code:
import itertools

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

hlist = []
for i in range(H+1):
    hlist += list(itertools.combinations(range(H), i))
wlist = []
for i in range(W+1):
    wlist += list(itertools.combinations(range(W), i))

answer = 0
for hchoice in hlist:
    for wchoice in wlist:
        count = 0
        for row in hchoice:
            for col in wchoice:
                if C[row][col]=='#':
                    count += 1
        if count == K:
            answer += 1
print(answer)

Submission status: Accepted

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


def count(h_mask, w_mask):
    sum_ = 0
    
    for i in range(h):
        if h_mask & 2 ** i != 0:
            continue
        for j in range(w):
            if w_mask & 2 ** j != 0:
                continue
            else:
                if c[i][j] == "#":
                    sum_ += 1

    if sum_ == k:
        return 1
    else:
        return 0


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

res = 0

for i in range(2 ** h):
    for j in range(2 ** w):
        res += count(i, j)

print(res)

Submission status: Accepted

Solution code:
import itertools 

H, W, K = map(int, input().split())
C = []
HS = []
WS = []
T = 0

def f(x):
  if x == "#":
    return 1
  else:
    return 0

for i in range(H):
  X = list(input())
  c = [f(x) for x in X]
  C.append(c)
  HS.append(sum(c))
  T += sum(c)

for j in range(W):
  cnt = 0
  for i in range(H):
    cnt += C[i][j]
  WS.append(cnt)
  
ans = 0

for h in itertools.product([0, 1], repeat = H):
  for w in itertools.product([0, 1], repeat = W):
    cnt = 0
    for i in range(H):
      if h[i] == 1:
        cnt += HS[i]
    for j in range(W):
      if w[j] == 1:
        cnt += WS[j]
    for i in range(H):
      for j in range(W):
        if h[i] == 1 and w[j] == 1:
          cnt -= C[i][j]
    if T - cnt == K:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math  # noqa: F401
from collections import deque  # noqa: F401
from itertools import combinations
from typing import Deque, Dict, List, Optional, Tuple, Union  # noqa: F401

import numpy as np


def count_sharp(C: List[List[str]]) -> int:
    n = 0
    for row in C:
        for e in row:
            if e == "#":
                n += 1
    return n


def main(H: int, W: int, K: int, C: List[List[str]]):
    ans = 0

    h_list = [x for x in range(0, H)]
    w_list = [x for x in range(0, W)]

    for num_row in range(H):
        for num_col in range(W):
            row_combs = list(combinations(h_list, num_row))
            col_combs = list(combinations(w_list, num_col))

            for row_comb in row_combs:
                for col_comb in col_combs:
                    C_np = np.array(C)
                    for row in row_comb:
                        C_np[row, :] = "*"
                    for col in col_comb:
                        C_np[:, col] = "*"

                    if count_sharp(C_np) == K:
                        ans += 1

    print(ans)


if __name__ == "__main__":
    H, W, K = map(int, input().split())
    C: List[List[str]] = []

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

    main(H, W, K, C)

Submission status: Accepted

Solution code:
def bit_fullsearch(target):
    n = len(target)
    ret = []
    for i in range(2**n):
        tmp = []
        for j in range(n):
            if (i>>j)&1:
                tmp.append(target[j])
        ret.append(tmp)
    return ret

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

col = [i for i in range(h)]
row = [j for j in range(w)]

col = bit_fullsearch(col)
row = bit_fullsearch(row)

now = 0
ans = 0
for i in range(h):
    for j in range(w):
        if C[i][j]=='#':
            now += 1
for y in col:
    for x in row:
        tmp = 0
        for i in range(h):
            for j in range(w):
                flg = False
                if i in y:
                    flg = True
                if j in x:
                    flg = True
                if flg and C[i][j]=='#':
                    tmp += 1
        if now - tmp == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
import copy


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    c_arr = []
    for i in range(H):
        _ = list(_in[i + 1])  # type:list(str)
        c_arr.append(_)
    c_arr = np.array(c_arr)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    c_arr[c_arr == '#'] = 1
    c_arr[c_arr == '.'] = 0
    c_arr = c_arr.astype(np.int8)

    ans = 0

    # 列方向
    for bitw in range(1 << W):
        for bith in range(1 << H):
            board = copy.deepcopy(c_arr)
            # bit = 1: selected
            for i in range(W):
                if bitw & (1 << i):
                    board[:, i] *= 0
            for i in range(H):
                if bith & (1 << i):
                    board[i, :] *= 0
            black = board.sum()
            if black == K:
                ans += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

from copy import deepcopy
ans = 0
for i in range(pow(2, H + W)):
    c_copy = deepcopy(c_list)
    for w in range(W):
        if (i & pow(2, H + w)) > 0:
            for h in range(H):
                c_copy[h] = c_copy[h][:w] + 'x' + c_copy[h][w+1:]
    cnt = 0
    for h in range(H):
        if (i & pow(2, h)) > 0:
            c_copy[h] = 'x' * W
        cnt += c_copy[h].count('#')
    if cnt == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
from itertools import product


h, w, k = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = 0
for x in product((0, 1), repeat=h):
    for y in product((0, 1), repeat=w):
        b = copy.deepcopy(c)
        for i in range(h):
            if x[i] == 1:
                for tate in range(w):
                    # print(tate)
                    b[i][tate] = "S"

        for j in range(w):
            if y[j] == 1:
                for yoko in range(h):
                   # print(yoko, j)
                    b[yoko][j] = "S"
        count = 0
        for i in range(h):
            count += b[i].count("#")

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

Submission status: Accepted

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

cnt=0
for i in range(2**h):
  for j in range(2**w):
    tmp=cp(l)
    for b in range(h):
      if (i>>b)&1:
        tmp[b]=['.']*w
    for b in range(w):
      if (j>>b)&1:
        for c in range(h):
          tmp[c][b]='.'
    black=0
    for r in tmp:
      black+=r.count('#')
    if black==k:
      cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
h, w, k = map(int, input().split())
cnt = 0
mass = []
for _ in range(h):
    s = list(str(input()))
    mass.append(s)
    
mass = np.array(mass)
for i in range(h+1):
    row_list = list(combinations(range(h), i))
    for j in range(w+1):
        col_list = list(combinations(range(w), j))
        for r_choice in row_list:
            for c_choice in col_list:
                tmp_mass = mass.copy()
                tmp_mass[list(r_choice), :] = "r"
                tmp_mass[:, list(c_choice)] = "r"
                if (tmp_mass == "#").sum() == k:
                    cnt += 1
      
print(cnt)

Submission status: Accepted

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

ans = 0
for i in range(2 ** (h + w)):
    d = copy.deepcopy(c)
    for j in range(h + w):
        if i >> j & 1:
            if 0 <= j < h:
                for k in range(w):
                    d[j][k] = "."
            else:
                for k in range(h):
                    d[k][j - h] = "."
    #print(d)
    cnt = 0
    for l in range(h):
        cnt += d[l].count("#")
    if cnt == x:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
## coding: UTF-8
from itertools import product
import copy

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

#sheet = [ [1] * W for _ in range(H)]
sheet = []
for i in range(H):
    s = input()
    ret = []
    for j in range(W):
        if(s[j] == '#'):
            ret.append(1)
        else:
            ret.append(0)
    sheet.append(ret)

#print(sheet)

pattern = list(product('YN', repeat = H+W))
#print(pattern)


ans = 0
for _ in range(len(pattern)):
    #town = []
    #for i in range(H):
        #town.append(sheet[i])
    town = copy.deepcopy(sheet)
    #print(town, sheet)
    now = pattern[_]
    #print(now)
    for i in range(H):
        #yoko
        if(now[i] == 'Y'):
            town[i] = [0] * W
    #print(town)
    for i in range(H, H+W):
        #tate
        if(now[i] == 'Y'):
            for j in range(H):
                town[j][i-H] = 0
    #print(town)
    #print('~~~~~~~~~~~~~')
    su = 0
    for i in range(H):
        su += sum(town[i])
    if(su == K):
        ans += 1

    
print(ans)

Submission status: Accepted

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

# print(h,w,k)
# print(*C,sep='\n',end='\n---\n')

ans = 0
for hbit in range(1<<h): # red row bit
    for wbit in range(1<<w): # red col bit
        c = 0
        for i in range(h):
            for j in range(w):
                if hbit>>i & 1 and wbit>>j & 1:
                    if C[i][j] =='#': c += 1
        if c == k: ans += 1

print(ans)

Submission status: Accepted

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

edge = [["#" for _ in range(W+2)]]
center = [["#"] + list(input()) + ["#"] for i in range(H)] #提出用

c = edge + center + edge

N = H + W
ans = 0

for i in range(2**(N)):
    bit_array = str(bin(i)[2:]).zfill((N))
    #print(bit_array)
    black = 0
    #bit_arrayをH,W分にそれぞれ分解
    H_bit = [0] + list(bit_array[0:H])
    W_bit = [0] + list(bit_array[H:])
    #print(H_bit,W_bit)

    for j in range(1,H+1):
        if H_bit[j] != "1":
            for k in range(1,W+1):
                if W_bit[k]!="1" and c[j][k]=="#":
                    black += 1
        if black > K:
            break
    
    if black == K:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product as pro

h,w,K=map(int,input().split())
C=[]
for _ in range(h):
    C.append(list(str(input())))



L=['0','1']
Sh=pro(L,repeat=h)


ans=0
for i in Sh:
    Sw=pro(L,repeat=w)
    for j in Sw:
        temp=0

        for k in range(h):
            for l in range(w):
                if i[k]=='0' and j[l]=='0':
                    if C[k][l]=='#':
                        temp+=1
        
        if temp==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 i in range(1<<H):
    for j in range(1<<W):
        cnt = 0
        for k in range(H):
            for l in range(W):
                if i & 1 << k or j & 1 << l: continue
                if c[k][l] == '#':
                    cnt += 1
        
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
h, w, k = map(int, input().split())
s = []

total = 0
hcnt = [0 for i in range(h)]
wcnt = [0 for i in range(w)]
for i in range(h):
  c = input()
  hcnt[i] = c.count('#')
  total += c.count('#')
  s.append(c)

for i in range(w):
  cnt = 0
  for j in range(h):
    if s[j][i] == '#':
      cnt += 1
  wcnt[i] = cnt

ans = 0
for i in itertools.product([0,1], repeat=h):
  for j in itertools.product([0,1], repeat=w):
    cnt = 0
    for a in range(h):
      for b in range(w):
        if i[a] == 1 and j[b] == 1:
          if s[a][b] == '#':
            cnt += 1
    if cnt == k:
      ans += 1
print (ans)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
C = []
for _ in range(H):
    C.append(input())
res = 0
for i in range(2**W):
    for j in range(2**H):
        tmp = 0
        for h in range(H):
            for w in range(W):
                if bin(i)[2:].zfill(W)[w] == '0' and bin(j)[2:].zfill(H)[h] == '0' and C[h][w] == '#':
                    tmp += 1
        if tmp == K:
            res += 1

print(res)

Submission status: Accepted

Solution code:
from copy import copy
import numpy as np

H,W,K=map(int,input().split())
c=np.array([list(input()) for _ in range(H)])
red_h=np.array(["R"]*W)
red_w=np.array(["R"]*H).reshape((H,1))

ans=0
for i in range(2**H):
    tmp1=copy(c)
    for j in range(H):
        if i%2==1:
            tmp1[j,:]=red_h
        i//=2
    for k in range(2**W):
        tmp2=copy(tmp1)
        cnt=0
        for l in range(W):
            if k%2==1:
                tmp2[:,l]=red_w[:,0]
            k//=2
    
        for h in range(H):
            for w in range(W):
                if tmp2[h,w]=="#":
                    cnt+=1
        if cnt==K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def bit_indexes(x):
    i = 0
    while x != 0:
        if x%2 != 0:
            yield i
        x //= 2
        i += 1
    

def solve():
    H, W, K = read_ints()
    C = []
    black_count = 0
    for i in range(H):
        C.append(input().strip())
        black_count += C[-1].count('#')
    ans = 0
    for i in range(2**H):
        for j in range(2**W):
            count = black_count
            for i0 in bit_indexes(i):
                for j0 in range(W):
                    if C[i0][j0] == '#':
                        count -= 1
            for j0 in bit_indexes(j):
                for i0 in range(H):
                    if C[i0][j0] == '#':
                        count -= 1
            for i0 in bit_indexes(i):
                for j0 in bit_indexes(j):
                    if C[i0][j0] == '#':
                        count += 1
            if count == K:
                ans += 1
    return ans


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
from itertools import chain,combinations, product
from copy import deepcopy

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

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

pset = product(powerset(range(h)), powerset(range(w)))
ans = 0
for vert, hori in pset:
    D = deepcopy(C)
    for i in vert:
        for j in range(w):
            D[i][j] = 'r'
    for i in range(h):
        for j in hori:
            D[i][j] = 'r'
    count = sum(D[i].count('#') for i in range(h))
    if count == k:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd, cos, radians, floor
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
h, w, k2 = map(int, input().split())
c = [[j for j in input()] for i in range(h)]
ans = 0
for i in range(1 << (h + w)):
    bit = bin(i)[2:].zfill(h + w)
    bit1 = bit[:h]
    bit2 = bit[h:]
    cnt = [[0 for _ in range(w)] for _ in range(h)]
    for j in range(h):
        if bit1[j] == "1":
            for k in range(w):
                cnt[j][k] = 1
    for j in range(w):
        if bit2[j] == "1":
            for k in range(h):
                cnt[k][j] = 1
    
    cnt2 = 0
    for j in range(h):
        for k in range(w):
            if c[j][k] == "#" and cnt[j][k] == 0:
                cnt2 += 1
    if cnt2 == k2:
        # # print("k =", k)
        # for j in range(h):
        #     for k in range(w):
        #         if c[j][k] == "#" and cnt[j][k] == 0:
        #             print(j, k)
        #             # cnt2 += 1

        # # print()
        # for j in range(h):
        #     for k in range(w):
        #         print(cnt[j][k], end =" ")
        #     print()
        # print()
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

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

hpattern = []
for i in range(2 ** h):
    temp = [0] * h
    for j in range(h):
        if i >> j & 1:
            temp[j] = 1
    hpattern.append(temp)

wpattern = []
for i in range(2 ** w):
    temp = [0] * w
    for j in range(w):
        if i >> j & 1:
            temp[j] = 1
    wpattern.append(temp)

ans = 0
for hp in hpattern:
    for wp in wpattern:
        cc = copy.deepcopy(c)
        for i in range(h):
            for j in range(w):
                if hp[i] == 1:
                    cc[i][j] = -1
                if wp[j] == 1:
                    cc[i][j] = -1

        black = sum([l.count('#') for l in cc])
        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)]
sumb=0

for i in range(h):
    for j in range(w):
        if c[i][j]=="#":
            sumb+=1
ans=0
for i in range(2**(h+w)):
    lish,lisw=[],[]
    s=sumb
    for j in range(h+w):
        if (i>>j)&1:
            if j<h:
                lish.append(j)
            else:
                lisw.append(j-h)
    for idxh in lish:
        for idx in range(w):
            s=s-(c[idxh][idx]=="#")
    for idx in range(h):
        for idxw in lisw:
            s=s-(c[idx][idxw]=="#")
    for idxh in lish:
        for idxw in lisw:
            s+=(c[idxh][idxw]=="#")
    if s==k:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

mp = [input() for _ in range(H)]
h = deque([[[0],[0]], [[0],[1]], [[1],[0]], [[1],[1]]])

rlt = 0
while h:
  l = h.pop()
  if len(l[0]) == H and len(l[1]) == W:
    k = 0
    for i in range(H):
      if l[0][i] == 1:
        continue
      for j in range(W):
        if mp[i][j] == '#' and l[1][j] == 0:
          k += 1
    if k == K:
      rlt += 1
  else:
    if len(l[0]) < H and len(l[1]) < W: 
      for m in [0,1]:
        for n in [0,1]:
          h.append([l[0] + [m],l[1]+[n]])
    elif len(l[0]) == H:
      for n in [0,1]:
        h.append([l[0],l[1]+[n]])
    else:
      for m in [0,1]:
        h.append([l[0]+[m],l[1]])
        
print(rlt)

Submission status: Accepted

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

mat = [list(input()) for i in range(h)]

n_black = 0
for line in mat:
    for elm in line:
        if elm == "#":
            n_black += 1

out = 0
for h_pattern in product((False, True), repeat=h):
    for w_pattern in product((False, True), repeat=w):
        #print(h_pattern, w_pattern)
        del_ = 0
        for hi, h_flag in enumerate(h_pattern):
            for wi, w_flag in enumerate(w_pattern):
                if h_flag or w_flag:
                    if mat[hi][wi] == "#":
                        del_ += 1
                        
        nokori = n_black - del_
        #print(nokori)
        if k == nokori:
            out += 1

print(out)

Submission status: Accepted

Solution code:
import itertools

h, w, k = map(int, input().split())
S = [input() for s in range(h)]
ans = 0
for rows in itertools.product([0, 1], repeat=h):
    for cols in itertools.product([0, 1], repeat=w):
        tmp = 0
        for idx_row, i in enumerate(rows):
            if i == 1:
                continue
            for idx_col, j in enumerate(cols):
                if j == 1:
                    continue
                if S[idx_row][idx_col] == '#':
                    tmp += 1
        if tmp == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    H, W, K = list(map(int, sysread().split()))
    C = []
    for i in range(H):
        C.append(input())
    ans = 0
    for i in range(0, 2 ** H):
        for j in range(0, 2 ** W):
            ret = 0
            selected = []
            for l in range(W):
                if not (j >> l) & 1:
                    selected.append(l)
            for k in range(H):
                if not (i >> k) & 1 :
                    for v in selected:
                        if C[k][v] == '#':ret += 1
            if ret == K:
                ans += 1
    print(ans)


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import numpy as np
from copy import deepcopy
ans = 0
h, w, k = map(int, input().split())
c = [list(input()) for _ in range(h)]
c = np.array(c)
c = (c == '#') * 1
for i in range(2 ** (h + w)):
    d = deepcopy(c)
    i = bin(i)
    i = "0" * (h + w - len(i) + 2) + i[2:]
    for j in range(h + w):
        if i[j] == "1" and j < h:
            d[j] = 0
        elif i[j] == "1":
            d[:,j - h] = 0
    if np.sum(d) == k:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    H, W, K = map(int, input().split())
    matrix = []
    for _ in range(H):
        c = list(input())
        matrix.append(c)
    ans = 0

    for row in range(2**H):
        for col in range(2**W):
            countK = 0
            for h in range(H):
                for w in range(W):
                    if matrix[h][w] == "#":
                        if (row >> h)&1 and (col >> w)&1:
                            countK += 1
            if countK == K:
                ans += 1
    print(ans)



if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
h, w, tar = [int(i) for i in input().split()]

line = []
for i in range(h):
    a = input()
    line.append([k for k in a])

ans = 0


import itertools
hs = []
for i in range(h + 1):
    hs.extend(list(itertools.combinations(range(h), i)))

ws = []
for i in range(w + 1):
    ws.extend(list(itertools.combinations(range(w), i)))

for i in hs:
    for j in ws:
        res = 0
        for k in range(h):
            for l in range(w):
                if line[k][l] == "#" and (k not in i) and (l not in j):
                    res += 1
        if res == tar:
            ans += 1


print(ans)

Submission status: Accepted

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

from itertools import product

ans = 0
for col, row in product(list(range(2**h)), list(range(2**w))):
    col = f"{int(str(bin(col))[2:]):0{h}}"
    row = f"{int(str(bin(row))[2:]):0{w}}"
    _c = []
    for i, is_col in enumerate(col):
        if int(is_col):
            _c.append(c[i])
    new_c = []
    for j, is_row in enumerate(row):
        if int(is_row):
            cur_c_c = []
            for _c_c in _c:
                cur_c_c.append(_c_c[j])
            new_c.append(cur_c_c)
    if sum([el.count("#") for el in new_c]) == k:
        ans += 1



print(ans)

Submission status: Accepted

Solution code:
import itertools

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

d = []
for i in range(h):
	d.append(input())

ph = list(itertools.product([0,1], repeat=h))
pw = list(itertools.product([0,1], repeat=w))

c = 0
ans = 0
for i in ph:
	for j in pw:
		for m in range(h):
			for n in range(w):
				if d[m][n]=='#' and i[m]==0 and j[n]==0:
					c += 1
		if c == k:
			ans += 1
		c = 0

print(ans)

Submission status: Accepted

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

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

C = []

for i in range(H):
    a = []
    for j in range(W):
        if CC[i][j] == '.':
            a.append(0)
        else:
            a.append(1)
    C.append(a)
ret = 0
for ph in product([0,1], repeat=H):
    for pw in product([0,1], repeat=W):
        cnt = 0
        for i in range(len(ph)):
            if ph[i] == 0:
                for j in range(len(C[i])):
                    if C[i][j] == 1 and pw[j] == 0:
                        cnt += 1
        if cnt == K: ret += 1

print(ret)

Submission status: Accepted

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

import copy
ans =[0]*(h*w+1)
for i in range(2**h):
    for j in range(2**w):
        
        cc = copy.deepcopy(c)
        bi = bin(i)[2:].zfill(h)
        bj = bin(j)[2:].zfill(w)
        for ii in range(h):
            for jj in range(w):
                if bi[ii]=="1":
                    cc[ii]=[2]*w
                if bj[jj]=="1":
                    for kk in range(h):
                        cc[kk][jj]=2
                    
        n_black = sum(ccc.count("#") for ccc in cc )
        
#        print(i,bi,j,bj,n_black,cc)
        ans[n_black]+=1
print(ans[k])

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
H,W,K= map(int,input().split())
C = [input().strip() for i in range(H)]
C = [list(map(lambda x : 0 if x == '.' else 1, c)) for c in C]

m = lambda x : 0 if x == '0' else 1
ans = 0
for h in range(2**H):
    for w in range(2**W):
        hb = list(bin(h)[2:])
        hb = [0]*(H-len(hb))+hb
        hp = list( i for i,x in enumerate(hb) if x == '1')
        wb = list(bin(w)[2:])
        wb = [0]*(W-len(wb))+wb
        wp = list( i for i,x in enumerate(wb) if x == '1')
        k = 0
        for i in range(H):
            for j in range(W):
                if i in hp:
                    continue
                if j in wp:
                    continue
                k += C[i][j]
        if k == K:
            ans += 1
print(ans)