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

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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] == "
                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)

Solution (Python):
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)

Solution (Python):
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=[]                                     
tate=[]                                     
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)

Solution (Python):
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()

Solution (Python):


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

Solution (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

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)

Solution (Python):
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)

Solution (Python):
from sys import stdin, setrecursionlimit

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)

Solution (Python):
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)

Solution (Python):
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
    
    if(cnt == K):
      ans += 1
print(ans)

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

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)

Solution (Python):


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=='
    ans=0
    
    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)



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



if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):


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

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):



def main():
    import sys
    sys.setrecursionlimit(10**6)
    

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

Solution (Python):

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)

Solution (Python):
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)

Solution (Python):
def two(x,y):
	return (y-len(bin(x)[2:]))*"0"+bin(x)[2:]
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):
		H=two(i,h);W=two(j,w)
		cnt=0
		for k in range(h):
			for l in range(w):
				if c[k][l]=="
					cnt+=1
		if cnt==K:
			ans+=1
print(ans)

Solution (Python):
from itertools import combinations

import sys
input = sys.stdin.readline

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

M = []

for h in range(H):
    row = input()
    M.append(row)

L1 = list(range(H))
L2 = list(range(W))
answer = 0

for l1 in range(H+1):
    for s1 in combinations(L1, l1):
        for l2 in range(W+1):
            for s2 in combinations(L2, l2):
                s = 0
                for h in range(H):
                    if h in s1:
                        continue
                    for w in range(W):
                        if w in s2:
                            continue
                        if M[h][w] == '
                            s += 1
                if s == K:
                    answer += 1
print(answer)

Solution (Python):
h,w,k = map(int,input().split())
field = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "
            field[i][j] = 1



def tobin(x,n):
    return format(x,'b').zfill(n)



ans = 0
for i in range(2**h):
    for j in range(2**w):
        f1 = tobin(i,h)
        f2 = tobin(j,w)


        temp = 0
        for hoge in range(h):
            for l in range(w):
                if f1[hoge] == "0" and f2[l] == "0":
                    temp += field[hoge][l]
        if temp == k:
            ans += 1
            

print(ans)

Solution (Python):
from itertools import product
h, w, k = map(int, input().split())
c = [input() for _ in range(h)]
ans = 0
for bh in product((True, False), repeat=h):
    for bw in product((True, False), repeat=w):
        cnt = 0
        for i in range(h):
            if not bh[i]:
                continue
            for j in range(w):
                if not bw[j]:
                    continue
                cnt += c[i][j] == '
        ans += cnt == k
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
c = [None]*h
for i in range(h):
    c[i] = input()
ans = 0
for b1 in range(1<<h):
    for b2 in range(1<<w):
        val = 0
        for i in range(h):
            if b1>>i&1:
                continue
            for j in range(w):
                if b2>>j&1:
                    continue
                if c[i][j]=="
                    val += 1
        if val==k:
            ans += 1
print(ans)

Solution (Python):
import sys

def read_int():
    line = sys.stdin.readline().rstrip('\n')
    return int(line)

def read_int_list():
    line = sys.stdin.readline().rstrip('\n')
    return [int(e) for e in line.split(' ')]

def count(field, di, dj, H, W):
    ans = 0
    for i in range(H):
        if not (di & (1 << i)):
            continue
        for j in range(W):
            if not (dj & (1 << j)):
                continue
            if field[i][j] == '
                ans += 1
    return ans

H, W, K = read_int_list()
field = []
for _ in range(H):
    field.append(sys.stdin.readline().rstrip('\n'))

ans = 0
for di in range(2**H):
    for dj in range(2**W):
        count_k = count(field, di, dj, H, W)
        if count_k == K:
            ans += 1
print(ans)

Solution (Python):
from itertools import product

H, W, K = map(int, input().split())
grid = [input() for _ in range(H)]
ans = 0
for h, w in product(range(1 << H), range(1 << W)):
    temp = 0
    for i in range(H):
        if (h & (1 << i)):
            for j, c in enumerate(grid[i]):
                if (w & (1 << j)) and c == '
    if temp == K: ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 8)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    H, W, K = ZZ()
    c = [list(input()) for _ in range(H)]
    ans = 0
    for h in range(2 ** H):
        for w in range(2 ** W):
            hs = set()
            ws = set()
            for i in range(H):
                if h & (1 << i): hs.add(i)
            for i in range(W):
                if w & (1 << i): ws.add(i)
            cc = 0
            for i in range(H):
                for j in range(W):
                    if i in hs: continue
                    if j in ws: continue
                    if c[i][j] == '
            if cc == K: ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()

Solution (Python):
def resolve():
    H, W, K = [int(i) for i in input().split()]
    A = [input() for _ in range(H)]
    ans = 0
    for i in range(2**H):
        for ii in range(2**W):
            cnt = 0
            for j in range(H):
                for jj in range(W):
                    if (i >> j) & 1 and (ii >> jj) & 1:
                        if A[j][jj] == "
                            cnt += 1
            if cnt == K:
                ans += 1
    print(ans)

resolve()

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

cnt=0
for i in range(2**h):
    num_1=format(i,"b").zfill(h)
    for j in range(2**w):
        point=0
        B=[["*"]*w for _ in range(h)]
        num_2=format(j,"b").zfill(w)
        for v,m in enumerate(num_1):
            if m=="1":B[v]=["."]*w
        for v,m in enumerate(num_2):
            if m=="1":
                for l in range(h):
                    B[l][v]=["."]
        for j in range(h):
            for v in range(w):
                if B[j][v]=="*" and C[j][v]=="
                    point +=1
        if point==k:
            cnt +=1
print(cnt)