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 itertools
bit_base = 2#bit_base^nの全探査になる. 
def Base_10_to_n(X, n):#10進数をbit_base進数に変換
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out

def main():
  H, W, K = map(int, input().split())
  C = []
  for i in range(H):
    C.append(str(input()))
  num_b = 0
  for i in range(H):
    for j in range(W):
      if C[i][j] == "#":
        num_b += 1
  ans = 0
  for i in range(bit_base**(H+W)):
    s = Base_10_to_n(i, bit_base)
    s = s.zfill(H+W)
    flag_h = []
    flag_w = []
    for num, j in enumerate(s):
      if j == '1':
        if num < H:
          flag_h.append(num)
        else:
          flag_w.append(num-H)
    temp = num_b
    for i in flag_h:
      for j in range(W):
        if C[i][j] == "#":
          temp -= 1
    for j in flag_w:
      for i in range(H):
        if C[i][j] == "#":
          temp -= 1
    for i, j in itertools.product(flag_h, flag_w):
      if C[i][j] == "#":
        temp += 1
    if temp  == K:
      ans += 1
  print(ans)
    
if __name__ == "__main__":
  main()

Submission status: Accepted

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

for i in range(2**H):
  for j in range(2**W):
    tmp_i = format(i,"0"+str(H)+"b")
    tmp_j = format(j,"0"+str(W)+"b")
    tmp = 0
    for p in range(H):
      if tmp_i[p] == "0":
        continue
      for q in range(W):
        if tmp_j[q] == "0":
          continue
        if HW[p][q] == "#":
          tmp += 1
    #print(tmp)
    if tmp == K:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
H, W, K = map(int, input().split())
squares = [list(input()) for _ in range(H)]
# black_squares = []
# for i in range(H):
#     accumrated_list = []
#     for j, color in enumerate(list(input())):
#         if color == '#':
#             accumrated_list.append(1)
#         else:
#             accumrated_list.append(0)
#     accumrated_list = list(accumulate(accumrated_list))
#     black_squares.append(accumrated_list)
# print(black_squares)
# black_count = 0
# for i in range(H):
#     black_count += black_squares[i][W - 1]

# print(black_count)
# 2,3のエリアで、
# 消すところが0,0の場合、1,1から
ans = 0
for hs in range(1 << H):
    for ws in range(1 << W):
        # ここまででどの行と列を使うかが決まる。
        # 使用する行と列に含まれる黒の数をカウントする
        count = 0
        for i in range(H):
            for k in range(W):
                if hs >> i & 1 and ws >> k & 1:
                    # そこは使うのでカウントする
                    # print(hs >> i, ws >> k)
                    if squares[i][k] == '#':
                        count += 1
        if count == K:
            ans += 1
print(ans)

Submission status: Accepted

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


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    H, W, K = MI()
    cells = []
    ans = 0
    for i in range(H):
        row = input()
        rows = []
        for item in range(len(row)):
            if row[item] == ".":
                rows.append(0)
            else:
                rows.append(1)
        cells.append(rows)

    for i in range(2**H):
        for j in range(2**W):
            iBi = format(i, '0'+str(H)+'b')
            jBi = format(j, '0'+str(W)+'b')

            tmp_cell = copy.deepcopy(cells)

            for ii in range(H):
                for jj in range(W):
                    if str(iBi)[ii] == '1' or str(jBi)[jj] == '1':

                        tmp_cell[ii][jj] = 0
            if sum(map(sum, tmp_cell)) == K:
                ans += 1

    print(ans)

    # oj t -c "pypy3 main.py"
    # acc s main.py -- --guess-python-interpreter pypy


main()

Submission status: Accepted

Solution code:
import copy
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def count_black(board, H, W):
    ans = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == "#":
                ans += 1
    return ans


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

    ans = 0
    for i in range(2**(H+W)):
        tmp = copy.deepcopy(board)
        for j in range(H+W):
            if (i >> j) & 1:
                if j < H:
                    tmp[j] = ["R"] * W
                else:
                    for k in range(H):
                        tmp[k][j - H] = "R"
        if count_black(tmp, H, W) == K:
            ans += 1
    return ans


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

