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

from sys import stdin
input = lambda: stdin.readline().rstrip()


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

c = []

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

answer = 0
def count(h_target, w_target):
    cnt = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == '#' and h not in h_target and w not in w_target:
                cnt+=1
    if cnt == K:
        return 1
    else:
        return 0

h_format = '0' + str(H) + 'b'
w_format = '0' + str(W) + 'b'
for h in range(2**(H)):
    for w in range(2**(W)):
        #print("----1------")
        #print(list(format(h,h_format)))
        #print(list(format(w,w_format)))
        h_target = [n for n, v in enumerate(list(format(h,h_format))) if v == '1']
        w_target = [n for n, v in enumerate(list(format(w,w_format))) if v == '1']
        #print("----2-----")
        #print(h_target)
        #print(w_target)
        answer += count(h_target,w_target)

print(answer)

Submission status: Accepted

Solution code:
import copy

def paint_h(h, w, t):
    for i in range(w):
        t[h][i] = ' '

def paint_v(h, w, t):
    for i in range(h):
        t[i][w] = ' '

def count_b(h, w, t):
    total = 0
    for i in range(h):
        for j in range(w):
            if t[i][j] == '#':
                total += 1
    return total


h, w, k = [int(e) for e in input().split()]

m = []
for i in range(h):
    m.append(list(input()))

count = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        t = copy.deepcopy(m)
        
        for a in range(h):
            if i & (2 ** a) == (2 ** a):
                paint_h(a, w, t)
        for a in range(w):
            if j & (2 ** a) == (2 ** a):
                paint_v(h, a, t)
        
        if k == count_b(h, w, t):
            count += 1

print(count)

Submission status: Accepted

Solution code:
import copy
ans=0
h,w,k=map(int,input().split())
cc=[list(input()) for i in range(h)]
for bit in range(1 << h):
  ccc=copy.deepcopy(cc)
  for i in range(h):
    if bit & (1 << i):
       ccc[i]=["!"]*w 
  for bit in range(1 << w):
    cccc=copy.deepcopy(ccc)
    for i in range(w):
      if bit & (1 << i):
        for j in range(h):
          cccc[j][i]="!"
    count0=0
    for i in range(h):
      count0+=cccc[i].count("#")
    if count0==k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations, chain, product

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

h_patterns = list(chain.from_iterable([set(combinations(range(H), i)) for i in range(H+1)]))
w_patterns = list(chain.from_iterable([set(combinations(range(W), i)) for i in range(W+1)]))

ans = 0
for h_pattern, w_pattern in product(h_patterns, w_patterns):
    
    count = 0
    for i in range(H):
        for j in range(W):
            if i in h_pattern or j in w_pattern:
                continue
            if board[i][j] == '#':
                count += 1
    
    if count == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy


def main():
    H, W, K = input_ints()

    c = []

    count = 0

    for _ in range(H):
        s = input()
        li = []
        for chara in s:
            li.append(chara == '#')

        c.append(li)

    for i in range(2 ** (H+W)):
        c2 = copy.deepcopy(c)

        for j in range(W):
            if (i >> j) & 1:
                for k in range(H):
                    c2[k][j] = False

        for j in range(H):
            if (i >> (j+W)) & 1:
                for k in range(W):
                    c2[j][k] = False

        black = 0
        for i in range(H):
            for j in range(W):
                if c2[i][j]:
                    black += 1

        if black == K:
            count += 1

    print(count)


def input_ints():
    line_list = input().split()

    if len(line_list) == 1:
        return int(line_list[0])
    else:
        return map(int, line_list)


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


def input_int_tuple_list(n: int):
    return [tuple(map(int, input().split())) for _ in range(n)]


main()

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
C=[input() for i in range(H)]
count=0
for i in range(2**(H+W)):
    tate=[]
    yoko=[]
    for j in range(W):
        if ((i >> j)&1)==True:
            for k in range(H):
                tate.append((k,j))
    for j in range(W,H+W):
        if ((i >> j)&1)==True:
            for k in range(W):
                yoko.append((j-W,k))
    kyo=set(tate) & set(yoko)
    itti=0
    if len(kyo)!=0:
        for items in kyo:
            if C[items[0]][items[1]]=="#":
                itti+=1
        if itti==K:
            count+=1
