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:

# Author : raj1307 - Raj Singh
# Date   : 05.07.2020

from __future__ import division, print_function

import os,sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def msi(): return map(str,input().strip().split(" "))
def li():  return list(mi())

def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()
    
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import log,sqrt,factorial,cos,tan,sin,radians
#from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
#from decimal import *
#import threading
#from itertools import permutations
#Copy 2D list  m = [x[:] for x in mark] .. Avoid Using Deepcopy

abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[1] 
def sort2(l):return sorted(l, key=getKey,reverse=True)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))

def ceil(x,y):
    if x%y==0:
        return x//y
    else:
        return x//y+1

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
    
def isPrime(n) : # Check Prime Number or not 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True



def read():
    sys.stdin  = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 




def main():
    


    #for _ in range(ii()):



    n,m,k=mi()
    s=[]
    for i in range(n):
        s.append(si())

    cnt=0
    for i in range(n):
        for j in range(m):
            if s[i][j]=='#':
                cnt+=1

    ans=0
    for i in range(2**(n+m)):

        row=[]
        col=[]


        for j in range(n+m):

            if j>=n and i&(1<<j):
                col.append(j-n)
            if j<n and i&(1<<j):
                row.append(j)


        e=[]

        for j in range(len(row)):



            for l in range(m):

                if s[row[j]][l]=='#':
                    if [row[j],l] not in e:
                        e.append([row[j],l])


        for j in range(len(col)):

            for l in range(n):
                #print(l,col[j])
                if s[l][col[j]]=='#':
                    if [l,col[j]] not in e:
                        e.append([l,col[j]])

        
        ex=len(e)

        if cnt-ex==k:
                #print(row,col)
            ans+=1

    print(ans)











    








# region fastio
# template taken from https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py

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


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

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

# endregion


if __name__ == "__main__":
    #read()
    main()
    #dmain()

# Comment Read()

Submission status: Accepted

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

C = [list(input()) for _ in range(H)]

hbit = [[0]*H for _ in range(2**H)]
wbit = [[0]*W for _ in range(2**W)]

for i in range(2**H):
    for j in range(H):
        if ((i >> j)&1):
            hbit[i][j] = 1

for i in range(2**W):
    for j in range(W):
        if ((i >> j)&1):
            wbit[i][j] = 1

ans = 0
for hbi in range(2**H):
    for wbi in range(2**W):
        tmp = 0
        for i in range(H):
            for j in range(W):
                if hbit[hbi][i] or wbit[wbi][j]:
                    continue
                if C[i][j] =="#":
                    tmp += 1
        if tmp == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
c = []
for i in range(H):
    c.append(list(input()))
ans = 0
for i in range(2 ** H):
    dh = [True] * H
    for j in range(H):
        if (i >> j) & 1:
            dh[j] = False
    for j in range(2**W):
        dw = [True] * W
        for k in range(W):
            if (j >> k) & 1:
                dw[k] = False
        cnt = 0
        for k in range(H):
            for l in range(W):
                #print(k,l,dh,dw)
                if dh[k] == True and dw[l] == True and c[k][l] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w, k = MAP()
s = [input() for i in range(h)]
n = h + w

ans = 0
for i in range(2**n):
    a = []
    for j in range(n):
        a.append(( i >> j ) & 1)
    reg = 0
    for j in range(h):
        for l in range(w):
            if s[j][l] == '#' and a[j]&a[h+l]==1:
                reg += 1
    if reg == k:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def c_h_and_v():
    from itertools import combinations
    H, W, K = [int(i) for i in input().split()]
    C = [input() for _ in range(H)]

    ans = 0
    for row_num in range(H + 1):
        for rows in combinations(range(H), row_num):
            for col_num in range(W + 1):
                for cols in combinations(range(W), col_num):
                    tmp = 0
                    for r in range(H):
                        for c in range(W):
                            if r in rows or c in cols:
                                continue
                            if C[r][c] == '#':
                                tmp += 1
                    if tmp == K:
                        ans += 1

    return ans

