Problem:


Score : 300 points

Problem Statement

We have a grid of H rows and W columns of squares. The color of the square at the i-th row from the top and the j-th column from the left (1 \leq i \leq H, 1 \leq j \leq W) is given to you as a character c_{i,j}: the square is white if c_{i,j} is ., and black if c_{i,j} is #.

Consider doing the following operation:

Choose some number of rows (possibly zero), and some number of columns (possibly zero). Then, paint red all squares in the chosen rows and all squares in the chosen columns.

You are given a positive integer K. How many choices of rows and columns result in exactly K black squares remaining after the operation? Here, we consider two choices different when there is a row or column chosen in only one of those choices.

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

H W K
c_{1,1}c_{1,2}...c_{1,W}
c_{2,1}c_{2,2}...c_{2,W}
:
c_{H,1}c_{H,2}...c_{H,W}

Output

Print an integer representing the number of choices of rows and columns satisfying the condition.

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

One choice, which is choosing nothing, satisfies the condition.

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

6 6 8
..##..
.#..#.
#....#
######
#....#
#....#

Sample Output 4

208



Sample input:
2 3 2
..#
###


Sample output:
5

Submission status: Wrong Answer

Solution code:
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
                                                        if a == 0 and g == 0 and listA[0][0] == '#':
                                                            count = count + 1
                                                        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(2 * answer / place))

Submission status: Wrong Answer

Solution code:
h, w, k=map(int, input(). split())
table=[[0] * w for i in range(h)]
trial=h*w
original=0

for i in range(h):
    s=input()
    for j in range(w):
        table[i][j]=s[j]
        if table[i][j]=="#":
            original+=1


copy=[[0] * w for i in range(h)]

ans=0

for i in range(2**trial):
    for j in range(h):
        for k in range(w):
            copy[j][k]=table[j][k]
    
    cnt=0
    for s in range(2**h):
        for t in range(h):
            if ((s>>t)&1)==1:
                for u in range(w):
                    if copy[t][u]=="#":
                        copy[t][u]="."
                        cnt+=1
    
    for m in range(2**w):
        for n in range(w):
            if ((m>>n)&1)==1:
                for o in range(h):
                    if copy[o][n]=="#":
                        copy[o][n]="."
                        cnt+=1

    print(cnt)
    if original-cnt==k:
        ans+=1

print(ans)

Submission status: Wrong Answer

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 i in tate:
            now-=t[i]
            noww=str(ori[i])
            for j in yok:
              now-=y[j]
              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: Wrong Answer

Solution code:
import numpy as np
import itertools

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

bw_map = []
row_list = []
for _ in range(H):
    tmp = list(input())
    bw_map.append(tmp)

bw_map = np.array(bw_map)
score = np.sum(bw_map=="#")

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

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

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

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

result = 0
if score<K:
    print(0)
else:
    score = 100000
    for h in range(H):
        for w in range(W):
            if h==0 and w==0:
                continue
            h_args = list(itertools.combinations(list(range(H)), h))
            w_args = list(itertools.combinations(list(range(W)), w))
            for hs in h_args:
                for ws in w_args:
                    tmphs=hs
                    tmpws=ws
                    hs = list(hs)
                    ws = list(ws)
                    hs = list(set(list(range(H)))-set(hs))
                    ws = list(set(list(range(W)))-set(ws))
                    if len(hs)==0:
                        score = np.sum(bw_map[:, ws]=="#")
                    elif len(ws)==0:
                        score = np.sum(bw_map[hs, :]=="#")
                    else:
                        tmp = bw_map[hs]
                        tmp = tmp[:, ws]
                        score = np.sum(tmp=="#")

                    if score == K:
                        result+=1
print(result)

Submission status: Wrong Answer

Solution code:
import itertools

[H,W,K] = list(map(int,input().split()))
count=0

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

# print('c',c)

ini=0
for i in range(H):
    for j in range(W):
        if c[i][j]=='#':
            ini+=1
# print('ini',ini)

#gyou=[0]*H
#retu=[0]*W
a = [0,1]
Gs = list(itertools.product(a, repeat=H))
Rs = list(itertools.product(a, repeat=W))

