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:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

h, w, K = map(int, input().split())
field = []
for _ in range(h):
    line = input().rstrip()
    field.append(line)

ans = 0
for i in range(2**h):
    for j in range(2**w):
        cnt = 0
        for k in range(h):
            if i & (1 << k):
                continue
            for l in range(w):
                if j & (1 << l):
                    continue
                if field[k][l] == "#":
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as comb

h,w,k = map(int,input().split())
g = [input() for i in range(h)]

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

for i in range(h+1):
	for cr in comb(row, i):
		for j in range(w+1):
			for cc in comb(col, j):
				gp = [list(s) for s in g]
				for ligne in cr:
					for colonne in range(w):
						gp[ligne][colonne] ="r"
				for colonne in cc:
					for ligne in range(h):
						gp[ligne][colonne] = "r"
				reste = 0
				for ligne in gp:
					reste+=ligne.count("#")
				if reste == k:
					ANS+=1
print(ANS)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def gen_comb(n):
    c = []
    for i in range(n):
        for comb in itertools.combinations([j for j in range(n)], i):
            c.append(list(comb))
    return c

def count(C, arr1, arr2):
    n_row = len(C)
    n_col = len(C[0])
    s1 = set(arr1)
    s2 = set(arr2)
    cnt = 0
    for r in range(n_row):
        for c in range(n_col):
            if r in s1:
                continue
            if c in s2:
                continue
            if C[r][c] == '#':
                cnt += 1
    return cnt

def main():
    H, W, K = LI()
    C = []
    for i in range(H):
        C.append(S())

    h_comb = gen_comb(H)
    w_comb = gen_comb(W)
    cnt = 0
    for ixs in h_comb:
        for jxs in w_comb:
            if count(C, ixs, jxs) == K:
                cnt += 1
    print(cnt)


main()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w,k = lr()
a = [input() for i in range(h)]
ans = 0
for i in range(2**(h+w)):
    tmp = [[a[q][l] for l in range(w)] for q in range(h)]
    for j in range(h+w):
        if (j < h and ((i >> j) & 1)):
            for q in range(w):
                tmp[j][q] = '0'
        elif (j >= h and ((i >> j) & 1)):
            for q in range(h):
                tmp[q][j-h] = '0'
    pre = 0
    for q in range(h):
        for l in range(w):
            if tmp[q][l] == '#':
                pre+=1
    if pre == k:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

import itertools
ans=0
count=0
for casei in itertools.product([0,1], repeat=h):
    for casej in itertools.product([0,1], repeat=w):
        for i in range(h):
            for j in range(w):
                if maze[i][j]=='#' and casei[i]==0 and casej[j]==0:
                    count+=1
        if count == k:
            ans+=1
        count=0

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq


def solve(H, W, K, field):
    # print(H, ",", W, ",", K, ",", field)
    N = 2 ** (H + W)
    F = "{:0" + str(H + W) + "b}"
    ans = 0
    for n in range(N):
        HM = F.format(n)[:H]
        WM = F.format(n)[H:]
        c = 0
        for h in range(H):
            for w in range(W):
                if HM[h] == "1":
                    continue
                if WM[w] == "1":
                    continue
                if field[h][w] == "#":
                    c += 1
        if c == K:
            ans += 1

    return ans


# print(solve(2, 3, 2, ['..#', '###']))

if __name__ == "__main__":
    H, W, K = tuple(map(int, input().split(" ")))
    field = [input() for _ in range(H)]
    print(solve(H, W, K, field))

Submission status: Accepted

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

def count_kuro(c, bit_i, bit_j):
    list_i = []
    for i in range(H):
        if bit_i>>i&1:
            list_i.append(i)
    list_j = []
    for j in range(W):
        if bit_j>>j&1:
            list_j.append(j)

    tansaku = [
        (i,j) for i in range(H) for j in range(W)
        if i in list_i and j in list_j
    ]

    return sum([c[dot[0]][dot[1]]=='#' for dot in tansaku])


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

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

