AtCoder Beginner Contest 173 C - H and V【Python】

https://atcoder.jp/contests/abc173/tasks/abc173_c

AtCoder ProblemsのRecommendationでDifficulty: 653、Solve Probability: 41%でした。
bit全探索で解くことができました。 for loopごとにリストをコピーしたのですが、多次元リストの場合はdeepcopyでないといけないことを知りました。

import copy

H, W, K = map(int, input().split())
C = []
for i in range(H):
    s = input()
    C.append(list(s))

ALL = 1 << (H+W)

def has_bit(n, i):
    return (n & (1<<i) > 0)
ans = 0
for n in range(ALL):
    res = copy.deepcopy(C)
    for i in range(H+W):
        if has_bit(n, i):
            if i < H:
                res[i] = ["r"] * W
            else:
                for j in range(H):
                    res[j][i-H] = "r"
    count = 0
    for k in range(H):
        count += res[k].count("#")
    if count == K:
        ans += 1

print(ans)