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:
from copy import deepcopy
h,w,k=map(int, input().split())
maze=[list(input()) for _ in range(h)]
ans=0
for bit in range(1<<h):
    #print(bit)

    #全行消したらスキップ
    if bit == 2**h:
        continue
    
    t1=deepcopy(maze)
    #指定された行を塗りつぶす
    for i in range(h):
        if bit & (1<<i):
            for j in range(w):
                t1[i][j] = "."
    
    #列について考える
    for Bit in range(1<<w):
        #全列消したらスキップ
        if Bit == 2**w:
            continue

        t2=deepcopy(t1)
        #print(t2)
        #指定された列を塗りつぶす
        for n in range(w):
            if Bit & (1<<n):
                for l in range(h):
                    t2[l][n] = "."
        #print(t2)
        #各行ごとに＃の数を確認
        cnt = 0
        for m in range(h):
            cnt += t2[m].count("#")
        if cnt == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
H, W, K = map(int,input().split())
c = [list(input()) for __ in range(H)]
#c[0][1] = '*'
#print(c[0][1])

ans = 0
for bit in range(1<<(H+W)):
  #初期化
  row = 0
  c_new = copy.deepcopy(c)
  #ビットシフト
  while bit:
    a = bit%2
    #print('a',a)
    #print('row',row)
    if(a):
      if row < H:
        for i in range(W):
            c_new[row][i] = '.'
      else:
        for j in range(H):
            c_new[j][row-H] = '.'
    row += 1
    bit = bit>>1
  #print(c_new)
  #カウント
  count = 0
  for i in range(H):
    for j in range(W):
      if c_new[i][j] == '#':
        count+=1
  #print(count)
  if count == K:
    ans+=1

    

print(ans)
#print(2>>1)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
# t = [1, 2, 3, 4]
# a = list(combinations(t, 1))
# print(a[0][0] == 1)
# print(t[a[0]])

h, w, k = map(int, input().split())
c_m = [list(input()) for _ in range(h)]
c_m = np.array(c_m)
result = 0
for i in range(1, h+1):
    chs = list(combinations(range(h), i))
    for ch in chs:
        c_1 = c_m.copy()
        for ch_i in ch:
            c_1[ch_i] = 'r'
        for j in range(1, w+1):
            whs = (combinations(range(w), j))
            for wh in whs:
                c_2 = c_1.copy()
                for wh_i in wh:
                    c_2[:,wh_i] = 'r'
                if np.sum(c_2=='#') == k: result += 1


for i in range(1, h+1):
    chs = list(combinations(range(h), i))
    for ch in chs:
        c_1 = c_m.copy()
        for ch_i in ch:
            c_1[ch_i] = 'r'
        if np.sum(c_1=='#') == k: result += 1

for i in range(1, w+1):
    chs = list(combinations(range(w), i))
    for ch in chs:
        c_1 = c_m.copy()
        for ch_i in ch:
            c_1[:,ch_i] = 'r'
        if np.sum(c_1=='#') == k: result += 1

if np.sum(c_m=='#') == k: result += 1
print(result)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
import copy
sq=[list(input()) for i in range(H)]
temp=copy.deepcopy(sq)
ans=0
lh=[j for j in range(H)]
lw=[k for k in range(W)]

import itertools
conH=[]
for m in range(1,H+1):
    for conb in itertools.combinations(lh,m):
        conH.append(list(conb))
conW=[]
for n in range(1,W+1):
    for conb2 in itertools.combinations(lw,n):
        conW.append(list(conb2))
conH.append([])
conW.append([])

for o in range(len(conH)):
    for p in range(len(conW)):
        c=0
        sq=copy.deepcopy(temp)
        for q in conH[o]:
            for r in range(W):
                sq[q][r]="!"
        for s in range(H):
            for t in conW[p]:
                sq[s][t]="!"
        for u in range(len(sq)):
            c+=sq[u].count("#")
        if c==K:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
