学生の備忘録なブログ

日々のことを忘れないためのブログです。一日一成果物も目標。技術系はQiitaにあげるように変更しました。

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):

問題

C - H and V

回答

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)