Problem:


Score : 300 points

Problem Statement

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

Consider doing the following operation:

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

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

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

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

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

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

Sample Output 4

208



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


Sample output:
5

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

r_bit = 1 << H
w_bit = 1 << W

# print(r_bit, w_bit)

ans = 0
for r in range(r_bit):
    n_row = []
    for i in range(H):
        if r & 1:
            n_row.append(i)
        r >>= 1

    for c in range(w_bit):
        # 使えない行、列

        n_col = []

        for j in range(W):
            if c & 1:
                n_col.append(j)
            c >>= 1

        cnt = 0
        for i in range(H):
            for j in range(W):
                if i in n_row or j in n_col:
                    continue
                if C[i][j] == "#":
                    cnt += 1

        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy

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

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

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

ans = 0

for i in range(2**H):
    d = copy.deepcopy(c)
    for j in range(H):
        if 2**j & i > 0:
            for k in range(W):
                d[j][k] = "."
    for j in range(2**W):
        e = copy.deepcopy(d)
        for k in range(W):
            if 2**k & j > 0:
                for l in range(H):
                    e[l][k] = "."
        #print(c)
        if count(e)==K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
H,W,K = map(int,input().split())
C = [input().strip() for _ in range(H)]
ans = 0
for row in product((0,1),repeat=H):
    for col in product((0,1),repeat=W):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if row[i]==0 and col[j]==0 and C[i][j]=="#":
                    cnt += 1
        if cnt==K:
            ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for h in range(1 << H):
    for w in range(1 << W):
        black = 0
        for i in range(H):
            for j in range(W):
                if ((h >> i) & 1) + ((w >> j) & 1) == 0:  # 赤く塗られない
                    black += (c[i][j] == '#')
        if black == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

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

def main():
    h,w,k = readInt()
    c = []
    for i in range(h):
        c.append(input())
    ans = 0
    for i in range(1<<h):
        for j in range(1<<w):
            res = 0
            for l in range(h):
                if (i>>l)&1:
                    for m in range(w):
                        if (j>>m)&1:
                            if c[l][m]=='#':
                                res += 1
            if res==k:
                ans += 1
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

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

c = []

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

	c.append(d)

result = 0

for m1 in range(1 << h):
	for m2 in range(1 << w):			
		d = []
		for i in range(h):
			x = []
			for j in range(w):
				x.append(c[i][j])
			d.append(x)


		for row in range(h):
			if (m1 >> row) % 2 == 1:
				for j in range(w):
					d[row][j] = '.'

		for col in range(w):
			if (m2 >> col) % 2 == 1:
				for i in range(h):
					d[i][col] = '.'

		count = 0
		for i in range(h):
			for j in range(w):
				if d[i][j] == '#':
					count += 1

		if count == k:
			result += 1

print(result)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
C = np.array([[0 if c == '.' else 1 for c in input()] for _ in range(H)],
             dtype=int)
ans = 0
for bh in itertools.product([True, False], repeat=H):
    D = C.copy()
    D[np.array(bh), :] = np.zeros(W, dtype=int)
    for bw in itertools.product([True, False], repeat=W):
        E = D.copy().T
        E[np.array(bw), :] = np.zeros(H, dtype=int)
        if np.sum(E) == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, k = map(int, input().split())
    grid = list(list(input()) for _ in range(H))

    res = 0
    for pattern_H in product([0, 1], repeat=H):
        ign_H = []
        for idx, p in enumerate(pattern_H):
            if p == 1:
                ign_H.append(idx)
        for pattern_W in product([0, 1], repeat=W):
            cnt = 0
            ign_W = []
            for idx, p in enumerate(pattern_W):
                if p == 1:
                    ign_W.append(idx)
            for h in range(H):
                if h in ign_H:
                    continue
                for w in range(W):
                    if w in ign_W:
                        continue
                    if grid[h][w] == "#":
                        cnt += 1
            if cnt == k:
                res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

ans = 0
for i in range(0,2**h):
	for j in range(0,2**w):
		iro = [[0]*w for i in range(h)]
		# 縦
		for v in range(h):
			if (i & (1 <<v)) != 0:
				for k in range(w):
					iro[v][k] = 1
		# 横
		for v in range(w):
			if (j & (1 <<v)) != 0:
				for k in range(h):
					iro[k][v] = 1
		count = 0
		
		for k in range(h):
			for l in range(w):
				if iro[k][l] == 0 and hw[k][l] == '#':
					count += 1

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

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
def count_grid(a,b):
    count = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#" and a >> i & 1 and b >> j & 1:
                count += 1
    return count