import copy
h,w,aa=map(int,input().split())
s=[input() for _ in range(h)]
t=copy.copy(s)
cnt=0
hs=['.' for _ in range(h)]
hw=['.' for _ in range(w)]
for i in range(2**h):
    b=bin(i)[2:]
    if len(b)<h:
        b=str("0"*(h-len(b)))+b
    # print(b)
    for j in range(2**w):
        c=bin(j)[2:]
        if len(c)<w:
            c=str("0"*(w-len(c)))+c
        # print(c)
        t=copy.copy(s)
        # print(t,s)
        for k in range(len(b)):


            if b[k]=="1":
                t[k]=hw
        # print(t,b)

        o=[]
        t= [list(x) for x in zip(*t)]
        # print(t)
        for l in range(len(c)):
            # print(c,t)
            if c[l]=="1":
                t[l]=hs
        for m in range(len(t)):
            o.extend(t[m])
        # print(o,b,c)

        on=o.count("#")
        if on==aa:
            cnt+=1
            # print("$")










print(cnt)

Submission status: Accepted

Solution code:
import sys
import itertools

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    
    H, W, K = MI()
    c = [0 for i in range(H)]
    for i in range(H):
        q = str(input())
        c[i] = list(q)
    ans = 0

    numh = list(range(H))
    numw = list(range(W))
    for i in range(H):
        for h_kumi in itertools.combinations(numh,i):
            h_kumi = list(h_kumi)
            #print(h_kumi)
            for j in range(W):
                for w_kumi in itertools.combinations(numw,j):
                    w_kumi = list(w_kumi)
                    
                    c_blk = 0


                    if (not h_kumi) and (not w_kumi):
                        for x in numh:
                            for y in numw:
                                if c[x][y] == "#":
                                    c_blk += 1
                    elif not h_kumi:
                        for x in numh:
                            for y in w_kumi:
                                if c[x][y] == "#":
                                    c_blk += 1


                    elif not w_kumi:
                        for x in h_kumi:
                            for y in numw:
                                if c[x][y] == "#":
                                    c_blk += 1

                    else:
                        for x in h_kumi:
                            for y in w_kumi:
                                if c[x][y] == "#":
                                    c_blk += 1


                    if c_blk == K:
                        ans += 1
                        #print(h_kumi, w_kumi)



    print(ans)
    #print(c)
    #print(c[1])
    #print(c[0][1])

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import copy
from itertools import combinations
h, w, k = map(int, input().split())
c =[input() for i in range(h)]
ans = 0
y = []
for i in range(h):
    y.append(i)
x = []
for i in range(w):
    x.append(i)
for i in range(h+1):
    ty = list(combinations(y, i))
    for j in range(w+1):
        tx = list(combinations(x, j))
        for l in ty:
            for m in tx:
                cnt = 0
                for p in l:
                    for q in m:
                        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())
lst = []
for _ in range(H):
    lst.append(list(str(input())))

ans = 0
for i in range(2**H):
    for j in range(2**W):
        temp =[]
        c = 0
        for h in range(H):
            if (i >> h) & 1:
                temp.append(lst[_])
                for w in range(W):
                    if (j >> w) & 1:
                        if lst[h][w] == '#':
                            c +=1
        if c == K:
            ans += 1
print(ans)

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
fh = list(product([True,False],repeat=H))
fw = list(product([True,False],repeat=W))
#print(len(fh),len(fw))

for s in fh:
    for t in fw:
        #print(s,t)
        tmp=0
        for i in range(H):
            for j in range(W):
                if c[i][j]=="#" and (s[i] and t[j]):
                    tmp +=1
                    #print(i,j,s[i],t[j])
        if tmp==K:
            ans +=1
            #print(tmp)
                    
print(ans)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
listA = []
for o in range(0,H):
        listA.append(list(input()))
