Problem:


Score : 300 points

Problem Statement

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

Consider doing the following operation:

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

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

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

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

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

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

Sample Output 4

208



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


Sample output:
5

Submission status: Accepted

Solution code:

import numpy as np

H, W, K = map(int,input().split())
D = np.zeros([H,W])

black_count = 0
for i in range(H):
    C = list(input())
    for j in range(len(C)):
        if(C[j] == "#"):
            D[i][j] = 1


#print(D)
for i in range(2**H):
    h = format(i, '06b')
    for j in range(2**W):
        w = format(j, '06b')
        d = D.copy()

        for hi in range(H):
            if(h[5-hi] == '1'):
                d[hi,:]=0
        for wi in range(W):
            if(w[5-wi] == '1'):
                d[:,wi]=0
            
        if (d.sum() == K):
            black_count += 1

print(black_count)

Submission status: Accepted

Solution code:
H,W,K=map(int,(input().split()))
board=[list(input()) for _ in range(H)]
ans=0
for paint_H in range(2**H):
    for paint_W in range(2**W):
        cnt=0
        for i in range(H):
            for j in range(W):
                if(paint_H>>i)&1==0 and (paint_W>>j)&1==0:
                    if board[i][j]=="#":
                        cnt+=1
        if cnt==K:
            ans+=1
print(ans)

Submission status: Accepted

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

ans=0
for m in range(2**h):
    for l in range(2**w):
        a=0
        for i in range(h):
            for j in range(w):
                if m>>i&1 and l>>j&1 and c[i][j]=="#":
                    a+=1
        if a==k:
            ans+=1
print(ans)

Submission status: Accepted

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

ans = 0
for h in range(1 << H):
    for w in range(1 << W):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if h >> i & 1:
                    continue
                if w >> j & 1:
                    continue
                if C[i][j] == "#":
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

h,w,k = LI()
cnt = 0
c = [0]*h
for i in range(h):
    c[i] = input()

for rows in range(1 << h):
    for cols in range(1 << w):
        black = 0
        for i in range(h):
            if (rows >> i) % 2 == 1:
                continue
            for j in range(w):
                if (cols >> j) % 2 == 1:
                    continue
                black += c[i][j] == '#'
        if black == k:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
H,W,K = map(int, input().split())
c = []
for i in range(H):
  tmp = list(input())			# リスト型に変換することで文字列を１文字ずつ分解
  c.append(tmp)

count = 0
for i in range(int(2**H)):
  tmp = str(bin(i))				# bit変換
  h_flag = tmp[2:].zfill(H)		# 先頭にゼロを追加してH桁にする
  for j in range(int(2**W)):
    tmp = str(bin(j))			# bit変換
    w_flag = tmp[2:].zfill(W)	# 先頭にゼロを追加してH桁にする
    num_black = 0
    for m in range(H):
      for n in range(W):
        if h_flag[m] == '0' and w_flag[n] == '0' and c[m][n] == '#':
          num_black += 1
    if num_black == K:
      count += 1
print(count)

Submission status: Accepted

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

C = []
for _ in range(h):
  C.append([1 if i == '#' else 0 for i in input()])
C = np.array(C)
ans = 0
for i in range(2**h):
  for j in range(2**w):
    row = [l for l in range(h-1, -1, -1) if (i >> l) & 1]
    col = [l for l in range(w-1, -1, -1) if (j >> l) & 1]
    if len(row) > 0 and len(col) > 0:
      #print(row, col)
      s = C[row][:,col].sum()
      if len(row) > 1 and len(col) > 1:
        s = s.sum()
    else:
      s = 0
    if s == k:
      ans += 1
    #print(row, col, j)
print(ans)

Submission status: Accepted

Solution code:
import itertools
H,W,K = map(int,input().split())
init_map = []
for i in range(H):
    row = list(input())
    init_map.append(row)
ans = 0
 
