bit全探索
abc173
bit全探索とは
True Falseの2値で表せるような事象の組み合わせを探索したいときに、便利な探索方法
pythonでは
1<< HOGE
23 を表したいとき、
1bitを3つ左シフトさせること
探索で使いたいのでrange(1<<HOGE)
で使われる
2(100) == 10(8)
1か0かチェックするには
01というintで管理しているので、2で割ったあまりが1か見る。
productライブラリ
from itertools import product for a in product([True, False], repeat=H): for b in product([True, False], repeat=W):
問題
回答
H, W, K = map(int, input().split()) c = [input() for _ in range(H)] result = 0 for rows in range(1 << H): for cols in range(1 << W): black = 0 # bitが1になっているか2重ループで探索 # 赤なら黒ではないからcontinue # それ意外ならblackカウンタインクリメント for i in range(H): if (rows >> i) % 2 == 1: continue for j in range(W): if (cols >> j) % 2 == 1: continue if c[i][j] == "#": black += 1 if black == K: # ループのなかで条件に合う場合をカウントする result += 1 print(result)