Edit

【pythonでABC173を解説】C - H and V

問題概要

問題ページ

C - H and V
C - H and V

問題ページへ移動する

問題文

\(H\) 行 \(W\) 列に並ぶマスからなるマス目があります。上から \(i\) 行目、左から \(j\) 列目 \((1 \leq i \leq H, 1 \leq j \leq W)\) のマスの色は文字 \(c_{i,j}\) として与えられ、\(c_{i,j}\) が . のとき白、# のとき黒です。

次の操作を行うことを考えます。

  • 行を何行か選び (\(0\) 行でもよい)、列を何列か選ぶ (\(0\) 列でもよい)。そして、選んだ行に含まれるマスと、選んだ列に含まれるマスをすべて赤く塗る。

正の整数 \(K\) が与えられます。操作後に黒いマスがちょうど \(K\) 個残るような行と列の選び方は何通りでしょうか。ここで、二つの選び方は、一方においてのみ選ばれる行または列が存在するときに異なるとみなされます。

制約

  • \(1 \leq H, W \leq 6\)
  • \(1 \leq K \leq HW\)
  • \(c_{i,j}\) は . または #

問題の考察

ACコード

import sys
import itertools
import copy


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w, kv = list(map(int, input().rstrip('\n').split()))
    c = [[0 if v == "." else 1 for v in str(input().rstrip('\n'))] for _ in range(h)]
    cnt = 0
    for i in itertools.product([True, False], repeat=h):
        for j in itertools.product([True, False], repeat=w):
            cc = copy.deepcopy(c)
            for ii in range(len(i)):
                if i[ii]:
                    for k in range(w):
                        cc[ii][k] = 0
            for jj in range(len(j)):
                if j[jj]:
                    for k in range(h):
                        cc[k][jj] = 0
            if sum([sum(cc[i]) for i in range(h)]) == kv:
                cnt += 1
    print(cnt)


if __name__ == '__main__':
    solve()

-Edit
-