count = 0
for bit_i in range(2**H):
    for bit_j in range(2**W):
        num_kuro = count_kuro(c, bit_i, bit_j)
        if num_kuro == K:
            count+=1

print(count)

Submission status: Accepted

Solution code:
from itertools import product
H, W, K = map(int, input().split())

c = [list(input()) for i in range(H)]

ans = 0
for bity in product([True, False], repeat=H):
    for bitx in product([True, False], repeat=W):
        area = [[0] * W for i in range(H)]
        for i in range(H):
            for j in range(W):
                area[i][j] = c[i][j]
        
        # 数える
        for y in range(H):
            if bity[y]:
                for x in range(W):
                    area[y][x] = '.'
        for x in range(W):
            if bitx[x]:
                for y in range(H):
                    area[y][x] = '.'
        temp = sum([a.count('#') for a in area])
        if temp == K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import *
h,w,K = map(int,input().split())
a = []
for i in range(h):
	a.append(list(input()))
ans = 0
for i in range(1 << h):
	for j in range(1 << w):
		c = [[a[J][I] for I in range(w)] for J in range(h)]
		for k in range(h):
			if(i&(1 << k)):
				for kk in range(w):
					c[k][kk] = 'R'
		for k in range(w):
			if(j&(1 << k)):
				for kk in range(h):
					c[kk][k] = 'R'
		ct = 0
		for k in range(h):
			ct += c[k].count('#')
		if(ct == K):
			ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


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

for a in range(1<<h):
    for b in range(1<<w):
        M = [[0] * w for _ in range(h)]
        for i in range(h):
            for j in range(w):
                if A[i][j] == "#":
                    M[i][j] = 1
        for i in range(h):
            if (a >> i) & 1:
                for j in range(w):
                    M[i][j] = 0

        for j in range(w):
            if (b >> j) & 1:
                for i in range(h):
                    M[i][j] = 0

        count = 0
        for i in range(h):
            for j in range(w):
                if M[i][j] == 1:
                    count += 1
        # print(bin(a)[2:], bin(b)[2:], count)

        if count == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

count=0
for x in product((0,1),repeat=h):
    for y in product((0,1),repeat=w):
        sm=0
        for i in range(h):
            if x[i]==0 : continue
            for j in range(w):
                if y[j]==0 : continue
                if lst[i][j]=="#" : sm+=1
        if sm==k : count+=1

print(count)

Submission status: Accepted

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

ans=0

for i in range(2**H):
    cc=deepcopy(c)
    for b in range(H):
        if (i>>b)&1==1:
            for k in range(W):
                cc[b][k]='r'

    for j in range(2**W):
        ccc=deepcopy(cc)
        for b in range(W):
            if (j>>b)&1==1:
                for k in range(H):
                    ccc[k][b]='r'
        cnt=0
        for i in range(H):
            for j in range(W):
                if ccc[i][j]=='#':
                    cnt+=1
        
        if cnt==K:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import copy
H,W,K = map(int,input().split())
C_org = [list(input().rstrip()) for _ in range (H)]
ans = 0 
def change(C, k, row):
    if row==0:
        for i in range(W):
            C[k][i] = '.'
    else:
        for i in range(H):
            C[i][k] = '.'
    return 

for i in range(1<<H):
    C1 = copy.deepcopy(C_org)
    for k in range(H):
        if i==0:
            break
        if i&1:
            for t in range(W):
                C1[k][t] = '.'
        i>>=1

    for j in range(1<<W):
        C2 = copy.deepcopy(C1)
        for k in range(W):
            if j==0:
                break
            if j&1:
                for t in range(H):
                    C2[t][k] = '.'
            j>>=1
        
        cnt = 0
        for cc in C2:
            for c in cc:
                if c=='#':
                    cnt += 1
        if cnt==K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

h,w,k = inm()
c = []
for i in range(h):
    c.append(ins())