Submission status: Accepted

Solution code:
def main():
    from itertools import product
    h, w, k = map(int, input().split())
    c = [input() for _ in range(h)]

    ans = 0
    for x in product([0, 1], repeat=h):
        for y in product([0, 1], repeat=w):
            res = 0
            for i, xx in enumerate(x):
                for j, yy in enumerate(y):
                    if xx and yy and c[i][j] == "#":
                        res += 1
            if res == k:
                #print(x, y, xx, yy, c[i][j])
                ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np


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

    field = np.zeros([H, W]).astype(int)
    for i in range(H):
        for j in range(W):
            if c[i][j] == '.':
                field[i][j] = 0
            else:
                field[i][j] = 1

    raw_field = field.copy()
    count = 0
    for i in range(2 ** (W+H)):
        field = raw_field.copy()
        searching = bin(i)[2:]
        searching = '0' * ((W+H) - len(searching)) + searching
        for k in range(W+H):
            if k < W and searching[k] == '1':
                field[:, k] = 0
            elif W <= k < W+H and searching[k] == '1':
                field[k-W, :] = 0
        if field.sum() == K:
            count += 1
    print(count)
    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for i in product(range(2), repeat=h):
    row_ind = [ii for ii in range(h) if i[ii] == 1]
    for j in product(range(2), repeat=w):
        col_ind = [jj for jj in range(w) if j[jj] == 1]
        tmp = 0
        for sub_i in row_ind:
            for sub_j in col_ind:
                if A[sub_i][sub_j] == '#':
                    tmp += 1
        if tmp == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
C = [[1 if c == "#" else 0 for c in input()] for _ in range(H)]
ans = 0
for bith in range(1 << H):
    for bitw in range(1 << W):
        c = [x[:] for x in C]
        for h in range(H):
            if bith & (1 << h):
                c[h] = [0] * W
        for w in range(W):
            if bitw & (1 << w):
                for h in range(H):
                    c[h][w] = 0
        count = sum(sum(x) for x in c)
        if count == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools


def count_black(row, col):
    count = 0
    for i, x in enumerate(row):
        for j, y in enumerate(col):
            if x == 0 and y == 0:
                if C[i][j] == "#":
                    count += 1
    return count


if __name__ == "__main__":
    H, W, K = [int(x) for x in input().split(" ")]
    C = []
    for _ in range(H):
        c = [s for s in input()]
        C.append(c)
    # print(C)
    ans = 0
    for row in itertools.product([0, 1], repeat=H):
        for col in itertools.product([0, 1], repeat=W):
            if count_black(row, col) == K:
                ans += 1
    print(ans)

Submission status: Accepted

Solution code:
def main():
    h, w, target = map(int, input().split())
    inlis = []
    for _ in range(h):
        clis = input()
        inlis.append(clis)
    ans = 0
    #print(inlis[0][2])
    for i in range(2 ** h):
            for k in range(2 ** w):
                tmp = 0
                for l in range(w):
                    for j in range(h):   
                        if ((i >> j) & 1) and ((k >> l) & 1) and inlis[j][l] == "#":
                            tmp += 1
                if tmp == target:
                    ans += 1
                    #print(i,j,k,l)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w, k=map(int, input().split())
l = [[] for _ in range(h)]
for _ in range(h):
  s=str(input())
  for o in s:
    if o=="#":
      l[_].append(1)
    else:
      l[_].append(0)
import numpy as np
l=np.array(l)
cnt=0

from itertools import product
s = [0,1]
for v1 in sorted(list(product(s, repeat=h)), reverse=1):
  for v2 in sorted(list(product(s, repeat=w)), reverse=1):
    lcal=l
    v1a=[]
    for i in v1:
      v1a.append([i])
    v1a=np.array(v1a)
    v2a=np.array(v2)
    lcal=v2a*lcal
    lcal=v1a*lcal
    if sum(sum(lcal))==k:
      cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 16:22:00 2020

