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)
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)
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
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)
Recommended Posts