ans = 0
for a in range(2**h):
    for b in range(2**w):
        if count_grid(a,b) == 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 x in range(2**h):
    for y in range(2**w):
        cnt=0
        for i in range(h):
            for j in range(w):
                if x>>i&1 and y>>j&1:
                    if c[i][j]=="#":
                        cnt+=1
        if cnt==k:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math
import pprint
import fractions
import collections
import itertools
from decimal import *
from collections import deque
from bisect import *
H,W,K=map(int,input().split())
table=[list(input()) for _ in range(H)]
yoko=[]                                     #横列の塗る(1)/ぬらない(0)
tate=[]                                     #縦列の塗る(1)/ぬらない(0)
ans=0
for i in range(pow(2,H)):
    yoko=[0]*H
    for j in range(H):
        if i>>j&1:
            yoko[j]=1
    for j in range(pow(2,W)):
        tate=[0]*W
        for k in range(W):
            if j >> k & 1:
                tate[k] = 1
        cnt=0
        for i in range(H):
            for j in range(W):
                if (yoko[i]==0)and(tate[j]==0)and(table[i][j]=="#"):
                    cnt=cnt+1
        if cnt==K:
            ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


import itertools

def powerset(iterable, low=0, high=None):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    if high is None:
        high = len(s)+1
    return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(low, high))


def solve(h, w, k, a):
    ans = 0
    rows = [i for i in range(h)]
    cols = [j for j in range(w)]

    for rr in powerset(rows):
        for cc in powerset(cols):
            rrs = set(rr)
            ccs = set(cc)
            cnt = 0
            for i in range(h):
                for j in range(w):
                    if i not in rrs and j not in ccs and a[i][j] == '#':
                        cnt += 1
            if cnt == k:
                ans += 1

    return ans


def main():
    h, w, k = ria()
    a = []
    for _ in range(h):
        a.append(rs())
    wi(solve(h, w, k, a))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	h, w, k = map(int, sys.stdin.readline().split())
	c = []
	for i in range(h):
		c.append(list(input()))
	log.print(c)
	ans = 0
	for i in range(2**h):
		gyou = []
		for l in range(h):
			if i >> l & 1:
				gyou.append(l)
		for j in range(2**w):
			retu = []
			for l in range(w):
				if j >> l & 1:
					retu.append(l)
			count = 0
			for l in range(h):
				for m in range(w):
					if l in gyou or m in retu:
						continue
					if c[l][m] == "#":
						count += 1
			if count == k:
				ans += 1
	print(ans)


main()

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
h,w,k=MI()
lis=[[0]*w for i in range(h)]
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]=="#":
            lis[i][j]=1
#print(lis)
ans=0
for x in product([0,1],repeat=h+w):
    count=0
    for i in range(h):
        for j in range(w):
            if x[i]==0 and x[h+j]==0 and lis[i][j]==1:
                count+=1
    if count==k:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy
h,w,K=map(int,input().split())
c=[list(input()) for i in range(h)]
b=[]
for i in range(2**(h+w)):
  b.append(format(i,'0'+str(h+w)+'b'))
ans=0
for i in range(len(b)):
  l=copy.deepcopy(c)
  for j in range(h+w):
    if j<h:
      if b[i][j]=='1':
        for k in range(w):
          l[j][k]='x'
    else:
      if b[i][j]=='1':
        for k in range(h):
          l[k][j-h]='x'
  ct=0
  for j in range(h):
    for k in range(w):
      if l[j][k]=='#':
        ct+=1
  if ct==K:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

answer = 0
for i in range(2 ** (H + W)):
    s = [list(ss) for ss in S]
    for h in range(H):
        if i >> h & 1:
            for w in range(W):
                s[h][w] = "."
    for w in range(H, H + W):
        if i >> w & 1:
            for h in range(H):
                s[h][w - H] = "."
    cnt = 0
    for h in range(H):
        for w in range(W):
            if s[h][w] == "#":
                cnt += 1
    if cnt == K:
        answer += 1

print(answer)

Submission status: Accepted

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

ans = 0
for hbit in range(1<<h):
    for wbit in range(1<<w):
        tmp = 0
        for i in range(h):
            if hbit & (1<<i):
                continue
            for j in range(w):
                if wbit & (1<<j):
                    continue
                elif C[i][j] == "#":
                    tmp += 1
        if tmp == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