print(count)

Submission status: Accepted

Solution code:
import numpy as np
h, w, k = map(int, input().strip().split())
cs = [list(input().strip()) for _ in range(h)]
grid = np.zeros((h, w), dtype=np.int)
for i, row in enumerate(cs):
    for j, cell in enumerate(row):
        if cell == '#':
            grid[i, j] = 1


def count_black(grid, bits_row, bits_col):
    mask = np.ones((h, w), dtype=np.int)
    for i in range(h):
        bit = bits_row >> i & 1
        if bit:
            mask[i] = 0
    for j in range(w):
        bit = bits_col >> j & 1
        if bit:
            mask[:, j] = 0

    return np.sum(grid * mask)

count = 0
for b_row in range(2 ** h):
    for b_col in range(2 ** w):
        c = count_black(grid, b_row, b_col)
        if c == k:
            count += 1

print(count)

Submission status: Accepted

Solution code:
from itertools import product

H, W, K = map(int, input().split(' '))
maze = [input() for i in range(H)]
ans = 0
cnt = 0
for i in range(pow(2,H+W)):
    cnt += 1
    i = format(i,'0{}b'.format(H+W))
    h = list(i[:H])
    w = list(i[H:])
    tmp = 0
    for j in range(H):
        for k in range(W):

            if h[j] == w[k] == '0' and maze[j][k] == '#':
                tmp += 1
    if tmp == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

h, w, k = map(int, input().split())
cs = []
ans = 0

def count_sharps(tmp):
  sharp = 0
  for y in range(h):
    sharp += tmp[y].count("#")
  if sharp == k:
    return True
  else:
    return False



for _ in range(h):
  cs.append(list(input()))

for i in range(2 ** h):
  for j in range(2 ** w):
    tmp = copy.deepcopy(cs)
    for p in range(h):
      if ((i >> p) & 1):
        for x in range(w):
          tmp[p][x] = "r"
    for q in range(w):
      if ((j >> q) & 1):
        for y in range(h):
          tmp[y][q] = "r"

    if count_sharps(tmp):
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
from copy import deepcopy
def resolve():
    H,W,K=pin()
    maze=[list(input()) for a in range(H)]
#    print(maze)

    #double bit full search
    ans=0
    for i in range(2**H):
        for j in range(2**W):
            #i,j is a set such that not colored red
            notred=[]
            numh=[0]*W
            #Height
            for ci in range(H):
                check=1<<ci
                if i & check:
                    #nukiidasi
                    for k in range(W):
                        if maze[ci][k]=="#":
                            numh[k]+=1

            cal=0
            for cj in range(W):
                check=1<<cj
                if j & check:
                    cal+=numh[cj]
            if cal==K:ans+=1
    print(ans)

#%%submit!
resolve()

Submission status: Accepted

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

H, W, K = map(int, readline().split())
L = []
s = 0
for i in range(H):
  li = readline().strip()
  Li = []
  for j in range(W):
    if li[j] == "#":
      s += 1
      Li.append(1)
    else:
      Li.append(0)
  L.append(Li)
if s < K:
  print(0)
  exit()

h0 = ""
w0 = ""
for i in range(H):
  h0 += "0"
for i in range(W):
  w0 += "0"
