ABC173Cによる学び（bit全探索、多次元リストのコピー、多次元リストの一次元化）

ABC173Cは非常に学びが多く、今後の参考になりそうなので個人的な備忘録代わりに。

ABC173C

import copy  # 多次元リストの値渡し/深いコピー(Deep Copy): copy.deepcopy()のため

h, w, k = map(int, input().split())
grd = [list(i for i in input()) for _ in range(h)]
ans = 0
for i in range(2**h):  # 行の選び方が2**h通りで、そのうちi番目
    grd1 = copy.deepcopy(grd)  # grdの値渡し/深いコピー(Deep Copy)
    for i1 in range(h):  # 2**h通りは２進数にしたときh桁で、そのうちi1桁目
        if i >> i1 & 1:  # 「2**h通りのうちi番目」のiを２進数にしたとき、どの桁が1になっているか
            grd1[i1] = ['r'] * w
    for j in range(2**w):  # 列の選び方が2**w通りで、そのうちj番目
        grd2 = copy.deepcopy(grd1)  # grd1の値渡し/深いコピー(Deep Copy)
        for j1 in range(w):  # 2**w通りは２進数にしたときw桁で、そのうちj1桁目
            if j >> j1 & 1:  # 「2**w通りのうちj番目」のjを２進数にしたとき、どの桁が1になっているか
                for n in range(h):
                    grd2[n][j1] = 'r'
        if sum(grd2,[]).count('#') == k:  # sum()で2次元リストを一次元に平坦化
            ans += 1
print(ans)

bit全探索

bit全探索に関してはいろいろな記事があるが、概して初心者かつPythonしか使えない人には難しい。以下はそんな人にもわかりやすく、まずbit全探索って何をするのかを掴むのにはちょうどよい。
Python de アルゴリズム（bit全探索）

多次元リストのコピー

リスト.copy()やリスト[:]を使って、オブジェクトの破壊・非破壊など意識して書いたつもりではあったが、思ったとおりに動いてくれなくて（上のコードではgrdが意図せずに書き換わって）困った。
コピーには参照渡し/浅いコピー(Shallow Copy)と値渡し/深いコピー(Deep Copy)があり、copyライブラリのcopy.copy()とcopy.deepcopy()では特に多次元リストで挙動が異なる。
Python - リストを複製する
【Python】多次元リストのコピー

多次元リストの一次元化

この問題のように多次元のリストを一元的に集計したいようなときに便利。いくつかやり方はあるようだが、sum()の意外な使い方も。
Pythonでflatten（多次元リストを一次元に平坦化）