for paint_h in range(2 ** H):
    for paint_w in range(2 ** W):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if (paint_h >> i)&1 == 0 and (paint_w >> j)&1 == 0:
                    if init_map[i][j] == "#":
                        cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

temp = []
for _ in range(H):
    C = list(input())
    A = [c.replace('.', '0') for c in C]
    A = [a.replace('#', '1') for a in A]
    A = list(map(lambda x: int(x), A))
    temp.append(A)

C = np.array(temp)

count = 0
l = [0, 1]
wide = itertools.product(l, repeat=W)
for w in wide:
    hight = itertools.product(l, repeat=H)
    for h in hight:
        copy_C = C.copy()
        # print('w: ', w)
        # print('h: ', h)
        for num, i in enumerate(w):
            if i == 1:
                copy_C[:, num-1] = 0
            for num2, j in enumerate(h):
                if j == 1:
                    copy_C[num2-1, :] = 0
        if copy_C.sum() == K:
            count += 1

print(count)

Submission status: Accepted

Solution code:
# coding:utf-8

h, w, k = map(int, input().split())
c = [list(input()) for _ in range(h)]
# print(c)
black = 0
H = []
W = []
ans = 0

for bit_h in range(2**h):
    for bit_w in range(2**w):
        black = 0
        for i in range(h):
            if not ((bit_h >> i) & 1):
                continue
            for j in range(w):
                if not ((bit_w >> j) & 1):
                    continue
                if c[i][j] == '#':
                    black += 1
        if black == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    H, W, K = map(int,input().split())
    Tgt = 0 - K
    Ch = [0] * H
    Cw = [0] * W
    Gmap = []
    for h in range(H):
        r = list(map(int, input().replace('.','0').replace('#','1')))
        Gmap.append(r)
        for w in range(W):
            x = Gmap[h][w]
            Ch[h] += x
            Cw[w] += x
            Tgt += x

    ret = 0
    for hs in range(2**H):
        for ws in range(2**W):
            cnt = 0
            for h in range(H):
                if hs >> h & 1:
                    cnt += Ch[h]
            for w in range(W):
                if ws >> w & 1:
                    cnt += Cw[w]
            for h in range(H):
                for w in range(W):
                    if (ws >> w & 1) and (hs >> h & 1):
                        cnt -= Gmap[h][w]
            if cnt == Tgt:
                ret +=1


    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,r = map(int,input().split())
l=[];an=0
cr=[];k=[0]*w
for i in range(h):
  x=list(input())
  l.append(x)
  cr.append(x.count('#'))
  for j in range(w):
    if x[j]=='#':
      k[j]+=1
ar=cr+k;tot=sum(cr)
tt=len(ar)
for i in range(1<<tt):
  re=tot;rr=[]
  cc=[]
  for j in range(tt):
    if i&(1<<j):
      re-=ar[j]
      if j>=h:
        cc.append(j-h)
      else:
        rr.append(j)
  for j in rr:
    for y in cc:
      if l[j][y]=='#':
        re+=1
  #print(i,rr,cc,re)
  if re==r:
    an+=1
  #print(i,re)
print(an)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
in_list = [[0] * w for i in range(h)]
for i in range(h):
    in_list[i][:] = input()
#print(in_list)

result = 0
for i in range(2**h):
    for j in range(2**w):
        cnt = 0
        for ih in range(h):
            for iw in range(w):
                if (i>>ih&1)==0 and (j>>iw&1)==0:
                    if in_list[ih][iw]=="#":
                        cnt+=1
        if cnt==k:
            result += 1
print(result)

Submission status: Accepted

Solution code:
import copy

H, W, K = map(int, input().split())
data = []
ans = 0
count = 0
for _ in range(H):
    line = list(input())
    count += line.count('#')
    data.append(line)
omega = count