h = 2**H
w = 2**W
ans = 0
for i in range(h):
  hi = (h0 + bin(i)[2:])[-H:]
  for j in range(w):
    wj  = (w0 + bin(j)[2:])[-W:]
    sij = 0
    for k in range(H):
      for l in range(W):
        if hi[k] != "1" and wj[l] != "1":
          sij += L[k][l]
    if sij == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    H,W,K = map(int, input().split())
    C = np.zeros((H,W), dtype='int8')
    for h in range(H):
        s = input()
        for i in range(len(s)):
            if s[i] == '.':
                C[h,i] = 0
            else:
                C[h,i] = 1

    t2 = 0
    count = 0
    while t2 < 2**(H+W):
        t = t2
        h = []
        w = []
        for i in range(H+W):
            if t&1 == 1:
                if i < H:
                    h += i,
                else:
                    w += (i-H),
            t = t >> 1
        a = np.delete(np.delete(C, h, 0), w, 1)
        c = np.count_nonzero(np.delete(np.delete(C, h, 0), w, 1))
        if c == K:
            count += 1
        t2+=1

    print(count)


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    H, W, K = map(int, input().split())
    field = ['' for _ in range(H)]
    for i in range(H):
        field[i] = input().rstrip()
    num_black = 0
    for i in range(H):
        for j in range(W):
            if field[i][j] == '#':
                num_black += 1
    ans = 0
    for bit in range(2**(H+W)):
        current = 'h'
        target_h = []
        target_w = []
        for i in range(H+W):
            if i < H:
                current = 'h'
            else:
                current = 'w'
            if bit & 1<<i:
                ord = i
                if current == 'w':
                    ord = i - H
                if current == 'h':
                    target_h.append(ord)
                else:
                    target_w.append(ord)
        cnt = 0
        for j in range(H):
            for k in range(W):
                if j in target_h or k in target_w:
                    if field[j][k] == '#':
                        cnt += 1
        if num_black - cnt == K:
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
from decimal import *

import numpy as np

import math

import collections
import itertools


def createmaiz(listh,listw,list):
    for i in range(h):
        if listh[i] == "1":
            for j in range(w):
                list[i][j] ="."
    for i in range(w):
        if listw[i] == "1":
            for j in range(h):
                list[j][i] ="."
    return  list


def calc(maiz):
    count = 0
    for i in maiz:
        for j in i:
            if j =="#":
                count +=1
    return count


if __name__ == '__main__':
    h,w,k = map(int, input().split())
    maiz = []
    for i in range(h):
        s = input()
        maiz.append(list(s))

    listh=[]
    for i  in itertools.product('01', repeat=h):
        listh.append(list(i))
    listw=[]
    for i in itertools.product('01', repeat=w):
        listw.append(list(i))
    ans = 0

    for i in listh:
        for j in listw:
            temp = copy.deepcopy(maiz)
            temp =createmaiz(i,j,temp)
            black = calc(temp)
            if black ==k:
                ans+=1
    print(ans)

Submission status: Accepted

Solution code:
import copy
M = []
H,W,K = map(int, input().split())  
for i in range(H):
    M.append(list(input()))

ans=0

for i in range(2 ** H):
    CM = copy.deepcopy(M)
    for j in range(H):  
        if ((i >> j) & 1):  
            for k in range(W):
                CM[j][k] = '.'
    for l in range(2 ** W):
        CCM = copy.deepcopy(CM)
        for m in range(W):
            if ((l >> m) & 1):
                for n in range(H):
                    CCM[n][m]='.'
        cnt = 0
        for n in range(H):
            for m in range (W):
                if CCM[n][m] == '#':
                    cnt += 1
        if cnt == K:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
a=[[]*w for ii in range(h)]
for ii in range(h):
  a[ii][:]=list(input())
"""
for ii in range(h):
  print(a[ii])
"""
def func(a,bmh,bmw):
  rr=0
  for ii in range(h):
    for jj in range(w):
      if rr>k:
        return(0)
      #print(bin((2**ii)&bmh),bin((2**ii)&bmw))
      if ((2**ii)&bmh)!=0:
        if ((2**jj)&bmw)!=0:
          #print(ii,jj,a[ii][jj],a[ii][jj]=="#",rr)
          if a[ii][jj]=="#":
            rr+=1
  #print(rr,k)
  if rr==k:
    return(1)
  else:
    return(0)
  
bh=2**h
bw=2**w
r=0
#print(bh,bw)
for ii in range(bh):
  for jj in range(bw):
    #print(ii,jj,r)
    r+=func(a,ii,jj)
print(r)

Submission status: Accepted

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

def generate_n_bit(n):
    bins= []
    for i in range(2**n):
        bins.append(list(str(format(i,'b').zfill(n))))
    
    return bins

h_all = generate_n_bit(h)
w_all = generate_n_bit(w)
ans = 0

field = [list(input()) for i in range(h)]

