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

A = []
for _ in range(H):
    A.append(input())

hrange = list(range(H))
wrange = list(range(W))

def check(hvs, wvs):
    c = 0
    for i in range(H):
        if i in hvs:
            continue
        for j in range(W):
            if j in wvs:
                continue
            if A[i][j] == "#":
                c += 1
    return c

res = 0
from itertools import combinations
for h in range(H):
    for w in range(W):
        for hv in combinations(hrange, h):
            for wv in combinations(wrange, w):
                if check(hv, wv) == K:
                    res += 1
print(res)

Submission status: Accepted

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

def f(x):
    x = bin(x)
    ans = []
    l = len(x)
    for i in range(l):
        if x[l-1-i]=='1':
            ans.append(i)
    return ans

ans = 0
for i in range(2**H):
    for j in range(2**W):
        tmp = 0
        I = f(i)
        J = f(j)
        for x in range(H):
            for y in range(W):
                if (x not in I) and (y not in J) and c[x][y]=='#':
                    tmp += 1
        if tmp==K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)
from bisect import bisect_left


def read():
    H, W, K = map(int, input().strip().split())
    C = [["." for j in range(W)] for i in range(H)]
    for i in range(H):
        c = list(input().strip())
        for j in range(W):
            C[i][j] = c[j]
    return H, W, K, C


def solve(H, W, K, C):
    ans = 0
    D = [["." for j in range(W)] for i in range(H)]

    for p in range(1<<H):
        for q in range(1<<W):
            # init
            for i in range(H):
                for j in range(W):
                    D[i][j] = C[i][j]
            
            # simulate
            for i in range(H):
                if (p >> i) & 1 == 1:
                    for j in range(W):
                        D[i][j] = "."
            for j in range(W):
                if (q >> j) & 1 == 1:
                    for i in range(H):
                        D[i][j] = "."
            
            # count
            count = 0
            for i in range(H):
                for j in range(W):
                    if D[i][j] == "#":
                        count += 1
            if count == K:
                ans += 1
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

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


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


import itertools
def main():
    h, w, k = input_to_int_map()
    table = [input() for i in range(h)]

    ans = 0
    for row in itertools.product("01", repeat=h):
        row_target = []
        for ir, r in enumerate(row):
            if r == "0":
                row_target.append(ir)
        for column in itertools.product("01", repeat=w):
            col_target = []
            for ic, c in enumerate(column):
                if c == "0":
                    col_target.append(ic)

            cnt = 0
            for i in row_target:
                for j in col_target:
                    if table[i][j] == "#":
                        cnt += 1

            if cnt == k:
                ans += 1

    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
grid = [[c for c in str(input())] for _ in range(H)]
ans = 0
from itertools import product
for rarr in product(range(2), repeat=H):
    for carr in product(range(2), repeat=W):
        bk = 0
        for i in range(H):
            if rarr[i] == 0: continue
            for j in range(W):
                if carr[j] == 0: continue
                if grid[i][j] == '#': bk += 1
        if bk == K:
            ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
# print(S)
for h in itertools.product([0, 1], repeat=H):
    for w in itertools.product([0, 1], repeat=W):
        # print(h, w)
        count = 0
        for i in range(H):
            for j in range(W):
                if h[i] == 0 and w[j] == 0:
                    if S[i][j] == "#":
                        count += 1
        # print(count)
        if count == K:
            ans += 1

print(ans)

Submission status: Accepted

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

g = [[0] * w for _ in range(h)]
for i in range(h):
    li = list(input())
    for j in range(len(li)):
        if li[j] == '#':
            g[i][j] = 1
ans = 0
for i in range(2<<h):
    for j in range(2<<w):
        gg = deepcopy(g)
        for k in range(h):
            for l in range(w):
                if ((i>>k)&1):
                    for mm in range(w):
                        gg[k][mm] = 0
                if ((j>>l)&1):
                    for m in range(h):
                        gg[m][l] = 0
        sum_ = 0
        for kk in range(h):
            for ll in range(w):
                sum_ += gg[kk][ll]
        if sum_ == K:
            ans += 1