# H, Wのbit全探索を行う。
for h in range(2 ** H):
    copy_data = copy.deepcopy(data)
    for f in range(H):
        if list(bin(h)[2:].zfill(H))[f] == '1':
            count -= copy_data[f].count('#')
            copy_data[f] = ['.' for _ in range(W)]
    tmp = count
    for w in range(2 ** W):
        count = tmp
        for g in range(W):
            if list(bin(w)[2:].zfill(W))[g] == '1':
                for row in copy_data:
                    if row[g] == '#':
                        count -= 1
        if count == K:
            ans += 1
    count = omega

print(ans)

Submission status: Accepted

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

cnt=0
for i in range(2**h):
  for j in range(2**w):
    black=0
    for hh in range(h):
      if bin((i>>hh)&0b1)==bin(1):
        continue
      for ww in range(w):
        if bin((j>>ww)&0b1)==bin(1):
          continue
        if c[hh][ww]=="#":
          black+=1
    if black==k:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import copy
H,W,K = map(int,input().split())
C = [list(input()) for _ in range(H)]
N = 0
for i in range(H):
  N += C[i].count("#")
ans = 0
for i in range(2**(H+W)):
  c = copy.deepcopy(C)
  R = 0
  for j in range(H+W):
    if ((i >> j) & 1):
      if j < H:
        R += c[j].count("#")
        c[j] = ["R"]*W
      else:
        for k in range(H):
          if c[k][j-H] == "#":
            R += 1
  if N - R == K:
    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 pattern_h in range(2**h):
  for pattern_w in range(2**w):
    count = 0
    for i in range(h):
      for j in range(w):
        if (pattern_h>>i)&1==0 and (pattern_w>>j)&1==0:
          if c[i][j]=='#':
            count += 1
    if count == k:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

def LI(): return list(map(int, stdin.readline().split()))
def LS(): return list(stdin.readline().rstrip('\n'))

h,w,k = LI()
a = [LS() for i in range(h)]
ans = 0
for r in range(1<<h):
    for c in range(1<<w):
        count = 0
        for i in range(h):
            for j in range(w):
                if (r>>i&1)==0 and (c>>j&1)==0 and a[i][j]=='#':
                    count += 1
        if count==k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
graph = []
for i in range(H):
    graph.append(list(input()))
    
ans = 0
for i in range(2**H):
    for j in range(2**W):
        black = 0
        for k in range(H):
            for l in range(W):
                if((i>>k)&1 == 0 and (j >>l)&1 == 0 and graph[k][l] == "#"):
                    black += 1
        if(black == K):
            ans += 1
print(ans)

Submission status: Accepted

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

mas = [0]*h
for i in range(h):
    mas[i] = input()

#rows　行　columns 列

cnt = 0
for rows in range(1 << h):
    for columns in range(1 << w):
        black = 0
        for i in range(h):
            if (rows >> i)%2 == 1:
                continue
            for j in range(w):
                if (columns >> j)%2 == 1:
                    continue
                if mas[i][j] == "#":
                    black += 1
        if black == k:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
'''
参考
https://note.com/tanon_cp/n/n9b0a77fcda7d
https://qiita.com/u2dayo/items/90a0693f31524e7b4cd0#c%E5%95%8F%E9%A1%8Ch-and-v
bit全探索を使用する
'''
from itertools import product

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

ans = 0

# bit全探索
for b_row in product([0, 1], repeat=H):             # 行の塗りつぶし全パターンを0か1で列挙
    for b_col in product([0, 1], repeat=W):         # 列の塗りつぶし全パターンを0か1で列挙
        cnt = 0
        for i in range(H):
            for j in range(W):                      # 全ての「i行目j列目」について調べる
                if b_row[i] == 0 and b_col[j] == 0: # 塗りつぶされないマス
                    if c[i][j] == '#':              # 黒のままだったらカウントアップ
                        cnt += 1
        if cnt == K:                                # 全ての「i行目j列目」についてカウント終了、黒マス数がKと一致したら
            ans += 1                                # 解答をカウントアップ

print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

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

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

b = [1, 0]
Bit = list(itertools.product(b, repeat = H+W))
#print(Bit)