for i_l in h_all:
    for j_l in w_all:
        c  = 0 
        fields = copy.deepcopy(field)
       
        
        for i_i, i in enumerate(i_l):
            for j_i, j in enumerate(j_l):
            
                if i == '1':
                    for a in range(w):
                        fields[i_i][a] = 'r'
                    
                if j == '1':
                    for b in range(h):
                        fields[b][j_i] = 'r'
        
        for q in range(h):
            for e in range(w):
                if fields[q][e] == '#':
                    c += 1
       
        if c == k:
            ans += 1
        
        
                
print(ans)

Submission status: Accepted

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

ans = 0
'それぞれの選び方について'
for i in range(2 ** H):
    for j in range(2 ** W):
        cnt = 0
        for l in range(H):
            for m in range(W):
                if ((i >> l) & 1) and ((j >> m) & 1):
                    if maze[l][m] == '#':
                        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 = [list(input()) for _ in range(H)]

A = 0
for bit in range(2 ** H):
    D = deepcopy(c)
    for i in range(H):
        if (bit & (1 << i)):
            for k in range(W):
                D[i][k] = '.'
    for bit2 in range(2 ** W):
        E = deepcopy(D)
        for j in range(W):
            if (bit2 & (1 << j)):
                for k in range(H):
                    E[k][j] = '.'
        X = 0
        for k in range(H):
            X += E[k].count('#')
        if X == K:
            A += 1

print(A)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np

def funk(matrix, n, k, no_list, h, w):
    if n == 0:
        mask = np.ones((h, w))
        for i in range(h):
            if no_list[i] == 1:
                mask[i,] = 0
        for j in range(w):
            if no_list[h+j] == 1:
                mask[:,j] = 0
        if np.sum(matrix * mask) == k:
            return 1
        else:
            return 0
    ans = 0
    ans += funk(matrix, n - 1, k, no_list + [1], h, w)
    ans += funk(matrix, n - 1, k, no_list + [0], h, w)
    return ans

ans = 0
h, w, k = map(int, input().split())
n = h + w
matrix = np.zeros((h, w))
for i in range(h):
    line = input()
    for j in range(w):
        if line[j] == "#":
            matrix[i,j] = 1
        else:
            matrix[i,j] = 0
no_list = []
ans += funk(matrix, n, k, no_list, h, w)
print(ans)

Submission status: Accepted

Solution code:
import math
import bisect
import copy
#import time
import itertools
#map(int,input().split())
#int(x) for x in input().split()
#for _ in range(int(input()))
l=[]
h,w,k=map(int,input().split())
for i in range(h):
	l.append(list(input()))

ccc=0
black=0
bl=0
for i in range(h):
	for j in range(w):
		if l[i][j]=='#':
			bl+=1

a=[i for i in range(64)]
b=[i for i in range(64)]
c=list(itertools.product(a,b))
for i in range(len(c)):
	a1=bin(c[i][0])[2:]
	b1=bin(c[i][1])[2:]
	if len(a1)>h:
		continue
	if len(b1)>w:
		continue
	if len(a1)<h:
		a1='0'*(h-len(a1))+a1
	if len(b1)<w:
		b1='0'*(w-len(b1))+b1
	row=0
	col=0
	for i in range(h):
		if a1[i]=='0':
			continue
		for j in range(w):
			if l[i][j]=='#':
				row+=1

	for i in range(w):
		if b1[i]=='0':
			continue
		for j in range(h):
			if l[j][i]=='#' and a1[j]!='1':
				col+=1
	if row+col==bl-k:
		ccc+=1

print(ccc)

Submission status: Accepted

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

hw_lst = [0 for i in range(h+w)]
lst_map = []
for i in range(h):
  lst_map.append(list(input()))
ans = [0]

def dfs(i, lst, aa):
  if i == h+w:
    count = 0
    for ij in range(h):
      for j in range(w):
        if lst[ij] == 0 and lst[h+j] == 0 and lst_map[ij][j] == '#':
          count += 1
    if count == k:
      aa[0] += 1
    return

  a = lst.copy()
  dfs(i+1, a, aa)
  b = lst.copy()
  b[i] = 1
  dfs(i+1, b, aa)

dfs(0, hw_lst, ans)
print(ans[0])