ans = 0
for i in range(2**h):
    for j in range(2**w):
        sm = 0
        for x in range(h):
            for y in range(w):
                if (i>>x)%2>0 and (j>>y)%2>0 and c[x][y]=='#':
                    sm += 1
        if sm==k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    # black = 0
    # for row in G:
    #     black += row.count('#')

    # target = black - K

    ans = 0
    for rh in range(1, H + 1):
        for combh in combinations(range(H), rh):
            for rw in range(1, W + 1):
                for combw in combinations(range(W), rw):
                    tmp = 0
                    for i in combh:
                        for j in combw:
                            if G[i][j] == '#':
                                tmp += 1
                    if tmp == K:
                        ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#create date: 2020-07-05 21:01

import sys
stdin = sys.stdin
from itertools import product

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def f(c, hi, wi):
    cnt = 0
    for i, hb in enumerate(hi):
        if hb == 0:
            continue
        for j, wb in enumerate(wi):
            if wb == 0:
                continue
            if c[i][j] == 1:
                cnt += 1
    return cnt



def main():
    h, w, k = na()
    hb = list(product([0,1], repeat=h))
    wb = list(product([0,1], repeat=w))
    c = list()
    for _ in range(h):
        c += [[1 if s == "#" else 0 for s in ns()]]
    #print(c)
    cnt = 0
    for hi in hb:
        for wi in wb:
            if f(c, hi, wi) == k:
                cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

cmat=[[x=="." for x in input()] for _ in range(H)]
#print(cmat)

answer=0
for perm in itertools.product([True,False],repeat=H+W):
  #print(perm)
  row_set=set()
  for i in range(H):
    if perm[i]:
      row_set.add(i)
  
  col_set=set()
  for i in range(H,H+W):
    if perm[i]:
      col_set.add(i-H)      
  
  #print(perm,row_set,col_set)
  cnt=0
  for i in range(H):
    for j in range(W):
      if not cmat[i][j] and not i in row_set and not j in col_set:
        cnt+=1
        
  if cnt==K:
    answer+=1
    
print(answer)

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):
        tmp = 0
        for h in range(H):
            if i & (1 << h):
                continue
            for w in range(W):
                if j & (1 << w):
                    continue
                if c[h][w] == "#":
                    tmp += 1
        if tmp == 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(2**H):
    for j in range(2**W):
        mm = 0
        for h in range(H):
            for w in range(W):
                if ((i>>h)&1) and ((j>>w)&1) and C[h][w]=="#":
                    mm += 1
        if mm==K:
            ans += 1
            # print(bin(i),bin(j))
print(ans)

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
h,w,k=n1()
s=s4(h)
H=list(itertools.product([0,1],repeat=h))
W=list(itertools.product([0,1],repeat=w))

ans=0
for tate in H:
    for yoko in W:
        c=0
        for i in range(h):
            for j in range(w):
                if tate[i] == 1 or yoko[j] == 1:
                    pass
                elif s[i][j]=="#":
                    c+=1
        if c==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for hh in itertools.product("01", repeat = h):
    h_lst = []
    for i, s in enumerate(hh):
        if s == "1":
            h_lst.append(i)
    for ww in itertools.product("01", repeat = w):
        w_lst = []
        for i, s in enumerate(ww):
            if s == "1":
                w_lst.append(i)
        tmp = 0            
        for i in h_lst:
            for j in w_lst:
                if c[i][j] == "#":
                    tmp += 1
        if tmp == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    c = [None] * H
    for i in range(H):
        S = input().rstrip()
        c[i] = [1 if s == "#" else 0 for s in S]

    ans = 0
    for h_comb in product((True, False), repeat=H):
        for w_comb in product((True, False), repeat=W):
            grid = np.array(c, dtype=np.int64)
            for i, paint in enumerate(h_comb):
                if paint:
                    grid[i, :] = 0
            for i, paint in enumerate(w_comb):
                if paint:
                    grid[:, i] = 0
            if np.sum(grid) == K:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w, K = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for i in range(2**h):
    dh = [(i >> j) & 1 for j in range(h)]
    for k in range(2**w):
        dw = [(k >> j) & 1 for j in range(w)]
        res = 0
        for nh in range(h):
            for nw in range(w):
                if dh[nh]==0 and dw[nw]==0:
                    if c[nh][nw]=="#":
                        res += 1
        if res == K: 
            ans += 1