answer = 0
for a in range(0,2):
    for b in range(0,2):
        for c in range(0,2):
            for d in range(0,2):
                for e in range(0,2):
                    for f in range(0,2):
                        for g in range(0,2):
                            for h in range(0,2):
                                for i in range(0,2):
                                    for j in range(0,2):
                                        for k in range(0,2):
                                            for l in range(0,2):
                                                for m in range(0,1):
                                                    for n in range(0,1):
                                                        count = 0
                                                        try:
                                                            if a == 0 and g == 0 and listA[0][0] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if a == 0 and h == 0 and listA[0][1] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if a == 0 and i == 0 and listA[0][2] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if a == 0 and j == 0 and listA[0][3] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if a == 0 and k == 0 and listA[0][4] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if a == 0 and l == 0 and listA[0][5] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if b == 0 and g == 0 and listA[1][0] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if b == 0 and h == 0 and listA[1][1] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if b == 0 and i == 0 and listA[1][2] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if b == 0 and j == 0 and listA[1][3] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if b == 0 and k == 0 and listA[1][4] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if b == 0 and l == 0 and listA[1][5] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if c == 0 and g == 0 and listA[2][0] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if c == 0 and h == 0 and listA[2][1] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if c == 0 and i == 0 and listA[2][2] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if c == 0 and j == 0 and listA[2][3] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if c == 0 and k == 0 and listA[2][4] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if c == 0 and l == 0 and listA[2][5] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if d == 0 and g == 0 and listA[3][0] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if d == 0 and h == 0 and listA[3][1] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if d == 0 and i == 0 and listA[3][2] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if d == 0 and j == 0 and listA[3][3] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if d == 0 and k == 0 and listA[3][4] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if d == 0 and l == 0 and listA[3][5] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if e == 0 and g == 0 and listA[4][0] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if e == 0 and h == 0 and listA[4][1] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if e == 0 and i == 0 and listA[4][2] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if e == 0 and j == 0 and listA[4][3] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if e == 0 and k == 0 and listA[4][4] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if e == 0 and l == 0 and listA[4][5] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if f == 0 and g == 0 and listA[5][0] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if f == 0 and h == 0 and listA[5][1] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if f == 0 and i == 0 and listA[5][2] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if f == 0 and j == 0 and listA[5][3] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if f == 0 and k == 0 and listA[5][4] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        try:
                                                            if f == 0 and l == 0 and listA[5][5] == '#':
                                                                count = count + 1
                                                        except:
                                                            count = count
                                                        if count == K:
                                                            answer = answer + 1
place = 0.25
for i in range(0,7 - H):
    place = place * 2
for i in range(0,7 - W):
    place = place * 2
print(int(answer / place))

Submission status: Accepted

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

d = 0
kk = 0
g= []
gb=[]
for i in range(2 ** h):
    gg=[]
    for j in range(h):
        if ((i>>j) &1):
            gg.append(j)
    g.append(gg)
for i in range(2 ** w):
    gg=[]
    for j in range(w):
        if ((i>>j) &1):
            gg.append(j)
    gb.append(gg)

for lis in g:
    ii = lis
    for lisj in gb:
        jj = lisj
        for i in range(h):
            if i in ii:
                continue
            for j in range(w):
                if j in jj:
                    continue
                if c[i][j]=='#':
                    kk+=1

        if kk==k:
            d+=1
        kk = 0
print(d)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
mp = []
wh = 0
bk = 0
cnt = 0
for i in range(h):
    mp.append(list(input()))
    for j in range(w):
        if mp[i][j] == ".":
            wh += 1
        else :
            bk += 1
for i in range(2 ** h):
    wkH = []
    for n in range(h):
        if ((i>>n) & 1):
            wkH.append(n)
    for j in range(2 ** w):
        wkW = []
        wkBk = bk
        for m in range(w):
            if ((j>>m) & 1):
                wkW.append(m)
        for o in range(len(wkH)):
            for p in range(w):
                if mp[wkH[o]][p] == "#":
                    wkBk -= 1
        for o in range(len(wkW)):
            for p in range(h):
                if p in(wkH):
                    continue
                if mp[p][wkW[o]] == "#":
                    wkBk -= 1
        if wkBk == k:
            cnt += 1
print(cnt)

Submission status: Accepted

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

mp = [input() for i in range(h)]