Submission status: Accepted

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
import copy
#n = int(input())
h, w, K = map(int, sys.stdin.readline().split())
#s = input()
#A = list(map(int, sys.stdin.readline().split()))

l = []
for i in range(h):
    l.append(list(input()))

ans = 0
for i in range(2**(h+w)):
    b = format(i, "0"+str(h+w)+"b")
    m = copy.deepcopy(l)
    for j in range(h):
        if b[j] == "1":
            for k in range(w):
                m[j][k] = "R"

    for j in range(w):
        if b[h+j] == "1":
            for k in range(h):
                m[k][j] = "R"

    cnt = 0
    for j in range(h):
        for k in range(w):
            if m[j][k] == "#":
                cnt += 1



    if cnt == K:
        ans += 1


print(ans)

Submission status: Accepted

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

import itertools
h = list(itertools.product([0,1], repeat=H))
w = list(itertools.product([0,1], repeat=W))

ans = 0
for i in h:
    for j in w:
        tmp = 0
        for ii in range(H):
            for jj in range(W):
                if C[ii][jj] == '#' and i[ii] == 0 and j[jj] == 0:
                    tmp += 1
        if tmp == K:
            ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

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

C = np.array(C)
C = np.where(C == '.', 0, C)
C = np.where(C == '#', 1, C)
C = C.astype(np.int)

ans = 0

for h_bits in product(*[range(2) for _ in range(H)]):
    ch = C.copy()
    for i,h in enumerate(h_bits):
        if h == 1:
            ch[i] = 0
    for w_bits in product(*[range(2) for _ in range(W)]):
        cw = ch.copy()
        for j,w in enumerate(w_bits):
            if w == 1:
                cw[:,j] = 0
        if cw.sum() == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

def main(H, W, K, HW):
    ans = 0

    # もとのHWに含まれる黒の数を数える．
    n_all = sum(HW, []).count('#')

    # 組み合わせ生成
    comb_h = []
    comb_w = []
    for h in range(H):
        comb_h.extend(combinations([i for i in range(H)], h))
    for w in range(W):
        comb_w.extend(combinations([i for i in range(W)], w))

    # h行目にある黒の数を数える．
    for c_h in comb_h:
        n_h = 0
        for h in c_h:
            n_h += HW[h].count('#')

        # w行目にある黒の数を数える．
        for c_w in comb_w:
            n_w = 0
            n_hw = 0
            for w in c_w:
                for h in range(H):
                    if HW[h][w] == '#':
                        n_w += 1
                        if h in c_h:
                            n_hw += 1
            # print(c_h, c_w, n_h, n_w, n_hw)
            n_black = n_all - n_h - n_w + n_hw
            if n_black == K:
                ans += 1
    print(ans)

if __name__ == '__main__':
    H, W, K = list(map(int, input().split()))
    HW = []
    for h in range(H):
        HW.append(list(input()))
    main(H, W, K, HW)

Submission status: Accepted

Solution code:
def func ( L00 , x0 , H  , W  , K , c0 ) :

	if sum(L00) == K :
		c0[0] += 1 ; 

	for r in range ( x0 , H + W ) : 

		if r >= H :
			y = r - H 
			L =L00[:];
			for c in range ( H ) :
				if L[ c * W + y ] == 1 :
					L[c * W + y ] = 0 ;
			func ( L , r+1 , H , W , K , c0 ) ;

		else :
			L =L00[:];
			for c in range ( W ) :
				if L[r * W + c] == 1 :
					L[r  * W + c ] = 0 ;
			func ( L , r+1 , H , W , K , c0 ) ;




	


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

L00 = [] ;
for x in range ( H ) :
	for c in input().strip() :
		if c =='#' :
			L00.append ( 1 ) ;
		else :
			L00.append ( 0 ) ;

c0 = [0] ;
func ( L00 , 0 , H , W , K , c0 ) ;
print ( c0[0] ) ;

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
import numpy as np
import copy
c=[]
for i in range(H):
  c.append(list(input().replace('.','0').replace('#','1')))