ans = 0

for i in range(len(Bit)):
    tmp = copy.deepcopy(graph)
    
    cnt = 0
    for h in range(H):
        if Bit[i][h] == 1:
            for j in range(W):
                tmp[h][j] = "."
    for w in range(H, H+W):
        if Bit[i][w] == 1:
            for j in range(H):
                tmp[j][w-H] = "."
    for j in range(H):
        cnt += tmp[j].count("#")
    #print(tmp)
    if cnt == K:
        ans += 1
    #print(cnt)
        
print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import copy

h,w,k = mi()
masu = [[] for i in range(h)]

class masusu:
    def __init__(self,w,h,masu):
        self.w = w
        self.h = h
        self.masu = masu

    def calcBlack(self,hpat,wpat):
        masuc = copy.deepcopy( self.masu)
        for i in range(h):
            if (hpat >> i) & 1:
                masuc[i] = [0]*w
            for j in range(w):
                if (wpat >> j) & 1:
                    for l in range(h):
                        masuc[l][j] = 0
        
        sumtmp = 0
        for i in range(h):
            sumtmp += sum(masuc[i])
        return sumtmp


for i in range(h):
    c = input()
    for j in range(w):
        if c[j] == '.':
            masu[i].append(0)
        else:
            masu[i].append(1)

m = masusu(w,h,masu)

ans = 0
for hpat in range((2**h)-1):
    for wpat in range((2**w)-1):
        sumBlack = m.calcBlack(hpat,wpat)

        if sumBlack == k:
            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 h_ptn in range(2 ** H):
  for w_ptn in range(2 ** W):
    cnt = 0
    # 1マスずつ黒マスの存在確認
    for h in range(H):
      for w in range(W):
        if (h_ptn >> h) & 1 == 0 and (w_ptn >> w) & 1 == 0:
          if C[h][w] == '#':
            cnt += 1
    if cnt == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

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

all_list = []
for h in range(H):
    h_list = []
    tmp = input()
    for i in range(len(tmp)):
        if(tmp[i] == ('.')):
            h_list.append(0)
        else:
            h_list.append(1)
    all_list.append(h_list)

cnt = 0
for i_b in range(2 ** H):
    for j_b in range(2 ** W):
        cnt_tmp = 0
        all_list_tmp = copy.deepcopy(all_list)
        for i in range(H):
            if((i_b >> i) & 1):
                for j_tmp in range(W):
                    all_list_tmp[i][j_tmp] = 3
        for j in range(W):
            if((j_b >> j) & 1):
                for i_tmp in range(H):
                    all_list_tmp[i_tmp][j] = 3
        
        for i in range(H):
            cnt_tmp += all_list_tmp[i].count(1)
        if(cnt_tmp == K):
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
H, W, K = [int(x) for x in input().split()]
 
init_map = []
 
for i in range(H):
    row = list(input())
    init_map.append(row)
 
#print(init_map)
 
ans = 0
 
for paint_h in range(2 ** H):
    #print("h: " + str(paint_h))
    for paint_w in range(2 ** W):
        #print("w: " + str(paint_w))
        cnt = 0
        for i in range(H):
            for j in range(W):
                if (paint_h >> i)&1 == 0 and (paint_w >> j)&1 == 0:
                    if init_map[i][j] == "#":
                        cnt += 1
        if cnt == K:
            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
def check(a):
    global ans
    tmp = 0
    for i in range(H):
        for j in range(W):
            if a[i] and a[H+j] and C[i][j] == "#":
                tmp += 1
    ans += 1 if tmp == K else 0

def dfs(a):
    if len(a) == H+W:
        check(a)
        return
    for i in range(2):
        dfs(a+[i])

dfs([])
print(ans)

Submission status: Accepted

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

ans = 0
def check(h, w):
    global ans
    tmp = 0
    for i in range(H):
        for j in range(W):
            if h[i] and w[j] and C[i][j] == "#":
                tmp += 1
    ans += 1 if tmp == K else 0