@author: neb0123
"""

import itertools

def solution(A,n,m,k):
	cnt = 0
	for i in range(n+1):
		R = list(itertools.combinations(range(n),i))
		for row in R:
			for j in range(m+1):
				C = list(itertools.combinations(range(m),j))
				for column in C:
					B = [A[i][:] for i in range(n)]
					s = 0
					for r in row:
						B[r] = ['.' for _ in range(m)]
					for c in column:
						for ro in range(n):
							B[ro][c] = '.'
					for r in B:
						for p in r:
							if p == '#':
								s += 1
					if s == k:
						cnt += 1
	return cnt


if __name__ == "__main__":
	n,m,k = map(int, input().split(' '))
	A = []
	for _ in range(n):
		A.append(list(input()))
	print(solution(A,n,m,k))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline().rstrip('\n')
    

def calc(H, W, K, C):
    ans = 0
    for ph in range(2 ** H):
        sh = format(ph, '0{0}b'.format(H))
        for pw in range(2 ** W):
            sw = format(pw, '0{0}b'.format(W))
            n = 0
            for i in range(H):
                if sh[i] == '1':
                    for j in range(W):
                        if sw[j] == '1':
                            n += (1 if C[i][j] == '#' else 0)
            if n == K:
                ans += 1
    return ans


(H, W, K) = tuple([int(s) for s in input().split()])
C = [list(input()) for _ in range(H)]
print(calc(H, W, K, C))

Submission status: Accepted

Solution code:
import itertools
import copy
def main():
    H, W, K = map(int, input().split())
    board = [list(input()) for i in range(H)]
    ans = 0

    for i in range(H + 1):
        for j in range(W + 1):
            for row in itertools.combinations(range(H), i):
                for col in itertools.combinations(range(W), j):

                    paint = copy.deepcopy(board)
                    
                    if len(row) == 0:
                        pass
                    else:
                        for r in row:
                            for k in range(W):
                                paint[r][k] = "-"

                    if len(col) == 0:
                        pass
                    else:
                        for c in col:
                            for l in range(H):
                                paint[l][c] = "-"

                    count = 0
                    for k in range(H):
                        for l in range(W):
                            if paint[k][l] == "#":
                                count += 1

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

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

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

ans = 0
for hi in range(2**H):
    tmp_hw = copy.deepcopy(hw)
    for hj in range(H):
        if ((hi >> hj) & 1):
            # bitが立っている時の操作
            for i in range(W):
                tmp_hw[hj][i] = 'x'

    tmp_cnt = 0
    for i in range(H):
        tmp_cnt += tmp_hw[i].count('#')
    if tmp_cnt < K:
        continue

    for wi in range(2**W):
        tmp_hw2 = copy.deepcopy(tmp_hw)
        for wj in range(W):
            if ((wi >> wj) & 1):
                # bitが立っている時の操作
                for i in range(H):
                    tmp_hw2[i][wj] = 'x'
        cnt = 0
        for i in range(H):
            cnt += tmp_hw2[i].count('#')
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy
h, w, k = list(map(int, input().split()))
maze = []
for i in range(h):
  li = []
  tmp = input()
  for j in range(w):
    li.append(tmp[j])
  maze.append(li)

h_total_li = list(itertools.product([1, 0], repeat=h))
w_total_li = list(itertools.product([1, 0], repeat=w))
ans = 0
for h_val in h_total_li:
  for w_val in w_total_li:
    now = 0
    tmp_maze = copy.deepcopy(maze)
    for h_ind, each_h in enumerate(h_val):
      if each_h == 1:
        for i in range(w):
          tmp_maze[h_ind][i] = 1
    for w_ind, each_w in enumerate(w_val):
      if each_w == 1:
        for i in range(h):
          tmp_maze[i][w_ind] = 1

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

    if now == k:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
def solve(C,H,W,tate,yoko,sum):
    for h in range(H):
        if 2**h & tate != 0:
            for w in range(W):
                if C[h][w] == "#":
                    sum -= 1

    for w in range(W):
        if 2**w & yoko != 0:
            for h in range(H):
                if C[h][w] == "#":
                    sum -= 1

    for h in range(H):
        for w in range(W):
            if 2**h & tate != 0 and 2**w & yoko != 0 and C[h][w] == "#":
                sum += 1

    return sum

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

    sum,ans = 0,0
    for h in range(H):
        for w in range(W):
            if C[h][w] == "#":
                sum += 1

    for i in range(2**H):
        for j in range(2**W):
            if solve(C,H,W,i,j,sum) == K:
                ans += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

sl=[]
for i in range(H):
    s=input()
    sl.append(s)

sh=list(range(H))
sw=list(range(W))

cnt=0

for i in range(H+1):
    for sqh in itertools.combinations(sh,i):
        for j in range(W+1):
            for sqw in itertools.combinations(sw,j):
                bcnt=0
                #print(sqh,sqw)
                for k in range(H):
                    for l in range(W):
                        if k not in sqh and l not in sqw:
                            if sl[k][l]=="#":
                                bcnt+=1
                
                if bcnt==K:
                    cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
import copy
h,w,v=map(int,input().split())
c=[list(input()) for _ in range(h)]
ans=0
for i in range(2**w):
  a=copy.deepcopy(c)
  tr1=bin(i)[2:].zfill(w)
  for k in range(w):
    if tr1[k]=='1':
      for l in range(h):
        a[l][k]='.'   
  for j in range(2**h):
    tr2=bin(j)[2:].zfill(h)
    cnt=0
    for k in range(h):
      if tr2[k]=='1':
          cnt+=a[k].count('#')
    if cnt==v:ans+=1
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
    print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

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

    def map_int_input():
        return map(int, input())

    MII = map_int_input

    def MII_split():
        return map(int, input().split())

    def MII_to_index():
        return map(to_index, input())

    def MII_split_to_index():
        return map(to_index, input().split())

    # 入力全てを整数に変換したものの配列を受け取る
    def list_int_inputs():
        return list(map(int, input()))

    LII = list_int_inputs

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

    # 2次元リスト化
    def LII_2D(rows_number):
        return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number):
        return [LII_split() for _ in range(rows_number)]

    import itertools
    import copy

    H, W, K = MII_split()
    field = [input() for _ in range(H)]

    # print(field)

    ans = 0
    rows = [i for i in range(H)]
    cols = [i for i in range(W)]
    for row_num in range(H + 1):
        for col_num in range(W + 1):
            # 行の選び方
            for paint_rows in itertools.combinations(rows, row_num):
                for paint_cols in itertools.combinations(cols, col_num):
                    tmp_field = copy.deepcopy(field)
                    blacks = 0
                    for i, row in enumerate(tmp_field):
                        if i in paint_rows:
                            continue
                        for j, col in enumerate(row):
                            if j in paint_cols:
                                continue
                            if col == '#':
                                blacks += 1
                    if blacks == K:
                        ans += 1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
listc = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == ".":
            listc[i][j] = 0
        else:
            listc[i][j] = 1

ans = 0
#print(listc[1])
for i in range(2**H):
    l = i
    tmp = []
    for j in range(H-1,-1,-1):
        if l >= (2**j):
            tmp.append(listc[j])
            l -= 2**j
    #print(tmp)
    for j in range(2**W):
        h = j
        t = 0
        for k in range(W-1,-1,-1):
            if h >= (2**k):
                for x in range(len(tmp)):
                    t += tmp[x][k]
                h -= 2**k
        #print(j,t)
        if t == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    H,W,K = map(int,input().split())
    c = [input().rstrip() for i in range(H)]

    res = 0

    for i in range(2**H):
        for j in range(2**W):
            cnt = 0
            for k in range(H):
                for l in range(W):
                    if ((i >> k) & 1) | ((j >> l) & 1):
                        continue
                    if c[k][l] == '#':
                        cnt += 1
            if cnt == K:
                res += 1

    print(res)



main()

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
c = [list(map(int, list(input().replace('.', '0').replace('#', '1')))) for _ in range(h)]
cs = [[0] for _ in range(h)]
y = 0
for i, ci in enumerate(c):
    for j, cij in enumerate(ci):
        cs[i].append(cs[i][-1])
        cs[i][-1] += c[i][j]
    y += cs[i][-1]
ans = 0
for i in range(2 ** h):
    for j in range(2 ** w):
        x = 0
        for ii in range(h):
            if (i >> ii) & 1:
                x += cs[ii][-1]
            else:
                for jj in range(j):
                    if (j >> jj) & 1:
                        x += c[ii][jj]
        ans += (y - x == k)
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = [x.strip() for x in open(0).readlines()]
h, w, k = map(int, X[0].split())
grid_origin = Grid(X[1:])
ans = 0
for i in range(2 ** h):
    grid_tmp = deepcopy(grid_origin.grid)
    Y = [k for k in range(h) if (i >> k) & 1]
    for y in Y:
        grid_tmp[y, :] = 'x'
    
    for j in range(2 ** w):
        grid = deepcopy(grid_tmp)
        X = [k for k in range(w) if (j >> k) & 1]
        for x in X:
            grid[:, x] = 'x'
        ans += np.sum(grid == '#') == k
print(ans)

Submission status: Accepted

Solution code:
def main():
    h, w, k = map(int, input().split())
    c = [list(input()) for _ in range(h)]
    hp, wp = [], []
    def dfs_h(hl):
        if len(hl) == h:
            hp.append(hl)
            return
        dfs_h(hl + [0])
        dfs_h(hl + [1])
    
    def dfs_w(wl):
        if len(wl) == w:
            wp.append(wl)
            return
        dfs_w(wl + [0])
        dfs_w(wl + [1])
    
    dfs_h([])
    dfs_w([])
    
    ans = 0
    for fh in hp:
        for fw in wp:
            num = 0
            for hi, i in enumerate(fh):
                if i == 1:
                    continue
                for wi, j in enumerate(fw):
                    if j == 1:
                        continue
                    if c[hi][wi] == "#":
                        num += 1
            if num == k:
                ans += 1
    print(ans)
                    
            
            
            

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
from itertools import combinations_with_replacement
from itertools import product
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, W, K = NMI()
    grid = [SI() for _ in range(H)]

    n = H + W
    ans = 0
    for case in range(2**n):
        cnt = 0
        for i in range(H):
            for j in range(W):
                if (case >> i) & 1:
                    if (case >> j + H) & 1:
                        if grid[i][j] == "#":
                            cnt += 1
        if cnt == K:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans=0
for i in range(1<<w):
    for j in range(1<<h):
        cnt=0
        for x in range(w):
            for y in range(h):
                if c[y][x]=="#":
                    if (i>>x)&1==0 and (j>>y)&1==0:
                        cnt+=1

        if cnt==k:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import copy

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

c_ = [input() for i in range(H)]
c = [[0] * W for i in range(H)]


for i in range(H):
    for j in range(W):
        if c_[i][j] == "#":
            c[i][j] = 1

ans = 0
for idxs in product(range(2), repeat=H+W):
    tmp_c = copy.deepcopy(c)

    for idx, j in enumerate(idxs):
        if j == 1:
            if idx < H:
                for x in range(W):
                    tmp_c[idx][x] = 0
            else:
                for x in range(H):
                    tmp_c[x][idx-H] = 0

    cnt = 0
    for i in range(H):
        for j in range(W):
            if tmp_c[i][j] == 1:
                cnt += 1
                
    if cnt == K:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

def calc_hash_bool(Len, hash):
    bools = [False] * Len
    for i in range(Len-1, -1, -1):
        remainder = hash %2
        if(remainder==1):
            bools[i] = True
        hash //= 2
    return bools

def calc_combinations(height, width, boards, demand_black):
    """
    縦: 2^6 = 64
    横: 2^6 = 64
    64^2 = 4096通り
    """
    combinations = 0
    #hashを2進数で考えて000000-> どれも選ばない, 111111->全て選択(色を染める)、というように
    for hash_h in range(2**height):
        bool_h = calc_hash_bool(height, hash_h)
        for hash_v in range(2**width):
            bool_v = calc_hash_bool(width, hash_v)
            N_black = 0
            for i in range(height):
                for j in range(width):
                    if(bool_h[i]==False and bool_v[j]==False and boards[i][j]=="#"):
                        N_black += 1
            if(N_black==demand_black):
                combinations += 1
    return combinations



if(__name__ == "__main__"):

    height, width, demand_black = map( int, input().strip().split() )

    boards = [ [] for i in range(height) ]
    N_black_total = 0
    for i in range(height):
        Str = input().strip()
        for j in Str:
            boards[i].append(j)
            if(j=="#"):
                N_black_total += 1
    if(N_black_total < demand_black):
        print("0")
    else:
        combinations = calc_combinations(height, width, boards, demand_black)
        print(combinations)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 0
for p in product([0,1],repeat=H+W):
  cnt = 0
  for i in range(H):
    for j in range(W):
      if S[i][j]=='#' and p[i]==0 and p[H+j]==0:
        cnt += 1
  if cnt == K:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

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

c = list()
for _ in range(H):
    c.append(list(input()))

ns = [i for i in range(H + W)]

res = 0
for n in range(H + W + 1):
    for tup in itertools.combinations(ns, n):
        _c = copy.deepcopy(c)
        for r in tup:
            if r < H:
                for w in range(W):
                    _c[r][w] = '-'
            else:
                for h in range(H):
                    _c[h][r - H] = '-'
        count = 0
        for h in range(H):
            for w in range(W):
                if _c[h][w] == '#':
                    count += 1

        if count == K:
            res += 1

print(res)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
cnt = 0
d = [[0]*(W) for _ in range(H)]
h = [0]*H
w = [0]*W
for i in range(H):
    A = input()
    for j in range(len(A)):
        if A[j]=='#':
            cnt += 1
            d[i][j] = 1
            h[i] += 1
            w[j] += 1
ans = 0
for i in range(2**H):
    I = bin(i)[2:]
    I = I.zfill(H)
    for j in range(2**W):
        J = bin(j)[2:]
        J = J.zfill(W)
        tmp = cnt
        for k in range(len(I)):
            if I[k]=='1':
                tmp-=h[k]
        for l in range(len(J)):
            if J[l] =='1':
                tmp-=w[l]
        for k in range(len(I)):
            for l in range(len(J)):
                if I[k]=='1' and J[l]=='1':
                    tmp += d[k][l]
        if tmp ==K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

def Hdfs(pat,hw):
    if len(pat)==hw:
        p=pat[:]
        Hlist.append(p)
        return
    else:
        pat.append(0)
        Hdfs(pat,hw)
        pat.pop()
        pat.append(1)
        Hdfs(pat,hw)
        pat.pop()

def Wdfs(pat,hw):
    if len(pat)==hw:
        p=pat[:]
        Wlist.append(p)
        return
    else:
        pat.append(0)
        Wdfs(pat,hw)
        pat.pop()
        pat.append(1)
        Wdfs(pat,hw)
        pat.pop()

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

cnt=0
Hlist=[]
Wlist=[]
Hdfs([],H)
Wdfs([],W)
for i in Hlist:
    for j in Wlist:
        cnt=0
        for h in range(H):
            for w in range(W):
                if i[h]==0 and j[w]==0 and c[h][w]=="#":
                    cnt+=1
        if cnt==K:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

Hs = []
for i in range(H + 1):
    Hs.extend(list(itertools.combinations(range(H), i)))
Ws = []
for i in range(W + 1):
    Ws.extend(list(itertools.combinations(range(W), i)))

ans = 0
for h_list in Hs:
    for w_list in Ws:
        C_tmp = C.copy()
        for h in h_list:
            for i in range(W):
                C_tmp[h][i] = 'r'

        for w in w_list:
            for i in range(H):
                C_tmp[i][w] = 'r'

        c = 0
        for i in range(H):
            for j in range(W):
                if C_tmp[i][j] == '#':
                    c += 1
        if c == K:
            ans += 1

print(ans)