def count(xdel,ydel,l):
  cnt=0
  for i in range(H):
      for j in range(W):
        if 2**i&ydel!=0 or 2**j&xdel!=0:
          l[i][j]=2
        if l[i][j]=='1':
          cnt+=1
          l[i][j]=1
        
  return cnt

result=0
for i in range(2**H):
  for j in range(2**W):
    l=copy.deepcopy(c)
    if count(j,i,l)==K:
      result+=1
print(result)

Submission status: Accepted

Solution code:
import math
import collections
import bisect
from copy import copy, deepcopy


def main():
    H, W, K = map(int, input().split())
    c = [None] * H
    for i in range(H):
        c[i] = list(input())

    ans = 0
    for i in range(2**(H)):
        c_ = deepcopy(c)
        for j in range(H):
            if((i >> j) & 1):
                for k in range(W):
                    c_[j][k] = "."
        for j in range(2**(W)):
            c__ = deepcopy(c_)
            for k in range(W):
                if((j >> k) & 1):
                    for l in range(H):
                        c__[l][k] = "."
            if K == sum(list(map(lambda x: x.count("#"), c__))):
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for ht in range(1 << h):
  for wt in range(1 << w):
    b = 0
    for i in range(h):
      # ht の bit = 1 は赤の行
      if ht & 1 << i:
        continue
      for j in range(w):
        # wt の bit = 1 は赤の列
        if wt & 1 << j:
          continue
        if c[i][j] == '#':
          b += 1
    if (b == k):
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
def tw(n,x):
  r=[0]*x
  i=0
  while (n>=2 and i<x-1):
    r[i]=n%2
    n=int(n/2)
    i+=1
  r[i]=n%2
  return r

H,W,K=input().split()
H,W,K=int(H),int(W),int(K)
c2=["."*W]*H
#print(c2)
for i in range(H): 
  tmp=input()
  #print(tmp)
  c2[i]=str(tmp)


a=2**(H+W)
cnt=0
for i in range(a):
  lis=tw(i,a)
  c=c2[:]
  for j in range(H):
    if lis[j]==1: c[j]="a"*W
  for j in range(W):
    if lis[H+j]==1: 
      for k in range(H): c[k]=c[k][:j]+"a"+c[k][j+1:]
  cnt2=0
  for s in range(H):
    for t in range(W):
      if c[s][t]=="#": cnt2+=1
  #print(cnt2)
  if cnt2==K: cnt+=1
print(cnt)

Submission status: Accepted

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

ans = 0

for i in range(2 ** (h + w)):
    white = 0
    wi = []
    he = []

    for j in range(h + w):
        if ((i >> j) & 1):
            if j < w:
                wi.append(j)
            else:
                he.append(j - w)

    for hei in range(h):
        for wid in range(w):
            if (not hei in he) and (not wid in wi) and c[hei][wid] == '#':
                white += 1

    if white == k:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
import numpy as np

def paint_red(array, rows, cols):
    ret = deepcopy(array)
    for i in rows:
        ret[i, :] = "r"
    for j in cols:
        ret[:, j] = "r"

    return ret

def get_idx(bins):
    indices = []
    for i, c in enumerate(reversed(bins)):
        if c == "1":
            indices.append(i)
    
    return indices

def is_terminated(array, n_blacks):
    actual_number = 0
    for i in range(array.shape[0]):
        for j in range(array.shape[1]):
            if array[i, j] == "#":
                actual_number += 1
    return n_blacks == actual_number

H, W, K = [int(x) for x in input().split()]
c = []
for i in range(H):
    row = [x for x in input()]
    c.append(row)
c = np.array(c)

n_solutions = 0
for counter in range(2 ** (H + W)):
    bins = bin(counter)[2:].zfill(H + W)
    rows = get_idx(bins[:H])
    cols = get_idx(bins[H:])

    painted = paint_red(c, rows, cols)
    if is_terminated(painted, K):
        n_solutions += 1

print(n_solutions)

Submission status: Accepted

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

c = []
for i in range(H):
    c.append(input())
a = []
for i in c:
    b = []
    for j in i:
        if j == '#':
            b.append(1)
        else:
            b.append(0)
    a.append(b)

col = []
r = list(range(H))
for i in range(H+1):
    col += itertools.combinations(r, i)