print(c_h_and_v())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def simulate(mh, mw, H, W, K, grid):
    flags = [[1 for _ in range(W)] for _ in range(H)]
    for h in range(H):
        if not (mh>>h)&1:
            continue
        for w in range(W):
            flags[h][w] = 0
    for w in range(W):
        if not (mw>>w)&1:
            continue
        for h in range(H):
            flags[h][w] = 0
    cnt = 0
    for h in range(H):
        for w in range(W):
            if flags[h][w] and grid[h][w] == '#':
                cnt += 1
    if cnt == K:
        # print(flags)
        # print(mh, mw)
        return 1
    return 0

def main():
    H, W, K = rli()
    grid = []
    for i in range(H):
        grid.append(input())
    ans = 0
    for mh in range(0, 2**H):
        for mw in range(0, 2**W):
            ans += simulate(mh, mw, H, W, K, grid)
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	H,W,K = inputMap()
	maps = []
	for i in range(H):
		s = inputStr()
		maps.append(s)

	ans = 0
	for i in range(2**H):
		iBin = bin(i)[2:]
		pl = ""
		for ttt in range(len(iBin), H):
			pl += "0"
		iBin = pl + iBin
		iBin = iBin[::-1]
		for j in range(2**W):
			jBin = bin(j)[2:]
			pl = ""
			for ttt in range(len(jBin), W):
				pl += "0"
			jBin = pl + jBin
			jBin = jBin[::-1]

			kuro = 0
			for iii,mapH in enumerate(maps):
				if iBin[iii] == "1":
					continue
				for jjj,mapW in enumerate(mapH):
					if jBin[jjj] == "1":
						continue
					if mapW == "#":
						kuro += 1
			#print(kuro)
			if kuro == 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
import itertools
for i in itertools.product([0, 1], repeat=h):
    for j in itertools.product([0, 1], repeat=w):
        cnt = 0
        for y in range(h):
            for x in range(w):
                if i[y] == 0 and j[x] == 0 and c[y][x] == '#':
                    cnt += 1
        if cnt == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
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):
    r = 0
    for k in range(H):
      if ((i >> k) & 1):
        for l in range(W):
          if ((j >> l) & 1):
            if c[k][l] == "#":
              r += 1
    if r == K:
      ans += 1
      
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
C = []
for _ in range(H):
    C.append(list(input()))
# print(f'{C=}')

# ビット全探索
# 147,456回なので各セルを毎回サーチする
ans = 0
for H_bit in range(1 << H):
    H_idx = []
    for i in range(H):
        if H_bit & (1 << i):
            H_idx.append(i)
    # print(f'{H_bit=}, {H_idx=}')

    for W_bit in range(1 << W):
        W_idx = []
        for i in range(W):
            if W_bit & (1 << i):
                W_idx.append(i)

        # print(f'{H_idx=}, {W_idx=}')

        cnt = 0
        for i in range(H):
            for j in range(W):
                if i not in H_idx and j not in W_idx and C[i][j] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:

import copy
H,W,K=map(int,input().split())
C=[]
for h in range(H):
    c=list(input())
    C.append(c)
ans=0
for i in range(2**(H+W)):
    c=copy.deepcopy(C)
    cnt=0
    for w in range(W):
        if i%2==1:
            for h in range(H):
                c[h][w]="R"
        i//=2
    for h in range(H):
        if i%2==1:
            for w in range(W):
                c[h][w]="R"
        i//=2
    
    for h in range(H):
        for w in range(W):
            if c[h][w]=="#":
                cnt+=1
    if cnt==K:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product
input = lambda: sys.stdin.readline().rstrip()

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

def check(sh, sw):
   cnt = 0
   for i in range(h):
      if sh[i]:
         continue
      for j in range(w):
         if sw[j]:
            continue
         if c[i][j] == "#":
            cnt += 1
   return cnt

ans = 0
for p1 in product(range(2), repeat=w):
   for p2 in product(range(2), repeat=h):
      if check(p2, p1) == k:
         ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