def dfs(h, w):
    if len(h) < H:
        for i in range(2):
            dfs(h+[i],w)
    elif len(w) < W:
        for i in range(2):
            dfs(h,w+[i],)
    else:
        check(h, w)
    return


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

Submission status: Accepted

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

ans = 0
def check(h, w):
    global ans
    tmp = 0
    for i in range(H):
        for j in range(W):
            if h[i] and w[j] and C[i][j] == "#":
                tmp += 1
    ans += 1 if tmp == K else 0

def dfs(h,w,hidx,widx):
    if hidx < H:
        for i in range(2):
            dfs(h+[i],w,hidx+1,widx)
    elif widx < W:
        for i in range(2):
            dfs(h,w+[i],hidx,widx+1)
    else:
        check(h, w)
    return


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

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W, K = map(int, readline().split())
C = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W]

C = 1 * (C == b'#')

def f(C, x, y):
    rows = [i for i in range(H) if x & (1<<i)]
    cols = [i for i in range(W) if y & (1<<i)]
    D = C[rows][:,cols]
    return D.sum() == K

ans = 0
for x in range(1 << H):
    for y in range(1 << W):
        ans += f(C, x, y)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
h, w, p = map(int,input().split())
F = []
for i in range(h):
    F.append(list(input()))
    
