ABC173 C - H and V

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W, K = il()
    line = [iss() for _ in range(H)]

    ret = 0
    for h in range(1 << H):
        for w in range(1 << W):
            cnt = 0
            for i in range(H):
                for j in range(W):
                    if h >> i & 1 and w >> j & 1 and line[i][j] == '#':
                        cnt += 1
            if cnt == K:
                ret += 1
    print(ret)


if __name__ == '__main__':
    main()

考え方

ある行（または列）を使うか、使わないかの2択を全探索する。
2択の全探索なので、bit全探索を使用する。
今回の問題では、行と列を選択するので、2重のbit全探索。
計算量は最大2 ^ 12 。

---

行と列の使用するか否かを判定する基準に、
1をHビット左シフトした値と1をWビット左シフトした値を使用する。
全てのH(0, 1, .... ,H-1)とW(0, 1, ... , W-1)に対して基準を元に使用するか否かを判定し、
使用するマスのうち、黒いマスの数をカウントする。

あとは黒いマスの数がKと一致しているか否かを判定することで回答。