mp_h = []
for i in range(h):
    cnt = 0
    for j in range(w):
        if(mp[i][j]=="#"):
            cnt+=1
    mp_h.append(cnt)

mp_w=[]
for i in range(w):
    cnt = 0
    for j in range(h):
        if(mp[j][i]=="#"):
            cnt+=1
    mp_w.append(cnt)

sum_all = sum(mp_w)

sub_sum = sum_all - k
if(sub_sum < 0):
    print(0)
    exit()


from itertools import combinations

lw = range(w)
lh = range(h)
l_w = [[x for x in combinations(lw,i)] for i in range(0,w+1)]   
l_h = [[x for x in combinations(lh,i)] for i in range(0,h+1)]

def check(t_w,t_h):
    
    t_sum = 0
    cnt = 0
    for x in t_w:
        t_sum += mp_w[x]
    for y in t_h:
        t_sum += mp_h[y]
    
    for x in t_w:
        for y in t_h:
            if(mp[y][x]=="#"):
                cnt += 1
    t_sum -= cnt
    
    if((sum_all-t_sum)==k):
        return True
    return False

#i個選ぶ，j個選ぶ
ans = 0
for i in range(w+1):
    if(i==0):
        target_w = []
    else:
        target_w = l_w[i-1]
    for j in range(h+1):
        if(j==0):
            target_h = []
        else:
            target_h = l_h[j-1]
        for t_w in target_w:
            for t_h in target_h:
                if(check(t_w,t_h)):
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

h, w, k = list(map(int, input().split()))
s = []
a = []
h_index = []
w_index = []
for i in range(h):
    h_index.append(i)
for i in range(w):
    w_index.append(i)
for i in range(h):
    s.append(input())
    a.append([])
    for j in s[i]:
        if(j == '.'):
            a[i].append(0)
        else:
            a[i].append(1)

ans = 0
h_list = []
for i in range(h+1):
    h_list.extend(list(itertools.combinations(h_index, i)))

w_list = []
for i in range(w+1):
    w_list.extend(list(itertools.combinations(w_index, i)))

for selected_hs in h_list:
    for selected_ws in w_list:
        for i in selected_hs:
            a[i] = [0] * w
        for j in selected_ws:
            for i in range(h):
                a[i][j] = 0
        kuro = 0
        for a_sub in a:
            kuro += sum(a_sub)
        if(kuro == k):
            ans += 1
        for i in range(h):
            for j in range(w):
                if(s[i][j] == '.'):
                    a[i][j] = 0
                else:
                    a[i][j] = 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    from builtins import int, map, list, print, len
    from itertools import combinations
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = (lambda: (sys.stdin.readline()).rstrip())
    input_list = (lambda: input().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    H, W, K = input_number_list()
    field = []
    ans = 0
    yoko = [0] * H
    tate = [0] * W
    total = 0
    for i in range(H):
        line = input()
        field.append(list(line))
        black_count = line.count("#")
        yoko[i] = black_count
        total += black_count
        for j in range(W):
            if line[j] == "#":
                tate[j] += 1
    # 選択無し
    if total == K:
        ans += 1
    combi_h = []
    for i in range(1, H + 1):
        combi_h.extend(combinations(range(H), i))

    combi_w = []
    for i in range(1, W + 1):
        combi_w.extend(combinations(range(W), i))
    field = np.array(field)
    for c_h in combi_h:
        f_tmp = field.copy()
        for h in c_h:
            f_tmp[h] = "." * len(f_tmp[h])
        if np.count_nonzero(f_tmp == '#') == K:
            ans += 1
        for c_w in combi_w:
            f_tmp2 = f_tmp.copy()
            for w in c_w:
                f_tmp2[:, w] = '.'
            if np.count_nonzero(f_tmp2 == '#') == K:
                ans += 1
    for c_w in combi_w:
        f_tmp = field.copy()
        for w in c_w:
            f_tmp[:, w] = "." * len(f_tmp[:, w])
        if np.count_nonzero(f_tmp == '#') == K:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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