row = []
r = list(range(W))
for i in range(W+1):
    row += itertools.combinations(r, i)

ans = 0
for i in col:
    for j in row:
        tar = copy.deepcopy(a)
        for k in i:
            tar[k] = [0] * W
        for k in j:
            for t in tar:
                t[k] = 0
        n = 0
        for t in tar:
            for k in t:
                n += k
        if n == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# 全探索

import sys
readline=sys.stdin.readline

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

C = [None] * H
for i in range(H):
  C[i] = readline().rstrip()
  
def count_black(C,y,x):
  cnt = 0
  for i in range(H):
    for j in range(W):
      if C[i][j] == ".":
        continue
      # 黒の場合
      if y[i] != "1" and x[j] != "1":
        cnt += 1
  return cnt

# 色は塗らずに、カウントだけする
ans = 0
yketa = len(bin(H)[2:])
xketa = len(bin(W)[2:])

for y in range(2 ** H):
  yst = bin(y)[2:].zfill(H)
  for x in range(2 ** W):
    xst = bin(x)[2:].zfill(W)
    if count_black(C,yst,xst) == K:
      ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import copy
sys.setrecursionlimit(2147483647)

def main():
  H, W, K = map(int, input().split(' '))
  C = []
  for i in range(H):
    C.append(input())
  count = 0
  mani_row = []
  mani_col = []
  for i in range(2**H):
    for j in range(2**W):
      num = 0
      bini = format(i, f'0{H}b')
      binj = format(j, f'0{W}b')
      for h in range(H):
        for w in range(W):
          if(bini[h] == '0' and binj[w] == '0' and C[h][w] == '#'):
            num += 1
      if(num == K):
        count += 1
  print(count)






if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import copy

H, W, K = list(map(int,input().split()))
c = []
for i in range(H):
    c.append(input())
    
red = 0
cc = [[-1 for _ in range(W)] for j in range(H)]
for i in range(W):
    for j in range(H):
        if c[j][i] == ".":  cc[j][i] = 0
        else:  
            cc[j][i] = 1
            red += 1
            
def bit_all(red):
    ans = 0
    for x in range(2 ** W):
        for y in range(2 ** H):
            ccc = copy.deepcopy(cc)
            temp = 0
            b = str(format(x, '010b'))
            c = str(format(y, '010b'))
            
            for i in range(W):
                if b[-(i + 1)] == "1":
                    for ii in range(H):
                        if ccc[ii][i] == 1:
                            ccc[ii][i] = 0
                            temp += 1
                            
            for j in range(H):
                if c[-(j + 1)] == "1":
                    for ii in range(W):
                        if ccc[j][ii] == 1:
                            ccc[j][ii] = 0
                            temp += 1 
                            
            if red - temp == K:
                ans += 1
                
    return ans

ans = bit_all(red)
print(ans)

Submission status: Accepted

Solution code:
def combinationUtil(arr, n, r, index, data, i):
    global a
    if(index == r):
        tmp = []
        for j in range(r):
            tmp.append(data[j])
            # print(data[j], end = " ")
        a.append(tmp)
        # print(" ") 
        return
    if(i >= n): 
        return
    data[index] = arr[i] 
    combinationUtil(arr, n, r, index + 1, data, i + 1) 
    combinationUtil(arr, n, r, index, data, i + 1) 

def printcombination(arr, n, r):
    data = list(range(r)) 
    combinationUtil(arr, n, r, 0, data, 0)

h, w, k = map(int, input().split())
l = []
for i in range(h):
    s = list(input())
    l.append(s)
ans = 0
ro, col = [], []
for i in range(h): ro.append(i)
for i in range(w): col.append(i)


t1 = []
t2 = []
for i in range(h + 1):
    a = []
    printcombination(ro, h, i)
    for j in a: t1.append(j)

for i in range(w + 1):
    a = []
    printcombination(col, w, i)
    for j in a: t2.append(j)

# print(t1)
# print(t2)


for i in t1:
    for j in t2:
        cnt = 0
        for a in range(h):
            for b in range(w):
                if a in i or b in j: continue
                if l[a][b] == '#': cnt -= -1
        if cnt == k: ans -= -1
print(ans)