ih = [i for i in range(h)]
iw = [i for i in range(w)]
ans = 0
for i in range(2 ** h):
    l_h = []
    for j in range(h):
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            l_h.append(ih[j])
    for j in range(2 ** w):
        l_w = []
        for k in range(w):
            if ((j >> k) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                l_w.append(iw[k])
        tmp = 0
        for u in l_h:
            for v in l_w:
                if F[u][v] == "#":
                    tmp += 1
        #print(tmp)
        if tmp == p:
            #print(tmp,k)
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def main():
    H, W, K = rli()
    grid = []
    for i in range(H):
        grid.append(input())
    ans = 0
    for mh in range(0, 2**H):
        for mw in range(0, 2**W):
            cnt = 0
            for h in range(H):
                for w in range(W):
                    if grid[h][w] == '#' and ((mh>>h)&1) and ((mw>>w)&1):
                        cnt += 1
            if cnt == K:
                ans += 1
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools,copy
h,w,k = map(int,input().split())
C = [list(input()) for i in range(h)]
ans = 0
for bith in range(2**h):
  for bitw in range(2**w):
    Ccopy = copy.deepcopy(C)
    for high in range(h):
      if (1 & bith>>high):
        for i in range(w):
          Ccopy[high][i] = "."
    for width in range(w):
      if (1 & bitw>>width):
        for i in range(h):
          Ccopy[i][width] = "."
    if list(itertools.chain.from_iterable(Ccopy)).count("#") == k:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
h,w,k=map(int,input().split())
c=[]
blacks=0
for hi in range(h):
    c.append(list(input()))
    blacks+=c[-1].count('#')
c=np.array(c)
#print(c)
x=h+w
bx=2**x
ans=0
max_ansi=0
for i in range(bx):
    bin_x=bin(i)[2:].zfill(x)
#    print(bin_x)
    line=[]
    row=[]
    ansi=0
    for j in range(h):
        if(bin_x[j]=='1'):
            line.append(j)
    for j in range(w):
        if(bin_x[h+j]=='1'):
            row.append(j)
    line=np.array(line)
    row=np.array(row)
    not_line=np.array(list(set([i for i in range(h)]) - set(line)))

    for j in range(x):
        if(bin_x[j]=='1'):
            if(j<h):
                ansi+=np.count_nonzero(c[j,:]=='#')
            elif(len(not_line)>0):
                m=j-h
                ansi+=np.count_nonzero(c[not_line[:],m]=='#')
    ansi=blacks-ansi
    if(ansi==k):
        ans+=1
#    print(ansi,ans,line,row,not_line)
print(ans)

Submission status: Accepted

Solution code:
import copy
import itertools
from itertools import product

def main():
    # productを使ってパターンを列挙して考える方法
    H, W, K = map(int, input().split())
    # あとで足し算で計算するので#は1にそれ以外は0へ
    C = [[1 if v == '#' else 0 for v in input()] for _ in range(H)]
    ans = 0
    # 塗り直すか塗り直さないかの01のパターンを出す
    HC = list(product([0,1], repeat=H))
    WC = list(product([0,1], repeat=W))
    # 選んだところは0に塗り直す
    c = copy.deepcopy(C)
    for hc in HC:
        for wc in WC:
            cnt = 0
            for hi, h in enumerate(hc):
                if h == 1:
                    for w in range(W):
                        c[hi][w] = 0
            for wi, w in enumerate(wc):
                if w == 1:
                    for h in range(H):
                        c[h][wi] = 0
            # flatten
            cnt = sum(list(itertools.chain.from_iterable(c)))
            if cnt == K:
                ans += 1
            c = copy.deepcopy(C)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

h, w, k = map(int, input().split())
grid = []
for _ in range(h):
    curRow = list(input())
    grid.append(curRow)

def countBlack(g):
    result = 0
    for row in g:
        result += row.count("#")
    return result

choices = list(range(h)) + list(range(w))


def checkChoice(path):
    curGrid = copy.deepcopy(grid)
    for i in range(h):
        if path[i]:
            for j in range(w):
                curGrid[i][j] = "r"
    for j in range(h, len(choices)):
        if path[j]:
            curCol = j - h
            for i in range(h):
                curGrid[i][curCol] = "r"
    return countBlack(curGrid) == k

result = 0
def solve(i, path):
    global result
    if i == len(choices):
        result += checkChoice(path)
    else:
        path.append(True)
        solve(i + 1, path)
        path.pop()
        path.append(False)
        solve(i + 1, path)
        path.pop()

solve(0, [])
print(result)

Submission status: Accepted

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

t=0	
for h in range(2**H):
  for w in range(2**W):
    b=0
    for i in range(H):
      if h&2**i:
        continue
      for j in range(W):
        if w&2**j:
          continue
        if C[i][j]=='#':
          b+=1
    if b==K:
      t+=1

print(t)

Submission status: Accepted

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

D = [list(list(input())) for _ in range(H)]


import numpy as np
D = np.array(D)

count = 0
for bit_H in range(2**H):
    for bit_W in range(2**W):
        C = D.copy()
        for h in range(H):
            mask = 1 << h
            if bit_H & mask:
                C[h, :] = 'h'    
        for w in range(W):
            mask = 1 << w
            if bit_W & mask:
                C[:, w] = 'w'
            
        if np.count_nonzero(C == '#') == K:
            count += 1
#            print(C)
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
H,W,K=map(int,input().split())

D=np.zeros([H,W])

for i in range(H):
    C=input()
    for j in range(W):
        if C[j]=="#":
            D[i,j]=1


ans=0

for i in range(2**H):
    h="{:06b}".format(i)
    for j in range(2**W):
        w="{:06b}".format(j)

        d=D.copy()
        for hi in range(H):
            if h[5-hi]=="1":
                d[hi,:]=0
        for wi in range(W):
            if w[5-wi]=="1":
                d[:,wi]=0
        #print(d.sum())
        if d.sum()==K: ans+=1



print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
c = [input() for i in range(h)]
a = 0
for i in range(2**h):
    for j in range(2**w):
        b = 0
        hb = format(i, '12b')
        wb = format(j, '12b')
        for m in range(h):
            for l in range(w):
                if hb[-m-1] == '1' and wb[-l-1] == '1' and c[m][l] == '#':
                    b += 1
        if b == k:
            a += 1
print(a)

Submission status: Accepted

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

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

ans = 0
for maskr in range(0, 1<<h):
    for maskc in range(0, 1<<w):
        black = 0
        for i in range(h):
            for j in range(w):
                if ((maskr>>i) & 1) == 0 and ((maskc>>j) & 1) == 0 and field[i][j] == '#':
                    black +=1
        if black == k:
            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 paint_h in range(2**h):
  for paint_w in range(2**w):
    cut=0
    for i in range(h):
      for j in range(w):
        if (paint_h>>i)&1==0 and (paint_w>>j)&1==0:
          if c[i][j]=='#':
            cut+=1
    if cut==k:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

h,w,k = map(int, input().split())
g = [['']*w for _ in range(h)]
for i in range(h):
    g[i] = input()

res = 0
for p in product((0,1), repeat = h):
    for q in product((0,1), repeat = w):
        black = 0
        for i in range(h):
            for j in range(w):
                if p[i] == 1 and q[j] == 1 and g[i][j] == '#':
                    black += 1
        if black == k:
            res += 1
print(res)

Submission status: Accepted

Solution code:
import itertools
def MI(): return map(int, input().split())
H,W,K=MI()
Map=[input() for _ in range(H)]
ans=0
for gyou in itertools.product([0,1],repeat=H):
  for retsu in itertools.product([0,1],repeat=W):
    count=0
    for i in range(H):
      for j in range(W):
        if gyou[i] and retsu[j]:
          if Map[i][j]=='#':
            count+=1
    if count==K:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
cells = [[''] * m for i in range(n)]

def count_black(num1, num2):
    num1 = bin(num1)[2:].rjust(n, '0')
    num2 = bin(num2)[2:].rjust(m, '0')
    blacky = 0
    for i in range(n):
        for j in range(m):
            if num1[i] != '1' and num2[j] != '1' and cells[i][j] == '#':
                blacky += 1
    return blacky == k

def get_ways(r, c):
    result = 0
    for i in range(0, 2 ** r):
        for j in range(0, 2 ** c):
            ans = count_black(i, j)
            result += 1 if ans else 0
    return result

for i in range(n):
    string = input()
    for j in range(m):
        cells[i][j] = string[j]

num_ways = get_ways(n, m)
print(num_ways)

Submission status: Accepted

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

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

    ans = 0
    for i in range(2 ** H):
        for j in range(2 ** W):
            count = 0
            for n in range(H):
                for m in range(W):
                    if ((i >> n) & 1) == 0 and ((j >> m) & 1) == 0 and C[n][m] == '#':
                        count += 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
def MI(): return map(int, input().split())
H,W,K=MI()
Map=[input() for _ in range(H)]
ans=0
for gyou in range(1<<H):
  for retsu in range(1<<W):
    count=0
    for i in range(H):
      if (gyou>>i)&1:
        for j in range(W):
          if (retsu>>j)&1:
            if Map[i][j]=='#':
              count+=1
    if count==K:
      ans+=1
print(ans)

Submission status: Accepted

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

def num2bi(x, k):
  out=format(x, '0'+str(k)+'b')
  return out

ans=0
for x in range(2**H):
  for y in range(2**W):
    p=num2bi(x, H)
    q=num2bi(y, W)
    cnt=0
    for s in range(H):
      for t in range(W):
        if p[s]=='0' and q[t]=='0' and c[s][t]=='#':
          cnt+=1
          
    if cnt==K:
      ans+=1
      
print(ans)

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
H,W,K=MI()
Map=[input() for _ in range(H)]
ans=0
for gyou in range(1<<H):
  for retsu in range(1<<W):
    count=0
    for i in range(H):
      for j in range(W):
        if (gyou>>i)&1 and (retsu>>j)&1:
          if Map[i][j]=='#':
            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)]

ans = 0
for b1 in range(2**h):
    for b2 in range(2**w):
        black = 0
        for i in range(h):
            for j in range(w):
                if (b1 >> i) & 1 == 0 and (b2 >> j) & 1 == 0 and c[i][j] == "#":
                    black +=1
                    
        if black == k:
            ans += 1

print(ans)