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: Wrong Answer

Solution code:
import os
import sys
from io import BytesIO, IOBase
# from collections import defaultdict as dd
# from collections import deque as dq
# import itertools as it
# from math import sqrt, log, log2
# from fractions import Fraction
from itertools import chain, combinations

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

def main():
    h, w, k = map(int, input().split())
    mat = []
    rowcount = dict()
    colcount = dict()
    totcount = 0
    for r in range(h):
        row = input()
        rowcount[r] = row.count('#')
        totcount += rowcount[r]
        mat.append(list(row))
    
    transpose = list(map(list, zip(*mat)))
    for c in range(w):
        col = ''.join(transpose[c])
        colcount[str(c)] = col.count('#')
    
    diff = totcount - k
    if diff<0:
        print(0)
    if diff == 0:
        print(1)
    else:
        # diff > 0. Remove diff blacks.
        ans = 0
        allitems = list(rowcount.items()) + list(colcount.items())
        for subset in powerset(allitems):
            rows = []
            cols = []
            totrem = 0
            for item in subset:
                if isinstance(item[0], int):
                    rows.append(item)
                else:
                    cols.append(item)
                totrem += item[1]

            
            for r in rows:
                for c in cols:
                    elem = mat[r[0]][int(c[0])]
                    totrem -= 1 if elem == '#' else 0

            if totrem == diff:
                ans += 1

        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: Wrong Answer

Solution code:
a = list(map(int,input().split()))
b = [input() for l in range(a[0])]
ans = 0
cnt = 0
for i in range(a[0]):
    cnt += b[i].count('#')
if a[2] == cnt:
    ans += 1

cnt = 0
for i in range(a[0]):
    cnt = 0
    for j in range(a[0]):
        if i == j:
            continue
        else:
            cnt += b[j].count('#')
    
    if a[2] == cnt:
        ans += 1

for k in range(a[1]):
    cnt = 0
    for l in range(a[1]):
        if k == l:
            continue
        else:
            for m in range(a[0]):
                if b[m][l] == '#':
                    cnt += 1 
    if a[2] == cnt:
        ans += 1        
print(str(ans))

Submission status: Wrong Answer

Solution code:
import itertools

n, m, k = map(int, input().split())
w = []
for _ in range(n):
    w.append(input())

def _try(rows, cols):
    x = 0
    for i in range(n):
        for j in range(m):
            if i not in rows and j not in cols and w[i][j] == '#':
                x += 1
    return x == k

l = [('r', i) for i in range(n)] + [('c', i) for i in range(m)]

sol = 0
if _try([], []):
    sol += 1

for hm in range(1, k+1):
    for c in itertools.combinations(l, hm):
        irows = [i for t, i in c if t == 'r']
        icols = [i for t, i in c if t == 'c']
        if _try(irows, icols):
            sol += 1

print(sol)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split(" "))
maze = []
line = [0]*H
row = [0]*W
todel = 0
for i in range(H):
  maze.append(input())
for i in range(H):
  for j in range(W):
    if maze[i][j] == "#":
      line[i] += 1
      row[j] += 1
      todel += 1
todel = todel-K
l = [0]
for i in line:
  long = len(l)
  for j in range(long):
    l.append(l[j]+i) 
for i in row:
  long = len(l)
  for j in range(long):
    l.append(l[j]+i)
print(l.count(todel))