graph = list()
for i in range(H):
  graph.append(input())
  
ans = 0
for h in range(1<<H):
  for w in range(1<<W):
    hlist = list()
    wlist = list()
    for i in range(H):
      if(h>>i & 1):
        hlist.append(i)
    for j in range(W):
      if(w>>j & 1):
        wlist.append(j)
    cnt = 0
    for i in range(H):
      for j in range(W):
        if (not i in hlist) and (not j in wlist) and graph[i][j] == '#':
          cnt += 1
    #print(hlist, wlist, cnt)
    if(cnt == K):
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
c = [input() for _ in range(H)]
# print(c)
ans = 0
for bi in range(1<<H):
    for bj in range(1<<W):
        cnt = 0
        for i in range(H):
            if (bi>>i)&1: continue
            for j in range(W):
                if (bj>>j)&1: continue
                if c[i][j]=='#':
                    cnt += 1
        if cnt==K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n,m,K=map(int,input().split())
    a=[[ x=='#' for x in input()] for _ in range(n)]
    ans=0
    # print(a)
    def get(x,y):
        cnt=0
        for i in range(n):
            for j in range(m):
                if x&(1<<i) or y&(1<<j):
                    continue
                cnt+=a[i][j]
        return cnt

    for m1 in range(1<<n):
        for m2 in range(1<<m):
            ans+=get(m1,m2)==K
    print(ans)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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

total = 0

for i in range(2 ** (H + W)):
	tmp_data = tuple(list(col) for col in data)
	for y in range(H):
		if i % 2 == 0:
			for x in range(W):
				tmp_data[y][x] = "r"
		i //= 2
	for x in range(W):
		if i % 2 == 0:
			for y in range(H):
				tmp_data[y][x] = "r"
		i //= 2
	count = 0
	for y in range(H):
		for x in range(W):
			if tmp_data[y][x] == "#":
				count += 1
	if count == K:
		total += 1
print(total)

Submission status: Accepted

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict,deque,Counter
from fractions import Fraction
import bisect
import itertools
from itertools import accumulate
from copy import deepcopy
import heapq
import random
import time
import os
import sys
from functools import lru_cache,reduce
readline=sys.stdin.readline
sys.setrecursionlimit(100000)
alp="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Set():
    def __init__(self,A=[]):
        self.heap=[]
        self.dic=defaultdict(bool)
        self.size=0
        for a in A:self.add(a)
    
    def __str__(self):
        return str(self.heap)
    
    def add(self,x):
        if not self.find(x):
            heapq.heappush(self.heap,x)
            self.dic[x]=True
            self.size+=1

    def remove(self,x):
        if self.find(x):
            self.dic[x]=False
            self.size-=1

    def find(self,x):
        return self.dic[x]
    
    def top(self):
        while self.heap and self.dic[self.heap[0]]==False:
            heapq.heappop(self.heap)
        if self.heap:return self.heap[0]
        else:return None

    def pop(self):
        ret=None
        if self.heap:
            ret=self.top()
            self.remove(ret)
        return ret