h, w, k = map(int, input().split())
c = []
black = 0
for _ in range(h):
    c.append(list(input()))
for i in c:
    black += i.count("#")

cnt = 0
for i in range(2**h):
    s = set()
    delete = 0
    i_bin = bin(i)[2:].zfill(h)
    for x in range(h):
        if i_bin[x] == "1":
            for y in range(w):
                if c[x][y] == "#":
                    delete += 1
                    s.add(x)
    for j in range(2**w):
        delete_ = delete
        j_bin = bin(j)[2:].zfill(w)
        for y in range(w):
            if j_bin[y] == "1":
                for x in range(h):
                   
                    if x not in s and c[x][y] == "#":
                        delete_ += 1
        if black - delete_ == k:
            cnt += 1
print(cnt)

Submission status: Accepted

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

ans = 0
from itertools import product
for i in product(range(2), repeat=h):
  for j in product(range(2), repeat=w):
    temp = 0
    for a in range(h):
      for b in range(w):
        if i[a]==1 and j[b]==1 and c[a][b]=="#":
          temp+=1
    if temp == k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
C = []
for i in range(H):
    C.append(input())
A = 0
for i in range(H):
    for j in range(W):
        if C[i][j] == "#":
            A += 1
cnt = 0
for i in range(2**H):
    I = bin(i)[2:]
    I = "0"*(H-len(I))+I
    for j in range(2**W):
        J = bin(j)[2:]
        J = "0"*(W-len(J))+J
        A1 = A
        for i1 in range(len(I)):
            if I[i1] == "0":
                continue
            for i2 in range(W):
                if C[i1][i2] == "#":
                    A1 -= 1
        for j1 in range(len(J)):
            if J[j1] == "0":
                continue
            for j2 in range(H):
                if C[j2][j1] == "#":
                    A1 -= 1
        for i1 in range(len(I)):
            if I[i1] == "0":
                continue
            for j1 in range(len(J)):
                if J[j1] == "0":
                    continue
                if C[i1][j1] == "#":
                    A1 += 1
        if A1 == K:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    h,w,k2=map(int,input().split())
    c=[]
    for i in range(h):
        temp=list(input())
        c.append(temp)

    for i in range(h):
        for j in range(w):
            if c[i][j]==".":
                c[i][j]=0
            else:
                c[i][j]=1
#    print(c)
    count=0
    orig=copy.deepcopy(c)
    for i in itertools.product(range(2),repeat=h):
        for j in itertools.product(range(2), repeat=w):
            c=copy.deepcopy(orig)
            for l in range(h):
                for k in range(w):
                    if i[l]==1:
                        c[l][k]=0
                    if j[k]==1:
                        c[l][k]=0
            temp=0
            for l in range(h):
                temp+=sum(c[l])
            if temp==k2:
                count+=1
    print(count)


if __name__ == "__main__":

    main()

Submission status: Accepted

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


    H = list(range(h))
    W = list(range(w))

    ans = 0
    for i in range(h+1):
        for t in itertools.combinations(H,i):
            t = set(t)
            for j in range(w+1):
                for t2 in itertools.combinations(W,j):
                    t2 = set(t2)

                    count = 0
                    for x in range(h):
                        if not x in t:
                            for y in range(w):
                                if not y in t2:
                                    if C[x][y] == '#':
                                        count += 1

                    if count == k:
                        ans += 1


    print(ans)




main()

Submission status: Accepted

Solution code:
from itertools import product

h, w, K = map(int, input().split())
fld = [input()for _ in range(h)]
ans = 0
for i in product([0, 1], repeat=h):
    for j in product([0, 1], repeat=w):
        cnt = 0
        for k in range(h):
            if not i[k]:
                continue
            row = fld[k]
            for l in range(w):
                if not j[l]:
                    continue
                if row[l] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
###==================================================
### import
#import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
#import string
import sys
### stdin
def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

H, W, K = iInM()
C = []
for _ in range(H):
  C.append(list(input()))