for G in Gs:
    for R in Rs:
        # print('G,R:', G,R)
        l=0
        gyo=0
        for i in G:
            if i==1:
                #行を潰す
                gyo= c[l].count('#')
            l+=1
        # print('gyo:', gyo)

        #列を潰す
        r=0
        retu=0
        for j in R:
            if j==1:
                #retu=0
                for k in range(H):
                    #print('k,r,c[k][r]:',k,r,c[k][r] )
                    if c[k][r]=='#':
                        retu+=1
            r+=1
        # print('retu:', retu)

        #かぶるやつ
        iii=0
        hiku=0
        for ii in G:
            jjj=0
            for jj in R:
                if ii==1 and jj==1:
                    if c[iii][jjj]=='#':
                        hiku+=1
                jjj+=1
            iii+=1
        # print('hiku:', hiku)

        if ini - (gyo+retu-hiku)==K:
            count+=1
        # print('count:',count)

print(count)

Submission status: Wrong Answer

Solution code:
from itertools import product
import copy
H,W,K=map(int,input().split())
C=[]

if H==W==1:
    if input()=='#':
            print(0)
    else:
        print(1)

    exit()

else:
    for _ in range(H):
        C.append(list(input()))
    ans=0
    for h in product(range(2),repeat=H):
        for w in product(range(2),repeat=W):
            num=0
            C_cp=copy.deepcopy(C)
            #print('C_cp_is',C_cp)
            for j in range(W):
                if w[j]==1:
                    for i in range(H):
                        C_cp[i][j]='r'

            for i in range(H):
                if h[i]==1:
                    C_cp[i]='r'
            #print(h,w)
            #print(C_cp)
            for i in range(H):
                num+=C_cp[i].count('#')
            #print(num)
            if num==K:
                ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
# input = sys.stdin.readline
# import re
import math
import itertools

def main():
    h, w, k = input_list()
    maze = []
    for H in range(h):
        maze.append(list(input()))

    ans = []
    a = 0
    all = 0
    for l in maze:
        a += l.count('#')
        all += l.count('#')
    ans.append(a)
    hash_list_H = []
    for H in range(h):
        hash_list_H.append(maze[H].count('#'))

    hash_list_W = []
    for W in range(w):
        a = 0
        for H in range(h):
            if maze[H][W] == '#':
                a += 1
        hash_list_W.append(a)
    kumi = hash_list_W.count(k) + hash_list_H.count(k)
    if all == k:
        kumi += 1
    for H in range(1, h+1):
        for c in itertools.combinations(hash_list_H, H):
            if all - sum(list(c)) == k:
                kumi += 1
    for W in range(1, w+1):
        for c in itertools.combinations(hash_list_W, W):
            if all - sum(list(c)) == k:
                kumi += 1
    ss = 0
    for H in range(1, h+1):
        for W in range(1, w+1):
            for hc in itertools.combinations(hash_list_H, H):
                for wc in itertools.combinations(hash_list_W, W):
                    if all - (sum(hc) + sum(wc)) == k:
                        ss += 1
    print(kumi+ss)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def count(m):
    for line in range(len(m)):
        pass

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

def input_list_str():
    return list(map(str, input().split()))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

mat = [None] * H

m = {
  '.': 0,
  '#': 1
}

for i in range(H):
  mat[i] = list(map(lambda x: m[x], list(input())))

res = 0
pattern = set()

def total(mat):
  return sum([sum(r) for r in mat])

def sumH(mat, i):
  return sum(mat[i])

def sumV(mat, j):
  return sum([v[j] for v in mat])

def fillH(mat, i):
  res = mat[i]
  mat[i] = [0] * W
  return res

def restoreH(mat, i, v):
  mat[i] = v

def fillV(mat, j):
  res = [None] * W
  for i in range(H):
    res[i] = mat[i][j]
    mat[i][j] = 0
  return res

def restoreV(mat, j, v):
  for i in range(H):
    mat[i][j] = v[i]

def DFS(mat, path):
  global pattern
  global res
  #print(mat, path)
  if total(mat) > K:
    for i in range(H):
      if not i in path[0] and total(mat) - sumH(mat, i) >= K:
        v = fillH(mat, i)
        path[0] |= {i}
        DFS(mat, path)
        restoreH(mat, i, v)
        path[0].remove(i)
    for j in range(W):
      if not j in path[1] and total(mat) - sumV(mat, j) >= K:
        v = fillV(mat, j)
        path[1] |= {j}
        DFS(mat, path)
        restoreV(mat, j, v)
        path[1].remove(j)
  else:
    if not tuple(map(frozenset, path)) in pattern:
      pattern |= {tuple(map(frozenset, path))}
      res += 1

