https://atcoder.jp/contests/abc173/submissions/15023087

abc173_c_wa.py

# WA

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

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

from pprint import pprint
# pprint(C)
import sys
from collections import Counter
from itertools import product, combinations

counter = Counter()
for row in C:
    counter.update(row)
n_blacks = counter['#']

if n_blacks < K:
    print(0)
    sys.exit()
# elif n_blacks == K:
#     # 黒がいない行、列があると破綻するからこの elif は NG
#     print(1)
#     sys.exit()


board = ''
for row in C:
    board += row

def get_calc_board_index_row(board, n_rows, n_cols):
    b = board
    _n_rows = n_rows
    _n_cols = n_cols
    def fun(n_row):
        # row number
        return list(range(_n_rows * n_row, _n_rows * n_row + _n_cols))
    return fun

calc_board_index_row = get_calc_board_index_row(board=board, n_rows=H, n_cols=W)

def get_calc_board_index_col(board, n_rows, n_cols):
    b = board
    _n_rows = n_rows
    _n_cols = n_cols
    def fun(n_col):
        # row number
        return list(range(
            n_col,
            n_col + _n_rows * _n_cols,
            _n_cols))
    return fun

calc_board_index_col = get_calc_board_index_col(board=board, n_rows=H, n_cols=W)

def get_print_board(board, n_rows, n_cols):
    b = board
    _n_rows = n_rows
    _n_cols = n_cols
    def fun():
        # row number
        for r in _n_rows:
            print(b[r*_n_cols, r*_n_cols+_n_cols])
    return fun

print_board = get_print_board(board, H, W)

# sys.exit()

# 消し込む行と列の数 (n_row, n_col) について、すべてのパターンで繰り返す
# i = 0
ans = 0
for n_row, n_col in product(range(H+1), range(K+1)):
    # n_row 個の行を消し込む場合の、行番号の組み合わせ
    choosed_rows = list(combinations(range(H), n_row))
    # n_col 個の列を消し込む場合の、列番号の組み合わせ
    choosed_cols = list(combinations(range(W), n_col))
    # print(n_row, n_col)
    # 消し込みするマスを計算
    for i_r, i_c in product(range(len(choosed_rows)), range(len(choosed_cols))):
        board_idx = set()
        for _r in choosed_rows[i_r]:
            board_idx.update(calc_board_index_row(_r))
        for _c in choosed_cols[i_c]:
            board_idx.update(calc_board_index_col(_c))

        rest_blacks = 0
        for ix in range(len(board)):
            if ix in board_idx: continue
            if board[ix] == '#':
                rest_blacks += 1
        # pprint({
        #     'choosed_rows': choosed_rows[i_r],
        #     'choosed_cols': choosed_cols[i_c],
        #     'rest_blacks': rest_blacks
        # })

        if rest_blacks == K:
            # print(removing_row_numbers, removing_col_numbers)
            ans += 1
    # print({
    #     'n_row': n_row,
    #     'n_col': n_col,
    #     'choosed_rows': choosed_rows,
    #     'choosed_cols' : choosed_cols,
    #     'board_idx': board_idx,
    #     'rest_blacks': rest_blacks
    # })
    # print()

print(ans)