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:
h,w,k=map(int,input().split())
import numpy as np
L=[]
for i in range(h):
    l=list(input())
    for j in range(w):
        if l[j]=='#':
            l[j]=1
        else:
            l[j]=0
    L.append(l)
r=np.asarray(L)
ans=np.sum(r)-k
p=np.sum(r,axis=1)
q=np.sum(r,axis=0)
pp=[]
qq=[]
import itertools as it
for i in range(1,h+1):
    for j in it.combinations([x for x in range(h)],i):
        pp.append(j)
for i in range(1,w+1):
    for j in it.combinations([x for x in range(w)],i):
        qq.append(j)
ok=0
for t in it.product(pp,qq):
    s=0
    for pairs in it.product(t[0],t[1]):
        s += r[pairs[0]][pairs[1]]
    P=0
    for i in t[0]:
        P += p[i]
    Q=0
    for i in t[1]:
        Q += q[i]
    if P+Q-s==ans:
        ok += 1
for i in pp:
    num=0
    for j in i:
        num += p[j]
    if num==ans:
        ok += 1
for i in qq:
    num=0
    for j in i:
        num += q[j]
    if num==ans:
        ok += 1
if ans==0:
    ok += 1
print(ok)

Submission status: Accepted

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


def count(a):
    re = 0
    for n in a:
        for m in n:
            if m == "#":
                re += 1
    return re


result = 0
for i in range(2**H):
    for j in range(2**W):
        temp_c = copy.deepcopy(c)
        sh = format(i, "0" + str(H) + "b")
        sw = format(j, "0" + str(W) + "b")
        for z, s in enumerate(sh):
            if s == "1":
                temp_c[z] = ["." for x in range(W)]

        for z, s in enumerate(sw):
            if s == "1":
                for y in range(len(temp_c)):
                    temp_c[y][z] = "."
        res = count(temp_c)
        if res == K:
            result += 1

print(result)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
cnt = 0
cntrem = 0
answer = 0
b = []
flag = [[0] * w for _ in range(h)]
for i in range(h):
    b.append(input())
    cnt += b[i].count('#')
# print(cnt)
copy = b
for i in range(2 ** h):
    cntrem = 0
    flag = [[0] * w for _ in range(h)]

    for j in range(h):
        if (i >> j) & 1:
            cntrem += b[j].count('#')

            for roop_w in range(w):
                flag[j][roop_w] = 1
    # print('firstrem', end=' ')
    # print(cntrem)
    tmp = cntrem
    for ka in range(2 ** w):
        cntrem = tmp
        for l in range(w):
            if (ka >> l) & 1:
                for roop_h in range(h):
                    # print(flag)
                    # print(b[roop_h][l])
                    if flag[roop_h][l] == 0 and b[roop_h][l] == '#':
                        cntrem += 1

                # cntrem += b[j].count('#')

        # print(cnt - cntrem)
        if cnt - cntrem == k:
            answer += 1

print(answer)

Submission status: Accepted

Solution code:
import copy
from itertools import combinations
h, w, k = map(int, input().split())
lis =[input() for i in range(h)]
res = 0
x = []
for i in range(h):
    x.append(i)
y = []
for i in range(w):
    y.append(i)
for i in range(h+1):
    f = list(combinations(x, i))
    for j in range(w+1):
        g = list(combinations(y, j))
        for l in f:
            for m in g:
                count = 0
                for p in l:
                    for q in m:
                        if lis[p][q] == '#':
                            count += 1
                if count == k:
                    res += 1
print(res)

Submission status: Accepted

Solution code:
import itertools
import copy
h,w,k=map(int,input().split())
c=[list(input()) for _ in range(h)] 
num=0
for i in range(h):
    for j in range(w):
        if c[i][j]=='#':
            num+=1
ans=0
for a in range(1,h+1):
    for b in range(1,w+1):
        l=range(1,h+1)
        m=range(1,w+1)
        for p in itertools.combinations(l, a):
            for q in itertools.combinations(m, b):
                sum=0
                d=copy.deepcopy(c)
                for i in p:
                    for j in q:
                        for s in range(w):
                            if d[i-1][s]=='#':
                                sum+=1
                                d[i-1][s]='.'
                        for t in range(h):
                            if d[t][j-1]=='#':
                                sum+=1
                                d[t][j-1]='.'
                if num-sum==k:
                    ans+=1
