ABC173 C問題(bit全探索)

C - H and V

要約

白と黒で埋められた表をどれかの列，行を赤で塗りつぶした時に残る黒色のマスがK個になるパターンを求める問題．

最初は手につかなかったが，途中で各列，各行を塗るor塗らないの2通りの全探索になることが分かった．．

つまり，全部でH行,W列を塗るか塗らないかの最大2^(H+W)通り全探索すればよく，H+Wは最大で12なので余裕で間に合う．

このことからbit全探索を行えば良いことが分かる．

以前この記事でbit全探索の問題について扱ったため，これと同じ方針で解いていく．

意識する点としては，

・各列，各行でbit全探索をしていくこと．

・わざわざ表を塗り替える必要はなく，各要素ずつ見ていけば良いこと

の2点である．実装に関してはコードにコメントを記入したのでそちらを参考にしてほしい

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

ans = 0
from itertools import product
#Trueが塗られないとする
for h_bit in product((True, False) , repeat = H):
 for w_bit in product((True, False), repeat = W):
   cnt = 0
   #----1つ1つの要素を見てくループ--
   for h in range(H):
     for w in range(W):
       #注目する要素が#でなおかつその行，列が塗られなければ良い
       if A[h][w] == "#" and (h_bit[h] and w_bit[w]):
         cnt += 1
   
   if cnt == K:
     ans += 1
print(ans)