class multiset():
    def __init__(self,A=[]):
        self.heap=[]
        self.dic=defaultdict(int)
        self.size=0
        for a in A:self.add(a)
    
    def __str__(self):
        return str(self.heap)
    
    def add(self,x):
        heapq.heappush(self.heap,x)
        self.dic[x]+=1
        self.size+=1

    def remove(self,x):
        if self.dic[x]>0:
            self.dic[x]-=1
            self.size-=1
    
    def count(self,x):
        return self.dic[x]

    def find(self,x):
        return self.dic[x]>0
    
    def top(self):
        while self.heap and self.dic[self.heap[0]]==0:
            heapq.heappop(self.heap)
        if self.heap:return self.heap[0]
        else:return None

    def pop(self):
        ret=None
        if self.heap:
            ret=self.top()
            self.remove(ret)
        return ret
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):print("yes" if b else "no")
def Yn(b):print("Yes" if b else "No")
def YN(b):print("YES" if b else "NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(b,t,f):return t if b else f
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def inputintlist(row=1): 
    if row==1:
        ret=list(map(int,input().split()))
    else:
        ret=[None]*row
        for a in range(row):
            ret[a]=int(input())
    return ret
def inputfloatlist(row=1): 
    if row==1:
        ret=list(map(float,input().split()))
    else:
        ret=[None]*row
        for a in range(row):
            ret[a]=float(input())
    return ret
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def getmd(x1,y1,x2,y2):return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow
def zipsort(*args):
    ziplist=sorted(zip(*args))
    for a in range(len(args)):
        for b in range(len(ziplist)):
            args[a][b]=ziplist[b][a]
def zipreverse(*args):
    ziplist=list(zip(*args))
    rev=[]
    for a in range(len(ziplist)-1,-1,-1):
        rev.append(ziplist[a])
    for a in range(len(args)):
        for b in range(len(rev)):
            args[a][b]=rev[b][a]

######################################################################################################
H,W,K=inputintlist()
G=[]
for a in range(H):
    G.append(input())
ans=0
for a in range(2**H):
    for b in range(2**W):
        cnt=0
        A=getbin(a,H)
        B=getbin(b,W)
        for i in range(H):
            for j in range(W):
                if A[i]==0 and B[j]==0:
                    if G[i][j]=="#":
                        cnt+=1
        if cnt==K:ans+=1
print(ans)

Submission status: Accepted

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

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

def check(grid, imask, jmask):
    black = 0
    for ii in range(h):
        for jj in range(w):
            if (1 << ii) & imask == 0 and (1 << jj) & jmask == 0 and grid[ii][jj] == '#':
                black += 1
    return black


cnt = 0
for imask in range(1 << h):
    for jmask in range(1 << w):
        t = check(grid, imask, jmask)
        if t == k:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def main():
    h, w, k = map(int, input().split())
    grid = [input() for _ in [0]*h]
    cnt = 0
    for i in range(2**h):
        yoko = []
        for t in range(h):
            if (i >> t) & 1:
                yoko.append(t)
        for j in range(2**w):
            tate = []
            for t in range(w):
                if (j >> t) & 1:
                    tate.append(t)
            red = [[0]*w for _ in [0]*h]
            for t in yoko:
                for l in range(w):
                    red[t][l] = 1
            for t in tate:
                for l in range(h):
                    red[l][t] = 1
            ans = 0
            for t in range(h):
                for t2 in range(w):
                    if red[t][t2] == 0 and grid[t][t2] == "#":
                        ans += 1
            if ans == k:
                cnt += 1
    print(cnt)


main()

Submission status: Accepted

Solution code:
# ABC173c


def main():
    import sys
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    def dump(*args):
        sys.stderr.write(str(args))

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

    def yoko(i):
        if i >= w:
            return 1 if sum([c[i].count('#') for i in range(h)]) == k else 0
        ans = yoko(i+1)
        for j in range(h):
            t = c[j][i]
            if t == '#':
                c[j][i] = 1
            elif t == 1:
                c[j][i] = 2
        ans += yoko(i + 1)
        for j in range(h):
            t = c[j][i]
            if t == 1:
                c[j][i] = '#'
            elif t == 2:
                c[j][i] = 1
        return ans

    def tate(i):
        if i >= h:
            return yoko(0)
        ans = tate(i+1)
        for j in range(w):
            t = c[i][j]
            if t == '#':
                c[i][j] = 1
        ans += tate(i + 1)
        for j in range(w):
            t = c[i][j]
            if t == 1:
                c[i][j] = '#'
        return ans

    print(tate(0))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
h, w, k = map(int, input().split())
c = [list(input()) for _ in range(h)]
ans = 0
for bi in range(1 << h):
    for bj in range(1 << w):
        d = [[""] * w for _ in range(h)]
        for i in range(h):
            for j in range(w):
                d[i][j] = c[i][j]
        for i in range(h):
            if ~bi >> i & 1:
                continue
            for j in range(w):
                d[i][j] = "r"
        for j in range(w):
            if ~bj >> j & 1:
                continue
            for i in range(h):
                d[i][j] = "r"
        s = 0
        for i in range(h):
            for j in range(w):
                if d[i][j] == "#":
                    s += 1
        if s == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H,W,K = list(map(int,input().split()))
cells = [input() for i in range(H)]
ans = 0
for i in range(2**H):
    for j in range(2**W):
        cnt = 0
        for a in range(H):
            for b in range(W):
                if i>>a & 1 or j>>b & 1: #塗る
                    continue
                else:
                    if cells[a][b] == "#":
                        cnt += 1
        if cnt == K:
            ans += 1

print(ans)