print(ans)

Submission status: Accepted

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

field = [input() for _ in range(h)]


ans = 0
for bit_h in range(2**h):
    for bit_w in range(2**w):
        count = 0
        use_h = []
        for i in range(h):
            if (bit_h >> i) & 1:
                use_h.append(field[i])

        for j in range(w):
            if (bit_w >> j) & 1:
                for line in use_h:
                    if line[j] == "#":
                        count += 1

        if count == k:
            ans += 1

print(ans)

Submission status: Accepted

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

def oneBit(bitarr,k):
    return (bitarr & 1 << k) > 0

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    H,W,K = map(int,input().split())
    C = [list(input())for i in range(H)]
    hMax = 2**H
    wMax = 2**W
    c=0
    for h in range(hMax):
        for w in range(wMax):
            bc = 0
            for y in range(H):
                for x in range(W):
                    if C[y][x] == "#" and (not oneBit(h,y) and not oneBit(w,x)):
                        bc +=1
            if bc == K:
                c += 1
    print(c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
H,W,K = map(int, input().split())
C = []
for _ in range(H):
  C.append(input())
  
ans = 0
for hp in product([0,1], repeat=H):
  for wp in product([0,1], repeat=W):
    wk = 0
    for i in range(H):
      for j in range(W):
        if C[i][j] == '#' and hp[i] == 0 and wp[j] == 0:
          wk += 1
    #print(hp, wp, wk)
    if wk == 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):
        d=[[c[z][v] for v in range(w)]for z in range(h)]
        for k in range(h):
            if (i>>k)&1:
                for l in range(w):
                    d[k][l]="x"
        for k in range(w):
            if (j>>k)&1:
                for l in range(h):
                    d[l][k]="x"
        cnt=0
        for k in range(h):
            for l in range(w):
                cnt+=(d[k][l]=="#")
        ans+=(cnt==K)
print(ans)