#print(C)

ans = 0
for i in range(2**H):
    h_lst = []
    for k in range(H):
       if (i >> k) & 1:
           h_lst.append(k)

    for j in range(2**W):
        w_lst = []
        for k in range(W):
            if (j >> k) & 1:
                w_lst.append(k)
        
        #print(h_lst, w_lst)
        ## 以下、hとwを選んだ列として処理する
        cnt = 0
        for h in h_lst:
            for w in w_lst:
                #print(h, w)
                if C[h][w] == '#':
                    cnt += 1
        if cnt == K:
            ans += 1


print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

ans = 0
for i in range(2**H):
    for j in range(2**W):
        c2 = deepcopy(c)
        for k in range(H):
            c2[k] = list(c2[k])

        for k in range(i):
            if (i >> k) % 2:
                for l in range(W):
                    c2[k][l] = '.'

        for k in range(j):
            if (j >> k) % 2:
                for l in range(H):
                    c2[l][k] = '.'

        black = 0
        for k in range(H):
            for l in range(W):
                if c2[k][l] == '#':
                    black += 1

        if black == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

h_kumiawase = list(product([1, 0], repeat=h))
w_kumiawase = list(product([1, 0], repeat=w))

C = [list(input()) for _ in range(h)]
# C[h][w]


def calc(h_kumi, w_kumi):
    cnt = 0
    for i in range(h):
        if h_kumi[i] == 1:
            continue
        for j in range(w):
            if w_kumi[j] == 1:
                continue
            if C[i][j] == ".":
                continue
            cnt += 1
    return cnt


ans = 0
for i in range(1 << h):
    h_kumi = h_kumiawase[i]
    for j in range(1 << w):
        w_kumi = w_kumiawase[j]

        if calc(h_kumi, w_kumi) == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy

h, w, k = map(int, input().split())
c = []
for i in range(h):
    c.append(list(input()))
bin_h = 2 ** h
bin_w = 2 ** w
count = 0
for i in range(bin_h):
    for j in range(bin_w):
        c0 = copy.deepcopy(c)
        h0 = bin(i + 2 ** (h + 1))[4:]
        w0 = bin(j + 2 ** (w + 1))[4:]
        for l in range(h):
            for m in range(w):
                if h0[l] == "1":
                    for n in range(w):
                        c0[l][n] = "."
                if w0[m] == "1":
                    for n in range(h):
                        c0[n][m] = "."
        num = 0
        for l in range(h):
            for m in range(w):
                if c0[l][m] == "#":
                    num += 1
        if num == k:
            count += 1
print(count)

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):
        cnt = 0
        for ii in range(h):
            for jj in range(w):
                if (i >> ii) & 1 == 0 and (
                        j >> jj) & 1 == 0 and C[ii][jj] == '#':
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

H,W,K = map(int,S().split())
c = [LS2() for i in range(H)]
for i in range(H):
    for j in range(W):
        if c[i][j] == '.':
            c[i][j] = 0
        else:
            c[i][j] = 1

from copy import deepcopy

ans = 0
for i in range(2**H):
    A = []
    for k in range(H):
        if (i>>k)&1:
            A.append(k)
    for j in range(2**W):
        B = []
        for l in range(W):
            if (j>>l)&1:
                B.append(l)
        d = deepcopy(c)
        for k in range(H):
            for l in range(W):
                if k in A or l in B:
                    d[k][l] = 0
        if sum(sum(d[k]) for k in range(H)) == K:
            ans += 1

print(ans)

Submission status: Accepted

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

C=[]
for h in range(H):
    c=list(input())
    C.append(c)
#print(C)
ans=0
for i in range(2**H):
    for j in range(2**W):
        now=np.array(C.copy())
        for h in range(H):
            if i>>h&1==1:
                now[h,:]="."
        for w in range(W):
            if j>>w&1==1:
                now[:,w]="."
        sub=(now=="#").sum()
        #print(sub, now)
        if sub==K:
            ans+=1

print(ans)