[PYTHON] Learning by ABC173C (bit full search, copying of multidimensional list, one-dimensionalization of multidimensional list)

ABC173C is a lot of learning and will be useful for future reference, so instead of a personal memorandum.

ABC173C

import copy  #Passing by value in a multidimensional list/Deep copy(Deep Copy): copy.deepcopy()for

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):  #How to choose a row 2**h street, ith of them
    grd1 = copy.deepcopy(grd)  #By value of grd/Deep copy(Deep Copy)
    for i1 in range(h):  # 2**h street is h digit when converted to binary number, of which i1 digit
        if i >> i1 & 1:  # 「2**Which digit is 1 when i of "ith out of h streets" is converted to a binary number
            grd1[i1] = ['r'] * w
    for j in range(2**w):  #How to choose a column 2**On w street, jth of them
        grd2 = copy.deepcopy(grd1)  #Passing by value of grd1/Deep copy(Deep Copy)
        for j1 in range(w):  # 2**The w street is the w digit when converted to a binary number, of which the j1 digit
            if j >> j1 & 1:  # 「2**Which digit is 1 when j of "jth of w streets" is converted to a binary number
                for n in range(h):
                    grd2[n][j1] = 'r'
        if sum(grd2,[]).count('#') == k:  # sum()Flatten a 2D list to 1D with
            ans += 1
print(ans)

bit full search

There are various articles about bit full search, but it is generally difficult for beginners and those who can only use Python. The following is easy to understand for such a person, and it is just right to grasp what to do by doing a full bit search first. Python de algorithm (bit full search)

Copy of multidimensional list

I intended to write using list.copy () and list [:] with the intention of destroying and non-destructing objects, but it didn't work as expected (in the above code). I was in trouble (when grd was unintentionally rewritten). There are two types of copy: pass by reference / shallow copy (Shallow Copy) and pass by value / deep copy (Deep Copy), and the copy library copy.copy () and copy.deepcopy () behave especially in multidimensional lists. Is different. Python --Duplicate list [Python] Copy of multidimensional list

One-dimensionalization of multidimensional list

This is useful when you want to centrally aggregate a multidimensional list like this problem. There seem to be several ways to do it, but there is also a surprising use of sum (). Flatten in Python (flattening a multidimensional list to one dimension)