for a in range(1,h+1):
        l=range(1,h+1)
        for p in itertools.combinations(l, a):
            sum=0
            d=copy.deepcopy(c)
            for i in p:
                for s in range(w):
                    if d[i-1][s]=='#':
                        sum+=1
                        d[i-1][s]='.'
            if num-sum==k:
                ans+=1
for b in range(1,w+1):
        m=range(1,w+1)
        for q in itertools.combinations(m, b):
            sum=0
            d=copy.deepcopy(c)
            for j in q:
                for t in range(h):
                    if d[t][j-1]=='#':
                        sum+=1
                        d[t][j-1]='.'
            if num-sum==k:
                ans+=1
if num==k:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 173: C - H and V
https://atcoder.jp/contests/abc173/tasks/abc173_c
"""

import copy


def debug_cells(cells):
    for col in cells:
        print(''.join(col))


def count_black(cells):
    count = 0
    for col in cells:
        count += col.count('#')
    return count


def draw_and_count(cells, xs, ys):
    for x in xs:
        for col in cells:
            col[x] = '@'
    for y in ys:
        for i in range(len(cells[y])):
            cells[y][i] = '@'
    # debug_cells(cells)
    return count_black(cells)


def main():
    H, W, K = list(map(int, input().split()))
    cells = [[0 for j in range(W)] for i in range(H)]
    for x in range(H):
        Cs = list(input())
        for y in range(W):
            cells[x][y] = Cs[y]

    Xs = []
    for i in range(2 ** W):
        Xs.append([j for j in range(W) if (i >> j) & 1])
    Ys = []
    for i in range(2 ** H):
        Ys.append([j for j in range(H) if (i >> j) & 1])

    # print(Xs)
    # print(Ys)
    ans = 0
    for xs in Xs:
        for ys in Ys:
            black_count = draw_and_count(copy.deepcopy(cells), xs, ys)
            if black_count == K:
                ans += 1
            # print('{}, {} => {}'.format(xs, ys, draw_lines(copy.deepcopy(cells), xs, ys)))
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

def main():
    h, w, k = map(int, input().split())
    c = [list(input()) for _ in range(h)]
    ans = solve(h, w, k, c)
    print(ans)

def solve(h, w, k, c):
    ans = 0
    for i in range(2 ** h):
        for j in range(2 ** w):
            cc = copy.deepcopy(c)
            for ii in range(h):
                if i >> ii & 1:
                    cc[ii] = ["!"] * w
            for jj in range(w):
                if j >> jj & 1:
                    for kk in range(h):
                        cc[kk][jj] = "!"
            tmp = [inner for outer in cc for inner in outer]
            if tmp.count('#') == k:
                ans += 1
    return ans

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
g = [input() for _ in range(H)]
ans = 0
for bit in range(2**(H + W)):
    cnt = 0
    for h in range(H):
        if (bit & (h << 1)):
            pass
        if ((bit >> h) & 1):
            #print(h,"cancel")
            continue
        for w in range(W):
            if (bit & (H + w << 1)):
                pass
            if ((bit >> H + w) & 1):
                continue
            if g[h][w] == '#':
                cnt += 1
                #print(h, w)
    if cnt == K:
        # print(bin(bit), "ok")
        # for i in range(H):
        #     print(g[i])
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,K=map(int,input().split())
c=[list(input()) for _ in range(h)]
ans=0
for i in range(2**h):
  cc=[]
  for j in range(h): 
    if ((i >> j) & 1):
      continue
    else:
      cc.append(c[j])
  cc=[list(x) for x in zip(*cc)]
  for k in range(2**w):
    ccc=[]
    for l in range(w): 
      if ((k >> l) & 1):
        continue
      else:
        if not cc==[]:
          ccc.append(cc[l])
    cnt=0
    for v in ccc:
      cnt+=v.count('#')
    if cnt==K:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
from copy import copy


def judge(color, rows, cols, H, W):
    h_ = list("_"*H)
    w_ = list("_"*W)
    for row in rows:
        color[row] = w_
    color = list(zip(*color))
    for col in cols:
        color[col] = h_
    color = sum(map(tuple, color), ())
    return color.count("#")


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

h_selector = []
w_selector = []
for i in range(H+1):
    h_selector.extend(list(combinations(range(H), i)))
for i in range(W+1):
    w_selector.extend(list(combinations(range(W), i)))

ans = 0
calc = 0
for rows in h_selector:
    for cols in w_selector:
        calc += 1
        t = copy(c)
        if judge(t, rows, cols, H, W) == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
ori=[]
for i in range(h):
  a=str(input())
  #a=a+"."
  ori.append(a)
#ori.append("........")
#print(ori)
t=[]
y=[]
for i in range(h):
  t.append(ori[i].count("#"))
#print(t)
total=sum(t)
#print(total)
for j in range(w):
  now=0
  for i in range(h):
    noww=str(ori[i])
    #print(j,i,noww[j])
    if noww[j]=="#":
      now+=1
  y.append(now)

  
#print(t,y)

import itertools

ans=0
check=0
listate = [i for i in range(h)]
lisyoko = [i for i in range(w)]
for n in range(1,len(listate)+1):
    for tat in itertools.combinations(listate, n):
      tate=list(tat)
      for n in range(1,len(lisyoko)+1):
        for yok in itertools.combinations(lisyoko, n):
          yoko=list(yok)

          now=total
          #print(tate,yoko)
          for j in yok:
            now-=y[j]
          for i in tate:
            now-=t[i]
            noww=str(ori[i])
            for j in yok:
              if noww[j]=="#":
                now+=1
          check+=1
          if now==k:
            ans+=1
            #print(tate,yoko)
            
for n in range(1,len(listate)+1):
    for tat in itertools.combinations(listate, n):
      tate=list(tat)
      now=total
      for i in tate:
        now-=t[i]
      check+=1
      if now==k:
        ans+=1
        #print(tate)

for n in range(1,len(lisyoko)+1):
  for yok in itertools.combinations(lisyoko, n):
    yoko=list(yok)
    now=total
    for i in yoko:
      now-=y[i]
    check+=1
    if now==k:
      ans+=1
      #print(yoko)
if total==k:
  ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy

h, w, z = map(int, input().split())
table = [['.' for j in range(w)] for i in range(h)]
ans = 0

for i in range(h):
    column = str(input())
    for j in range(w):
        table[i][j] = column[j]

tmp = h + w

for i in range(2**tmp):
    table_tmp = copy.deepcopy(table)
    count = 0

    for j in range(h):
        if (i >> j) & 1:
            for k in range(w):
                table_tmp[j][k] = 'x'

    for l in range(w):
        if (i >> (h + l)) & 1:
            for m in range(h):
                table_tmp[m][l] = 'x'

    for p in range(h):
        for q in range(w):
            if table_tmp[p][q] == '#':
                count += 1

    if count == z:
        ans += 1

print(ans)

Submission status: Accepted

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

row_black = [0]*H
column_black = [0]*W
row_position = []
column_position =[]
full = 0
res = 0
for i in range(H):
    row_position.append([])
for j in range(W):
    column_position.append([])

for i in range(H):
    s = list(input())
    for j in range(W):
        if s[j] =="#":
            row_black[i] +=1
            column_black[j] +=1
            row_position[i].append(j)
            column_position[j].append(i)
            full +=1

n = H+W

for i in range(2**n):
    r = copy.copy(row_black)
    c = copy.copy(column_black)
    temp = 0
    for j in range(n):
        if i & (1<<j):
            if(j<H):
                temp += r[j]
                r[j] = 0
                for k in row_position[j]:
                    c[k] -=1
            else:
                temp += c[j-H]
                c[j-H] = 0
                for k in column_position[j-H]:
                    r[k] -=1
        if full - temp < K:
            break
    if full - temp == K:
        res +=1

print(res)

#print(row_black)
#print(column_black)
#print(row_position)
#print(column_position)

Submission status: Accepted

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,itertools
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################

def solve():
    h,w,k = invr()
    a = []
    qq = [i + 1 for i in range(h)]
    ww = [i + 1 for i in range(w)]
    for i in range(h):
        s = insr()
        a.append(s)
    r = [0] * h
    c = [0] * w
    b = transpose(a)
    qwqw = 0
    for i in range(h):
        r[i] = a[i].count("#")
    for i in range(w):
        c[i] = b[i].count("#")
    qqww = sum(r)
    for i in range(7):
        q = list(itertools.combinations(qq,i))
        for j in range(len(q)):
            for ii in range(7):
                w = list(itertools.combinations(ww,ii))
                for jj in range(len(w)):
                    qw = 0
                    for ij in range(i):
                        qw = qw + r[q[j][ij] - 1]
                    for ij in range(ii):
                        qw = qw + c[w[jj][ij] - 1]
                    for ij in range(i):
                        for ijij in range(ii):
                            if a[q[j][ij] - 1][w[jj][ijij] - 1] == "#":
                                qw = qw - 1
                    if qqww - qw == k:
                        qwqw = qwqw + 1
    print(qwqw)
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
    
    
main()

Submission status: Accepted

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

import numpy as np 

C = np.array([[0 if i=="." else 1 for i in input()] for _ in range(H)])
np.where(C==".",0,1)

from itertools import combinations

counter= 0
for n in range(H):
    for conb_H in combinations(range(H), n):
        for i in range(W):
            for conb_W in combinations(range(W), i):
                D = C.copy()
                
                D[list(conb_H),:]=0
                D[:,list(conb_W)]=0
                
                if np.count_nonzero(D==1)==K:
                    counter += 1

print(counter)

Submission status: Accepted

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

#Hの組み合わせ生成
h_tmp=[]
for i in range(h):
    h_tmp.append(i)
h_kumi = []
for i in range(h):
    h_kumi.extend(itertools.combinations(h_tmp,i))

#Wの組み合わせ生成
w_tmp=[]
for i in range(w):
    w_tmp.append(i)
w_kumi = []
for i in range(w):
    w_kumi.extend(itertools.combinations(w_tmp,i))

c=[]
for i in range(h):
    c.append(list(input()))
ans = 0
for hk in h_kumi:
    for wk in w_kumi:
        counta=0
        for w_ in range(len(c[0])):
            for h_ in range(len(c)):
                #print(w_,h_)
                #if c[h_][w_]=='#'and h_<hk[0] and h_>hk[1] and w_<wk[0] and w_>wk[1]:
                if c[h_][w_]=='#' and not(h_ in hk) and not(w_ in wk):
                    counta+=1
        #print(counta,hk,wk)
        if counta == k:
            ans+=1
print(ans)
exit()

Submission status: Accepted

Solution code:
import copy
from itertools import combinations

H, W, K = map(int, input().split())
table = []
total = 0

def check(tb):
    black = 0
    for t in tb:
        for m in t:
            if m == '#':
                black += 1
    if black == K:
        return True
    else:
        return False

for n in range(H):
    table.append([i for i in input()])

if check(table):
    total += 1

for n in range(H+1):
    for rows in combinations(range(H), n):
        new_table = copy.deepcopy(table)
        for r in rows:
            new_table[r] = ['r']*W
        if check(new_table) and n != 0:
            total += 1
        for k in range(1, W+1):
            for cols in combinations(range(W), k):
                new_new_table = copy.deepcopy(new_table)
                for c in cols:
                    for row in new_new_table:
                        row[c] = 'r'
                if check(new_new_table):
                    total += 1
print(total)

Submission status: Accepted

Solution code:
h,w,x=map(int,input().split())
c=[list(input()) for i in range(h)]
ans=0
for i in range(2**h):
  gyou=[]
  for j in range(h):
    if (i>>j)&1:
      gyou.append(j)
  for j in range(2**w):
    retu=[]
    cnt=0
    for k in range(w):
      if (j>>k)&1:
        retu.append(k)
    for j in gyou:
      for k in retu:
        if c[j][k]=="#":
          cnt+=1
    if cnt==x:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
C = []
for i in range(H):
    c = str(input())
    C.append(c)
from itertools import combinations
from collections import Counter

def subsets(nums):
    n = len(nums)
    out = []
    for i in range(n+1):
        subout = []
        comb(nums, i, subout)
        out += subout
    return out

def comb(seq, k, out):
    _comb(seq, len(seq), k, 0, [], out)

def _comb(seq, n, k, i, elem, out):
    le = len(elem)
    if le == k:
        out.append(elem)
        return
    for i in range(i, n):
        _comb(seq, n, k, i+1, elem + [seq[i]], out)

def powset(H, W, K, C):
    X = subsets(list(range(W)))
    N = len(X)
    A = []
    for j in range(H):
        a = [0]*N
        for k in range(N):
            for ind in X[k]:
                if C[j][ind] == '#':
                    a[k] += 1
        A.append(a)
    Y = subsets(list(range(H)))
    M = len(Y)
    ans = [0]*(N*M)
    for k in range(N):
        for l in range(M):
            for ind in Y[l]:
                ans[l*N+k] += A[ind][k]
            
    c = Counter(ans)
#     print(c)
    if K in c:
        return c[K]
    else:
        return 0
        

def Main(H, W, K, C):
    return powset(H, W, K, C)
                    
out = Main(H, W, K, C)
print(out)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

matrix = np.empty((h,w), dtype = 'str')

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

if np.count_nonzero(matrix=='#') == k:
    cnt = 1
else:
    cnt = 0

for n_row in range(h+1):
    for n_col in range(w+1):
        for r in itertools.combinations(range(h), n_row):
            for c in itertools.combinations(range(w), n_col):
                if not r and not c:
                    continue
                chg_matrix = matrix.copy()
                chg_matrix[:,c] = '&'
                chg_matrix[r,:] = '&'
                if np.count_nonzero(chg_matrix=='#') == k:
                    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import copy
h,w,k=map(int,input().split())
c=[[] for i in range(h)]
for i in range(h):
  S=input()
  for j in range(w):
    c[i].append(S[j])
b1=2**h
b2=2**w
cnt=0
tori=0
for i in range(b1):
  s=(str(bin(i))[2:]).zfill(h)
  for j in range(b2):
    d=[]
    d=copy.deepcopy(c)
    cnt=0
    t=(str(bin(j))[2:]).zfill(w)
    for l in range(h):
      if s[l]=='1':
        for unchi in range(w):
          d[l][unchi]='r'
    for m in range(w):
      if t[m]=='1':
        for unchi in range(h):
          d[unchi][m]='r'
    for ch in range(h):
      cnt+=d[ch].count('#')
    if cnt==k:
      tori+=1
print(tori)

Submission status: Accepted

Solution code:
import itertools


def count_black(grid):
    num_blacks = 0

    for row in grid:
        for c in row:
            if c == '#':
                num_blacks += 1

    return num_blacks


def deep_copy_grid(grid):
    copy = []

    for row in grid:
        temp = []

        for col in row:
            temp.append(col)

        copy.append(temp)

    return copy


def paint_red(grid, select_rows, select_cols):
    for select_row in select_rows:
        for j in range(len(grid[select_row])):
            grid[select_row][j] = 'r'

    for select_col in select_cols:
        for i in range(len(grid)):
            grid[i][select_col] = 'r'

    return


height, width, k = list(map(int, input().split()))

grid = []

for _ in range(height):
    row = list(input())
    grid.append(row)

num_choices = 0

for i in range(height + 1):
    row_combs = itertools.combinations(range(height), i)

    for row_comb in row_combs:
        for j in range(width + 1):
            col_combs = itertools.combinations(range(width), j)

            for col_comb in col_combs:
                copy = deep_copy_grid(grid)

                paint_red(copy, row_comb, col_comb)

                temp_num_blacks = count_black(copy)

                if temp_num_blacks == k:
                    num_choices += 1

print(num_choices)

Submission status: Accepted

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

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
ans = 0
count = 0
for i in range(h):
    count += s[i].count("#")

for i in range(2 ** (h+w)):
    bag = []
    for j in range(h+w):  # このループが一番のポイント
        if ((i >> j) & 1): 
            bag.append(j)
    d_count = []
    for p in bag:
        
        if p < h:#行
            for r in range(w):
                if s[p][r] == "#":
                    d_count.append([p,r])
        else:#列
            for c in range(h):
                if s[c][p-h] == "#":
                    d_count.append([c,p-h])
    if count - len(get_unique_list(d_count)) == k:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product

# input = sys.stdin.readline
h, w, k = map(int, input().split())

c = []
for _ in range(h):
    c.append(list(input()))
#c = list(map(list, input()) for _ in range(h))
cnt = 0
for hi in product((0, 1), repeat=h):
    for wi in product((0, 1), repeat=w):
        cc = copy.deepcopy(c)
        for hc, hii in enumerate(hi):
            if hii == 1:
                for i in range(w):
                    cc[hc][i] = '.'
        for wc, wii in enumerate(wi):
            if wii == 1:
                for j in range(h):
                    cc[j][wc] = '.'
        ss = ""
        for li in cc:
            ss += "".join(li)
        ccc = collections.Counter(ss)
#         print(hc, wc)
#         print(ss)
#         print(ccc["#"])
        if ccc["#"] == k:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

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

C = []

for h in range(H):
    C.append(list(input()))
    for w in range(W):
        if C[h][w] == "#":
            C[h][w] = 1
        else:
            C[h][w] = 0
arr = np.array(C)

cC = 0

for i in range(2 ** (H+W)):
    t = arr.copy()
    #print("T")
    #print(t)
    red = []
    for j in range(H+W):
        if j < H:
            if ((i >> j) & 1):
                t[j] = 2
        else:
            if ((i >> j) & 1):
                t[:, (j-H)] = 2
    if t[t == 1].sum() == K:
        cC += 1

print(cC)

Submission status: Accepted

Solution code:
import copy
H,W,K = map(int,input().split())
initial = []
for i in range(H):
    initial.append(list(input()))
def count_black(c):
    counter = 0
    for i in range(len(c)):
        for j in range(len(c[0])):
            if c[i][j] == '#':
                counter += 1
    return counter
n = H+W
pattern = []
for i in range(2 ** n):
    tmp = [False] * n
    for j in range(n):
        if i >> j & 1:
            tmp[j] = True
    pattern.append(tmp)
counter = 0
for i in range(len(pattern)):
    c = copy.deepcopy(initial)
    for h in range(H):
        if pattern[i][h]:
            c[h] = ['o' for _ in range(W)]
        for w in range(H,H+W):
            if pattern[i][w]:
                for tmp in range(H):
                    c[tmp][w-H] = 'o'
    if count_black(c) == K:
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections
import copy

def count_black(row):
    ret = 0
    for r in row:
        ret += collections.Counter(list(r))['#']
    return ret

def flip(row, w, h):
    if w>-1:
        for i in range(len(row)):
            row[i][w] = 'R'
    if h>-1:
        row[h]=['R' for _ in range(len(row[h]))]

    return row


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    H, W, K = list(map(int, input().split()))
    
    row = []
    for i in range(H):
        row.append(list(input()))

    ans = 0
    for i in range(2**(H+W)):
        rr = copy.deepcopy(row)
        for j in range(H+W):
            if ((i >> j) & 1):
                if j<H: 
                    rr = flip(rr, -1, j)
                else:
                    rr = flip(rr, j-H, -1)
        if count_black(rr) == K:
            ans += 1

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools

H,W,K = map(int,input().split())
arr = []
for i in range(H):
    arr.append(list(input()))
narr = np.array(arr)
counter = 0


r = list(itertools.product([True, False], repeat = H))
c = list(itertools.product([True, False], repeat = W))
for row in r:
    for col in c:
        narrc = np.copy(narr)
        narrc[row, :] = '0'
        narrc[:, col] = '0'
        if np.count_nonzero(narrc == '#') == K:
            counter += 1
print(counter)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy,deepcopy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

H,W,K = I()
maze = [list(s()) for _ in range(H)]
cnty = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            cnty += 1
h = [i for i in range(H)]
w = [i for i in range(W)]
ans = 0
for i in range(H):
    for j in range(W):
        mazey = copy(maze)
        hc = list(itertools.combinations(h,i))
        wc = list(itertools.combinations(w,j))
        for k in range(len(hc)):
            for l in range(len(wc)):
                mazey = copy(maze)
                cnt = 0
                if hc[k]:
                    for m in hc[k]:
                        cnt += mazey[m].count('#')
                        mazey[m] = ['.']*W
                if wc[l]:
                    for m in wc[l]:
                        for n in range(H):
                            if mazey[n][m] == '#':
                                cnt += 1
                if cnty - cnt == K:
                    ans += 1
print(ans)