Submission status: Wrong Answer

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
2 3 2
..#
###
'''

def solve(L,H,W,K):
	R,C = [],[]
	rows = [i for i in range(H)]
	cols = [i for i in range(W)]
	for r in range(H+1):
		R.append(list(combinations(rows,r)))
	for c in range(H+1):
		C.append(list(combinations(cols,c)))
	RR,CC = [],[]
	for i in R:
		for j in i:
			jj = list(j)
			RR.append(jj)
	for i in C:
		for j in i:
			jj = list(j)
			CC.append(jj)
	ans = 0
	blacks = 0
	for i in range(H):
		for j in range(W):
			if(L[i][j] == '#'):
				blacks += 1
	for rc in RR:
		for cc in CC:
			curr = blacks
			for r in range(H):
				for c in range(W):
					if(r in rc or c in cc):
						if(L[r][c] == '#'):
							curr -= 1
			if(curr == K):
				ans += 1
	return ans



H,W,K = list(map(int, stdin.readline().rstrip().split()))
L = []
for i in range(H):
	L.append(list(input()))
ans = solve(L,H,W,K)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import numpy as np

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

matrix = []
for _ in range(h):
  matrix.append([1 if word=='#' else 0 for word in input()])

h_list = list(range(h))
w_list = list(range(w))

h_check_list = []
w_check_list = []
for i in range(h-1):
  h_check_list += list(combinations(h_list, i))
for i in range(w-1):
  w_check_list += list(combinations(w_list, i))

for h_paint in h_check_list:
  for w_paint in w_check_list:
    tmp = np.array(matrix.copy())
    for row in h_paint:
      tmp[row] = [0]*w
    for column in w_paint:
      for i in range(h):
        tmp[i][column] = 0
    if np.sum(tmp)==k:
      cnt+=1
print(cnt)

Submission status: Wrong Answer

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

print('1')

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W,K = IL()
data = SLs(H)
ans = 0
for h in range(1<<6):
  for w in range(1<<6):
    count = 0
    for i in range(H):
      for  j in range(W):
        if (h>>i)&1 and (w>>j)&1 and data[i][j] == "#":
          count += 1
    if count == K:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import numpy as np
    import itertools
    import copy

    H, W, K = map(int, input().split())
    table = []
    for _ in range(H):
        s = input()
        inte = []
        for i in range(W):
            if s[i] == '.':
                inte.append(0)
            else:
                inte.append(1)
        table.append(np.array(inte))

    ans = 0
    table = np.asarray(table)
    q_w = list(range(W))
    for i in range(2, W):
        P = itertools.combinations(q_w, i)
        for p in P:
            q_w.append(p)
    q_w.append(W)

    q_h = list(range(H))
    for i in range(2, H):
        P = list(itertools.combinations(q_h, i))
        for p in P:
            q_h.append(p)
    q_h.append(H)
    q = list(itertools.product(q_h, q_w))

    while len(q) != 0:
        temp = copy.deepcopy(table)
        idxs_h, idxs_w = q.pop(0)
        if idxs_h != H:
            temp[idxs_h] = [0 for k in range(W)]
        if idxs_w != W:
            temp[:, idxs_w] = [0 for k in range(H)]

        if np.sum(temp) == K:
            # print(idxs_h, idxs_w)
            # print(temp)
            ans += 1

    print(ans)

resolve()

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int,input().split())
C = [0]*H
 
for i in range(H):
    C[i] = list(str(input()))
    
 
    
def gyotsubushi(n,E):
    if I[n] == 1:
        E[n] = ['R']*W
        #print('GYO')
        
def retsutsubushi(n,E):
    if J[n] == 1:
        for i in range(H):
            E[i][n] = 'R'
stock = []
counter = 0
import copy
for i0 in range(2):
    for i1 in range(2):
        for i2 in range(2):
            for i3 in range(2):
                for i4 in range(2):
                    for i5 in range(2):
                        for j0 in range(2):
                            for j1 in range(2):
                                for j2 in range(2):
                                    for j3 in range(2):
                                        for j4 in range(2):
                                            for j5 in range(2):
                                                preI = [i0,i1,i2,i3,i4,i5]
                                                preJ = [j0,j1,j2,j3,j4,j5]
                                                I = preI[0:H]
                                                J = preJ[0:W]
                                                if I+J in stock:
                                                    break
                                                stock.append(I+J)
                                                D = copy.deepcopy(C)
                                                #print(D,I,J)
                                                for i in range(H):
                                                    gyotsubushi(i,D)
                                                for j in range(W):
                                                    retsutsubushi(j,D)
                                                #print(D)
                                                count = 0
                                                for i in range(H):
                                                    for j in range(W):
                                                        if D[i][j] == '#':
                                                            count += 1
                                                if count == K:
                                                    counter += 1
 
    
print(counter)

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int,input().split())
C = [0]*H

for i in range(H):
    C[i] = list(str(input()))
    

    
def gyotsubushi(n,E):
    if I[n] == 1:
        E[n] = ['R']*W
        #print('GYO')
        
def retsutsubushi(n,E):
    if J[n] == 1:
        for i in range(H):
            E[i][n] = 'R'
stock = []
counter = 0
import copy
for i0 in range(2):
    for i1 in range(2):
        for i2 in range(2):
            for i3 in range(2):
                for i4 in range(2):
                    for i5 in range(2):
                        for j0 in range(2):
                            for j1 in range(2):
                                for j2 in range(2):
                                    for j3 in range(2):
                                        for j4 in range(2):
                                            for j5 in range(2):
                                                preI = [i0,i1,i2,i3,i4,i5]
                                                preJ = [j0,j1,j2,j3,j4,j5]
                                                I = preI[0:H]
                                                J = preJ[0:W]
                                                if I+J in stock:
                                                    break
                                                stock.append(I+J)
                                                D = copy.deepcopy(C)
                                                #print(D,I,J)
                                                for i in range(H):
                                                    gyotsubushi(i,D)
                                                for j in range(W):
                                                    retsutsubushi(j,D)
                                                #print(D)
                                                count = 0
                                                for i in range(H):
                                                    for j in range(W):
                                                        if D[i][j] == '#':
                                                            count += 1
                                                if count == K:
                                                    counter += 1

    
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from copy import deepcopy
from dataclasses import dataclass, field
from typing import List


@dataclass
class Cell:
    i: int
    j: int
    color: str

    def to_red(self):
        return Cell(self.i, self.j, color='R')


@dataclass
class Board:
    cells: List[Cell] = field(default_factory=list)
    count: int = 0

    @classmethod
    def create(cls, H: int, W: int, C: List[str]):
        cells = []
        for i in range(H):
            for j in range(W):
                cell = Cell(i + 1, j + 1, C[i][j])
                cells.append(cell)

        return Board(cells)

    def count_black(self) -> int:
        return len([c for c in self.cells if c.color == '#'])

    def paint_row(self, row: int):
        new_cells = []

        for cell in self.cells:
            if cell.i == row:
                new_cells.append(cell.to_red())
            else:
                new_cells.append(cell)

        return Board(new_cells)

    def paint_col(self, col: int):
        new_cells = []

        for cell in self.cells:
            if cell.j == col:
                new_cells.append(cell.to_red())
            else:
                new_cells.append(cell)

        return Board(new_cells)


def actual(H, W, K, C):
    count = 0

    board_org = Board.create(H, W, C)

    patterns = list(itertools.product(range(2), repeat=H + W))

    for pattern in patterns:
        board = deepcopy(board_org)
        row_info = pattern[:H]
        col_info = pattern[H:]

        for row_idx, row in enumerate(row_info, start=1):
            if row == 1:
                board = board.paint_row(row_idx)

        for col_idx, col in enumerate(col_info, start=1):
            if col == 1:
                board = board.paint_col(col_idx)

        if board.count_black() == K:
            count += 1

    return count

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

print(actual(H, W, K, C))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

def combinationlist(n):
    p_sets = []
    for i in range(2 ** n):
        lst = [x + 1 for x in range(i) if 2 **x & i]
        if lst != []:
            p_sets.append(lst)
    p_sets = sorted(p_sets, key=lambda x: len(x))
    return p_sets


def main():
    data = input().split()
    h = int(data[0])
    w = int(data[1])
    k = int(data[2])
    c = np.empty((h,w),dtype=str)
    for i in range(h):
        s = input()
        c[i,:] = np.array([c for c in s])
    rowset = []
    colset = []
    all_black = 0
    for i in range(h):
        data = c[i,:]
        count = len(data[data == '#'])
        all_black += count
        rowset.append([count, data])
    for j in range(w):
        data = c[:,j]
        count = len(data[data=='#'])
        colset.append([count,data])
    ans = 0
    if k == all_black:
        ans += 1
    combList = combinationlist(h+w)
    for comb in combList:
        count = 0
        if all(np.array(comb) <= h):
            for i in  comb:
                count += rowset[i-1][0]
            if count == all_black - k:
                ans += 1
        elif all(np.array(comb) > h):
            for i in comb:
                count += colset[i-h-1][0]
            if count == all_black - k:
                ans += 1
        else:
            rows = []
            for i in comb:
                if i <= h:
                    count += rowset[i-1][0]
                    rows.append(i-1)
                else:
                    count += colset[i-h-1][0]
                    for j in rows:
                        if '#' == colset[i-h-1][1][j]:
                            count = count -1
            if count == all_black  - k:
                ans += 1
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0
for hl in product([0, 1], repeat=h):
    for wl in product([0, 1], repeat=w):
        cnt = 0
        for ci, hi in zip(c, hl):
            for cij, wj in zip(ci, wl):
                if hi == 0 and wj == 0:
                    cnt += (cij == '#')
        ans += (cnt == k)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from copy import deepcopy

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

ans = 0
for hl in product([0, 1], repeat=h):
    for wl in product([0, 1], repeat=w):
        cnt = 0
        cc = deepcopy(c)
        for ci, hi in zip(c, hl):
            for cij, wj in zip(ci, wl):
                if cij == '#' and hi == 0 and wj == 0:
                    cnt += 1
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

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

count = 0
import itertools
for r_paint in itertools.product([0,1], repeat=h): #0:その行を塗りつぶさない 1:その行を塗りつぶす
    for c_paint in itertools.product([0,1], repeat=w): # column
        kuro = 0 #黒塗りの数を数える
        for row in range(h):
            for col in range(w):
                if (fig[row][col] == "#") and (r_paint[row] == 0) and (c_paint[col] == 0): #黒いマスかつ塗りつぶされていない
                    kuro += 1
        if kuro == k:
            count += 1

print(count)

Submission status: Accepted

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

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

ans = 0
for i in range(1 << h):
    for j in range(1 << w):
        tmp = 0
        for i1 in range(h):
            for j1 in range(w):
                if (i >> i1) & 1: continue
                if (j >> j1) & 1: continue
                if field[i1][j1] != '#': continue
                tmp += 1
        if tmp == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0

for row_bit in product(range(2), repeat=h):
    for col_bit in product(range(2), repeat=w):
        tmp = 0
        for row in range(h):
            for col in range(w):
                if table[row][col] == "#" and (row_bit[row] and col_bit[col]):
                    tmp += 1
        if tmp == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c=[input() for i in range(h)]
ans=0
for i in range(2**h):
  for j in range(2**w):
    cnt=0
    for p in range(h):
      for q in range(w):
        if i&(1<<p) and j&(1<<q):
          if c[p][q]=='#':
            cnt+=1
    if cnt==k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
m=[list(input()) for i in range(h)]
o=0
for h_bit in range(2**h):
    for w_bit in range(2**w):
        c=0
        for i in range(h):
            for j in range(w):
                if (h_bit>>i)&1==0 and (w_bit>>j)&1==0 and m[i][j]=='#':
                    c+=1
        if c==k:
            o+=1
print(o)

Submission status: Accepted

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

ans = 0
for i in range(H+1):
    for j in range(W+1):
        for row in itertools.combinations([x for x in range(H)], i):
            for column in itertools.combinations([x for x in range(W)], j):
                tmp = 0
                for tr in range(H):
                    for tc in range(W):
                        if tr in row:
                            continue
                        if tc in column:
                            continue
                        if c[tr][tc] == '#':
                            tmp += 1
                if tmp == K:
                    ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for R in range(2**H):
    for C in range(2**W):
        n = 0
        for y in range(H):
            if R>>y&1:
                for x in range(W):
                    if C>>x&1:
                        if c[y][x]=="#":
                            n += 1
        if n==K:
          ans += 1
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
P=[]
for i in range(H):
    s=input()
    a=[]
    for j in range(W):
        a.append(s[j])
    P.append(a)
    
ans=0
for markR in range(2**H):
    for markC in range(2**W):
        black=0
        for i in range(H):
            for j in range(W):
                if (markR>>i)&1==0 and (markC>>j)&1==0 and P[i][j]=='#':
                    black+=1
        if black==K:
            ans+=1

print(ans)