Submission status: Accepted

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

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    c = [SI() for _ in range(H)]
    ans = 0
    for i in range(2**H):
        for j in range(2**W):
            cnt = 0
            for a in range(H):
                if (1 << a) & i:
                    for b in range(W):
                        if (1<<b) & j:
                            cnt += (c[a][b] == "#")

            if cnt == K: ans+= 1
    print (ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy

R, C, K = [int(x) for x in input().split()]

gridOriginal = [list(input()) for r in range(R)]

initBlack = 0
for r in range(R):
    for c in range(C):
        if gridOriginal[r][c] == "#":
            initBlack += 1

count = 0
for rowMask in range(1 << R):
    for colMask in range(1 << C):
        grid = deepcopy(gridOriginal)
        removed = 0
        for r in range(R):
            for c in range(C):
                if grid[r][c] == "#" and (rowMask & (1 << r) or colMask & (1 << c)):
                    removed += 1
                    grid[r][c] = "R"

        if initBlack - removed == K:
            count += 1

print(count)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
grid = [list(input())for i in range(h)]
from copy import deepcopy
maze = deepcopy(grid)
ans = 0
for i in range(2**h):
    for j in range(2**w):
        point = 0
        for bh in range(h):
            if ((i>>bh)&1):
                for a in range(w):
                    grid[bh][a] = '0'
        for bw in range(w):
            if ((j >> bw)&1):
                for b in range(h):
                    grid[b][bw] = '0'
        for ii in range(h):
            for jj in range(w):
                if grid[ii][jj] == '#':
                    point += 1
        
        if point == k:
            ans += 1
        
        grid = deepcopy(maze)
print(ans)

Submission status: Accepted

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

def int2bit(n, l):
	bit = [0 for i in range(l)]
	i = 0
	while n > 0:
		bit[i] = n % 2
		n = n // 2
		i += 1
	return bit

ans = 0
for h in range(2**H):
	ph = int2bit(h, H)
	for w in range(2**W):
		pw = int2bit(w, W)
		paint = [[(ph[i] == 1 or pw[j] == 1) for j in range(W)] for i in range(H)]
		cnt = 0
		for i in range(H):
			for j in range(W):
				if not paint[i][j] and G[i][j] == "#":
					cnt += 1
		if cnt == K:
			ans += 1
print(ans)

Submission status: Accepted

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

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

B = [input().rstrip() for _ in range(H)]


def get_black(X, Y):
    ret = 0
    for i in range(W):
        for j in range(H):
            if i in X or j in Y: continue
            if B[j][i] == '#': ret += 1
    return ret

ans = 0

for i in range(1 << W):
    for j in range(1 << H):
        X = set()
        Y = set()
        for x in range(W):
            if (1 << x) & i: X.add(x)
        for y in range(H):
            if (1 << y) & j: Y.add(y)

        if get_black(X, Y) == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
ans=0
boards=[]
for i in range(2**h):
  tmp=copy.deepcopy(board)
  bit1=format(i,'b')
  bit1='0'*(h-len(bit1))+bit1
  for th in range(h):
    if bit1[th]=='0':
      continue
    for tw in range(w):
      tmp[th][tw]='.'
  boards.append(tmp)
for i in range(len(boards)):
  for j in range(2**w):
    tmp=copy.deepcopy(boards[i])
    bit2=format(j,'b')
    bit2='0'*(w-len(bit2))+bit2
    for tw in range(w):
      if bit2[tw]=='0':
        continue
      for th in range(h):
        tmp[th][tw]='.'
    cnt=0
    for th in range(h):
      for tw in range(w):
        if tmp[th][tw]=='#':
          cnt+=1
    if cnt==k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy

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

    ans = 0
    for i in range(1 << h):
        c1 = copy.deepcopy(c)
        x = i
        p = 0
        while x > 0:
            if x & 1 == 1:
                c1[p] = ['x'] * w
            x = x >> 1
            p += 1
        for j in range(1 << w):
            c2 = copy.deepcopy(c1)
            x = j
            p = 0
            while x > 0:
                if x & 1 == 1:
                    for l in range(h):
                        c2[l][p] = 'x'
                x = x >> 1
                p += 1
            count = 0
            for l in range(h):
                for m in range(w):
                    if c2[l][m] == '#':
                        count += 1
            if count == k:
                ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
C=[[0]*w for i in range(h)]
for i in range(h):
    c=input()
    for j in range(w):
        if c[j]=="#":
            C[i][j]=1

ans=0
for i in range(2**h):
    for j in range(2**w):
        R=[]
        for p in range(h):
            if i>>p&1:
                R.append([1]*w)
            else:
                R.append([0]*w)
        for q in range(w):
            if j>>q&1:
                for p in range(h):
                    R[p][q]=1
        cnt=0
        for p in range(h):
            for q in range(w):
                if C[p][q]==1 and R[p][q]==0:
                    cnt+=1
        if cnt==k:
            ans+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    H,W,K=mis()
    c = [input() for _ in range(H)]
    ans = 0
    for D in product((0, 1), repeat=H+W):
        h = D[:H]
        w = D[H:]
        if sum(c[y][x]=='#' and not w[x] and not h[y] for x, y in product(range(W), range(H))) == K:
            ans += 1
    print(ans)






main()

Submission status: Accepted

Solution code:
import itertools

h, w, k = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for x, y in itertools.product(range(2 ** h), range(2 ** w)):
    cnt = 0
    for i in range(h):
        for j in range(w):
            if x >> i & 1 or  y >> j & 1: continue
            if c[i][j] == '#': cnt += 1
    if cnt == k:
        ans += 1
print(ans)