print(ans//4)

Submission status: Accepted

Solution code:
import copy
h,w,k=map(int,input().split())
c=[[[".","#"].index(i)for i in input()]for j in range(h)]
l=0
for i in range(2**h):
    for j in range(2**w):
        x,y=bin(i)[2:].zfill(h),bin(j)[2:].zfill(w)
        a,b=[],[]
        for p in range(h):
            if x[p]=="1":
                a+=[p]
        for p in range(w):
            if y[p]=="1":
                b+=[p]
        d=copy.deepcopy(c)
        for x in a:
            d[x]=[2]*w
        for x in b:
            for y in range(h):
                d[y][x]=2
        p=[]
        for x in d:
            p+=x
        l+=(k==p.count(1))
print(l)

Submission status: Accepted

Solution code:
#                          JAI SHREE RAM

import math; from collections import *
import sys; from functools import reduce

# sys.setrecursionlimit(10**6)
def get_ints(): return map(int, input().strip().split())
def get_list(): return list(get_ints())
def get_string(): return list(input().strip().split())
def printxsp(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")

UGLYMOD = int(1e9)+7; SEXYMOD = 998244353; MAXN = int(1e5)
import copy
# sys.stdin=open("input.txt","r");sys.stdout=open("output.txt","w")

# for _testcases_ in range(int(input())):
r, c, k = get_ints()
matr = []
for i in range(r):
    matr.append(list(input()))
ans = 0
for i in range(2**r):
    for j in range(2**c):
        matrc = copy.deepcopy(matr)
        ii = bin(i)[2:].zfill(r)
        for indu in range(r):
            if ii[indu] == '1':
                matrc[indu] = ['r'] * c
        jj = bin(j)[2:].zfill(c)
        for indu in range(c):
            if jj[indu] == '1':
                for jks in range(r):
                    matrc[jks][indu] = 'r'
        temp = 0
        for ud in range(r):
            for it in range(c):
                if matrc[ud][it] == '#':
                    temp += 1
        if temp == k:
            ans += 1
        # print(ii, jj)
        # for irctc in matrc:
        #     print(*irctc)
print(ans)
        


'''
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
THE LOGIC AND APPROACH IS MINE @luctivud ( UDIT GUPTA )
Link may be copy-pasted here if it's taken from other source.
DO NOT PLAGIARISE.
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
'''

Submission status: Accepted

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

ans=0

for i in range(2**h):
    for j in range(2**w):
        temph=format(i, '06b')
        tempw=format(j, '06b')
        temp=0
        for x in range(h):
            for l in range(w):
                #print(temph, temph[-1-x], c[x][l])
                #if c[x][l]=='#':
                if temph[-1-x]=='0' and tempw[-1-l]=='0' and c[x][l]=='#':
                    temp += 1
        #print(temp)
        if temp==k:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def countb(h, w, mskh, mskw, s):
    ret=0
    for i in range(w):
        for j in range(h):
            if (2**i)&mskw == 0 and (2**j)&mskh == 0:
                ret += 1 if s[j][i] == "#" else 0
    return ret

def main(h,w,k,s):
    ans=0
    for i in range(2**w):
        for j in range(2**h):
            ans += 1 if countb(h, w, j, i, s)==k else 0

    print(ans)
    return

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w, K = LI()
c = [list(input()) for _ in range(h)]
count = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == '#':
            count += 1
ans = 0
for i in range(1 << h):
    f = defaultdict(lambda : 0)
    cnt = count
    for k in range(h):
        if i >> k & 1:
            for l in range(w):
                if c[k][l] == "#" and f[(k, l)] == 0:
                    f[(k, l)] = 1
                    cnt -= 1
    for j in range(1 << w):
        cnt2 = cnt
        f2 = defaultdict(lambda : 0)
        for k, l in f.items():
            if l == 1:
                f2[k] = 1
        for k in range(w):
            if j >> k & 1:
                for l in range(h):
                    if c[l][k] == "#" and f2[(l, k)] == 0:
                        f2[(l, k)] = 1
                        cnt2 -= 1
        if cnt2 == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
from itertools import product
h, w, k = list(map(int, input().split()))
s = [list(map(str, list(input()))) for i in range(h)]

ans = 0
for bith in product([0, 1], repeat=h):
    for bitw in product([0, 1], repeat=w):
        ss = copy.deepcopy(s)
        tmp = 0
        for i, bh in enumerate(bith):
            for j, bw in enumerate(bitw):
                if bh == 1 or bw == 1:
                    ss[i][j] = 'o'
        for i in range(h):
            for j in range(w):
                if ss[i][j] == '#':
                    tmp += 1
        if tmp == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    H, W, K = map(int, input().split())
    C = [list(input()[:-1]) for _ in range(H)]
    black = 0
    for i in range(H):
        for j in range(W):
            if C[i][j] == "#":
                black += 1
    
    ans = 0
    for n in range(2**H):
        for m in range(2**W):
            tmp = black
            used = [[False]*W for _ in range(H)]
            for h in range(H):
                if n & (1 << h):
                    for j in range(W):
                        if C[h][j] == "#" and used[h][j] == False:
                            tmp -= 1
                            used[h][j] = True
            for w in range(W):
                if m & (1 << w):
                    for i in range(H):
                        if C[i][w] == "#" and used[i][w] == False:
                            tmp -= 1
                            used[i][w] = True
            if tmp == K:
                ans += 1
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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


def is_valid(xs, ys):
    k = 0
    for i in range(1, H + 1):
        if i in ys:
            continue
        for j in range(1, W + 1):
            if j in xs:
                continue
            if C[i - 1][j - 1] == '#':
                k += 1
    return k == K


ans = 0
for i in range(0, H + 1):
    for j in range(0, W + 1):
        for ys in itertools.combinations(range(1, H + 1), i):
            for xs in itertools.combinations(range(1, W + 1), j):
                if is_valid(xs, ys):
                    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 x in range(2**W):
    for y in range(2**H):
        m = [[False for _ in range(W)] for _ in range(H)]

        for xi in range(W):
            if ((x >> xi) & 1):
                for i in range(H):
                    m[i][xi] = True

        for yi in range(H):
            if ((y >> yi) & 1):
                for i in range(W):
                    m[yi][i] = True
        
        count = 0
        for i in range(W):
            for j in range(H):
                if C[j][i] == "#" and not m[j][i]:
                    count += 1
        if count == K:
            ans += 1
print(ans)

Submission status: Accepted

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

result = 0

for i in range(2 ** H):
    h = str(format(i, 'b')).zfill(H)
    for j in range(2 ** W):
        w = str(format(j, 'b')).zfill(W)
        count = 0
        for k in range(H):
            for l in range(W):
                if c[k][l] == "#" and h[k] == "0" and w[l] == "0":
                    count += 1
        if count == K:
            result += 1

print(result)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import itertools

import numpy as np

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

C = np.zeros((H, W))

for h in range(H):
    cs = input().strip()
    for w in range(W):
        C[h, w] = 1 if cs[w] == "#" else 0

count = 0

for max_h in range(H + 1):
    for max_w in range(W + 1):
        for hs in itertools.combinations(range(H), max_h):
            for ws in itertools.combinations(range(W), max_w):

                tmp = np.array(C)

                for h in hs:
                    for w in range(W): tmp[h, w] = 0

                for w in ws:
                    for h in range(H): tmp[h, w] = 0

                if int(np.sum(tmp)) == K:
                    count += 1

print(count)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Submission status: Accepted

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

M = [0]*h
for i in range(h):
  r = list(input())
  r = [0 if j == '.' else 1 for j in r ]
  M[i] = r
  

total = sum([sum(r) for r in M])

import copy
ans = 0
for i in range(2**h):
  for j in range(2**w):
    del_cnt = 0
    MC = copy.deepcopy(M)
    for x in range(h):
      if i>>x&1:
        for y in range(w):
          if MC[x][y]==1:
            MC[x][y] = 0
            del_cnt += 1
    for x in range(w):
      if j>>x&1:
        for y in range(h):
          if MC[y][x] == 1:
            MC[y][x] = 0
            del_cnt += 1
    if del_cnt == total - k:
      ans += 1
  
print(ans)

Submission status: Accepted

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

ans=0
for row in range(2**h):
    for col in range(2**w):
        cnt=0
        for i in range(h):
            for j in range(w):
                if (row>>i)&1 and (col>>j)&1 and matrix[i][j]=="#":
                    cnt+=1
        if cnt==k:
            ans+=1
            
print(ans)

Submission status: Accepted

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

for i in range(2 ** h):
    l = []
    for j in range(h):
        if ((i >> j) & 1):
            l.append(ma[j])

    for p in range(2 ** w):
        cnt = 0
        for q in range(w):
            if ((p >> q) & 1):
                for g in l:
                    if g[q] == "#":
                        cnt += 1
        if cnt == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
def check(C, H, W, hp, wp):
    count = 0
    for hi in range(H):
        for wi in range(W):
            if (C[hi][wi] == '#') and (0 == (hp&(1<<hi))) and (0 == (wp&(1<<wi))):
                count += 1
    return count

def main():
    H, W, K = map(int, input().split())
    C = [list(input()) for _ in range(H)]
    ans = 0
    for hp in range(2**H):
        for wp in range(2**W):
            if check(C, H, W, hp, wp) == K:
                ans += 1
    print(ans)

main()

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
B=[[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j,c in enumerate(input()):
        if c == "#":
            B[i][j] = 1

def getCnt(r,c):
    cnt = 0
    for i in r:
        for j in c:
            if B[i][j] == 1:
                cnt += 1
    return cnt

ans = 0
for y in range(2**H):
    r = []
    for i in range(H):
        if (y>>i) % 2 == 1:
            r.append(i)
    for x in range(2**W):
        c = []
        for j in range(W):
            if (x >> j) % 2 == 1:
                c.append(j)
        if getCnt(r,c) == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product, compress


def main():
    h, w, k = list(map(int, input().split()))
    c = [None for _ in range(h)]
    for i in range(h):
        c[i] = input()
    ans = 0
    for columns in product([1, 0], repeat=w):
        columns = list(compress(list(range(w)), columns))
        for rows in product([1, 0], repeat=h):
            count = 0
            rows = list(compress(list(range(h)), rows))
            # print(rows, columns)
            for row in rows:
                for column in columns:
                    if c[row][column] == "#":
                        count += 1
            if count == k:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
H,W,K=map(int,input().split())
c=[input() for _ in range(H)]
ans=0
for i in list(itertools.product([0,1], repeat=H+W)):
  a=0
  for j in range(H):
    if i[j]==1:
      continue
    for k in range(W):
      if i[H+k]==1:
        continue
      if c[j][k]=='#':
        a+=1
  if a==K:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
c = [list(input()) for _ in range(H)]
cH = [sum([1 for x in c[i] if x == '#']) for i in range(H)]
cW = [sum([1 for j in range(H) if c[j][i] == '#']) for i in range(W)]
B, ans = sum(cH), 0

for num in range(2**(W+H)):
    indexes = [(num >> i) % 2 for i in range(W+H)]
    indexesH = []
    temp = B
    for i in range(H):
        if indexes[i] == 1:
            temp -= cH[i]
            indexesH.append(i)
    for i in range(W):
        if indexes[H+i] == 1:
            temp -= cW[i] - sum([int(c[j][i] == '#') for j in indexesH])
    if temp == K:
        ans += 1
print(ans)

Submission status: Accepted

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

blk = 0
ans = 0

for i in range(h):
    for j in range(w):
        if c[i][j] == '#':
            blk += 1

for i in range(2**(h+w)):
    tmp_blk = blk
    tmp = format(i, '0'+str(h+w)+'b')
    for j in range(h):
        if tmp[j] == '1':
            #print(i,j)
            for k in range(w):
                if c[j][k] == "#":
                    tmp_blk -= 1
    for j in range(w):
        if tmp[h+j] == '1':
            for k in range(h):
                if c[k][j] == "#" and tmp[k] == '0':
                    tmp_blk -= 1
    if tmp_blk == K:
        ans += 1
    #print(tmp_blk)
        
print(ans)

Submission status: Accepted

Solution code:
# Contest No.: ABC173
# Problem No.: C
# Solver:      JEMINI
# Date:        20200705

import sys
import heapq

def main():
    h, w, K = map(int, input().split())
    table = []
    for _ in range(h):
        temp = input()
        table.append([])
        for i in temp:
            table[-1].append(i)    
    ans = 0
    for i in range(2 ** (w + h)):
        cnt = 0
        tempTable = [_[:] for _ in table]

        rowNum = i % (2 ** h)
        colNum = i // (2 ** h)
        cntRow = 0
        cntCol = 0

        while rowNum:
            if rowNum % 2:
                tempTable[cntRow] = ["R"] * w
            rowNum = rowNum // 2
            cntRow += 1
        while colNum:
            if colNum % 2:
                for j in range(h):
                    tempTable[j][cntCol] = "R"
            colNum = colNum // 2
            cntCol += 1
        for j in range(h):
            for k in range(w):
                if tempTable[j][k] == "#":
                    cnt += 1
        #print(i, cnt, K, tempTable)
        if cnt == K:
            ans += 1

    print(ans)


    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h,w,k = map(int,input().split())
s = 0
a = [[0]*(w+1)]
for i in range(h):
  ar = input().rstrip()
  for i in ar:
    if i == '#':
      s += 1
  a.append([0]+list(ar))
  
ans = 0
for i in range(2**(h+1)):
  for j in range(2**(w+1)):
    chk = s
    for num,ai in enumerate(a):
      if i>>num&1:
        for aa in ai:
          if aa == '#':
            chk -= 1
      else:
        for bb in range(w+1):
          if j>>bb&1 and ai[bb] == '#':
            chk -= 1
    if chk == k:
      ans += 1
print(ans//4)

Submission status: Accepted

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

import itertools
for conh in itertools.product([True,False], repeat = h):
    for conw in itertools.product([True,False], repeat = w):
        count = 0
        for i in range(h):
            for j in range(w):
                if conh[i] or conw[j]:
                    continue
                else:
                    if arr[i][j] == "#":
                        count += 1
        if count == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
h,w,k = map(int,input().split())
s = ["" for _ in range(h)]
for i in range(h):
  si = str(input())
  s[i] = si
lh = [i for i in range(h)]
lw = [j for j in range(w)]
sh = [0 for _ in range(h)]
sw = [0 for _ in range(w)]
for i in range(h):
  for j in range(w):
    if s[i][j] == "#":
      sh[i] += 1
      sw[j] += 1  
g = sum(sh) - k
c = 0
for i in range(h+1):
  for vh in itertools.combinations(lh,i):
    for j in range(w+1):
      for vw in itertools.combinations(lw,j):
        t = 0
        for hx in vh:
          t += sh[hx] 
        for hy in vw:
          t += sw[hy]
        for hx in vh:
          for hy in vw:
            if s[hx][hy] == "#":
              t -= 1
        if t == g:
          c += 1
print(c)

Submission status: Accepted

Solution code:
import copy
import itertools

h, w, k = map(int,input().split())
li = [list(input()) for i in range(h)]
ans = 0


#ビット全探索
for i in range(2**h):
    for j in range(2**w):
        x = copy.deepcopy(li)
        count = 0

        for b in range(h):
            if ((i >> b) & 1): #フラグが立っていたら
                x[b] = ["-"] * w
        for b in range(w):
            if ((j >> b) & 1): #フラグが立っていたら
                for a in range(h):
                    x[a][b] = "-"
        
        x = list(itertools.chain.from_iterable(x))
        if x.count("#") == k:
            ans += 1


print(ans)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
c = [[0] * W for i in range(H)]
p = 0
ans = 0
for i in range(H):
    a = str(input())
    for j in range(W):
        if a[j] == ".":
            c[i][j] = 0
        else:
            c[i][j] = 1
            p += 1
aa = [0]*(H + W)
for i in range(2**(H + W)):
    pp = p
    for j in range(H + W):
        aa[j] = i%2
        i = i//2
    for k in range(H):
        for l in range(W):
            if c[k][l] == 1:
                if aa[k] == 1 or aa[H + l] == 1:
                    pp -= 1
    if pp == K:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

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

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

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



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

Submission status: Accepted

Solution code:
import copy
H, W, K = list(map(int, input().split()))
c = []
for _ in range(H):
    s = input()
    tmp = []
    for one in s:
        if one=='#':
            tmp.append(1)
        else:
            tmp.append(0)
    c.append(tmp)


h = 1<<H
w = 1<<W
cnt = 0
for j in range(h):
    tmp_c = copy.deepcopy(c)#.copy()
    for p in range(H):
        if j>>p & 1==1:
            tmp_c[p] = [0]*W
    
    for i in range(w):
        tm_c = copy.deepcopy(tmp_c)#.copy()
        for q in range(W):
            if i>>q & 1==1:
                for k in range(H):
                    tm_c[k][q] = 0
        if sum([sum(one) for one in tm_c])==K:
            cnt+=1
print(cnt)

Submission status: Accepted

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

ans = 0

def foo(x,y):
  sx = set()
  i = 0
  while x > 0:
    if x % 2 == 1:
      sx.add(i)
    i += 1
    x //= 2
  sy = set()
  i = 0
  while y > 0:
    if y % 2 == 1:
      sy.add(i)
    i += 1
    y //= 2

  r = 0
  for i in range(H):
    for j in range(W):
      if b[i][j] == '#':
        if i not in sx and j not in sy:
          r += 1
  if r == K:
    return 1
  else:
    return 0

for i in range(2**H):
  for j in range(2**W):
    ans += foo(i,j)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from copy import deepcopy

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

ans = 0

for a in product([0,1], repeat = H+W):
    ca = deepcopy(c)
    for i in range(H):
        if a[i] == 1:
            for j in range(W):
                ca[i][j] = 'r'
    for j in range(W):
        if a[H+j] == 1:
            for i in range(H):
                ca[i][j] = 'r'
    count = 0
    for i in range(H):
        for j in range(W):
            if ca[i][j] == '#':
             count += 1
    if count == K:
             ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy
h,w,k=map(int, input().split())
s=[[0]*w for _ in range(h)]
for i in range(h):
    s[i]=list(input())

n=h+w
ans=0
for i in range(2**n):
    a=copy.deepcopy(s)
    for j in range(n):
        if ((i >> j) & 1):
            if j<h:
                for l in range(w):
                    a[j][l]='.'
            else:
                for l in range(h):
                    a[l][j-h]='.'
    cnt=0
    for j in range(h):
        for l in range(w):
            if a[j][l]=='#':
                cnt+=1
    if cnt==k:
        ans+=1
print(ans)