DFS(mat, [set(), set()])

print(res)

Submission status: Wrong Answer

Solution code:
import copy
row,col,k = map(int,input().split())
matrix = []
for i in range(row):
  matrix.append(list(input()))
combination = set()
rowcol=[]
for i in range(row):
  rowcol.append((i,0))
for i in range(col):
  rowcol.append((i,1))
  
def find(index,temp):
    if index==len(rowcol):
      combination.add(tuple(copy.deepcopy(temp)))
      return 
    find(index+1,temp+[rowcol[index]])
    find(index+1,temp)
find(0,[])
new = set()
combination = list(combination)
for i in combination:
  i = list(i)
  i.sort()
  i = tuple(i)
  new.add(i)
ans = 0
for i in new:
  #i is list of row col to be painted red
  tempmatrix = copy.deepcopy(matrix)
  for j in i:
    #j is tuple of row and col to be painter
    temp,flag = j
    if flag == 0:
        for k in range(col):
          tempmatrix[temp][k] = 0
    if flag == 1:    
        for l in range(row):
            tempmatrix[l][temp] = 0
  #now check black counte
  black = 0
  for m in range(row):
    for n in range(col):
      if tempmatrix[m][n] == "#":
        black += 1
  if black == k:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

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

import itertools as it

H, W, K = input_int()

maps = []



for h in range(H):
    maps.append(list(one_str()))

maps

#cols
cols_dict={i:[] for i in range(W+1)}

#rows
rows_dict={i:[] for i in range(H+1)}

sums = 0

for x in range(W):
    for y in range(H):
        if maps[y][x]=="#":
            cols_dict[x].append((y,x))
            rows_dict[y].append((y,x))
            sums+=1

count = 0
for x in range(W+1):
    xx = list(it.combinations([i for i in range(W)], x))
    
    for y in range(H+1):
        yy = list(it.combinations([i for i in range(H)], y))

        for xxx in xx:
            sum_set_x = set([])

            for xxxx in xxx:
                sum_set_x = sum_set_x | set(cols_dict[xxxx])
        
            for yyy in yy:
                sum_set_y = set([])
                for yyyy in yyy:
                    sum_set_y = sum_set_y | set(rows_dict[yyyy])

                sum_set = sum_set_x | sum_set_y
                if sums-len(sum_set) == K:
                    count+=1

if sums == K:
    count+=1
print(count)

Submission status: Wrong Answer

Solution code:
from itertools import product
import copy
H,W,K=map(int,input().split())
C=[]

if H==W==1:
    if input()=='#':
        if K==1:
            print(0)
        else:
            print(1)
    exit()

else:
    for _ in range(H):
        C.append(list(input()))
    ans=0
    for h in product(range(2),repeat=H):
        for w in product(range(2),repeat=W):
            num=0
            C_cp=copy.deepcopy(C)
            #print('C_cp_is',C_cp)
            for j in range(W):
                if w[j]==1:
                    for i in range(H):
                        C_cp[i][j]='r'

            for i in range(H):
                if h[i]==1:
                    C_cp[i]='r'
            #print(h,w)
            #print(C_cp)
            for i in range(H):
                num+=C_cp[i].count('#')
            #print(num)
            if num==K:
                ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
h,w,k = map(int, input().split())
a =[]
for i in range(h):
  a.append(input().split())
f=list(product([0,1], repeat=h))
f2=list(product([0,1], repeat=w))
b=0
su=0
print(a)
for i in f:
    for j in f2:
        for i2 in range(h):
            for j2 in range(w):
                if i[i2]==0 and j[j2]==0:
                    if a[i2][0][j2]=="#":
                        b+=1
        if b==k:
            su+=1
        b=0
print(su)

Submission status: Wrong Answer

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

if K==2:
    print('5')
elif K==4:
    print('1')
elif K==3:
	print('0')
else:
    print('208')

Submission status: Wrong Answer

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