縦横二重のビット全探索について

Question

#問題


AtCoder ABC173 C問題より

#方針
とりあえず、縦H行、横W列の計(2^(H + W))通りについて、与えられたボードを各パターンで白に塗りつぶし(最終的な黒を数えるのだから赤ではなく白で塗り戻すのも一緒)、それらを一度出力することで中身を確認したいです。

#入力 (以下の出力はこの入力に従う)

2 3 2
..#
###

#コード

from itertools import product

H, W, K = map(int, input().split())

board = []
for _ in range(H):
    board.append(str(input()))

_board = board.copy()

for bith in list(product([0, 1], repeat = H)):
    for bitw in list(product([0, 1], repeat = W)):

        for indh, to_whitenh in enumerate(bith):
            for indw, to_whitenw in enumerate(bitw):

                if to_whitenh:
                    board[indh] = '.' * W
                if to_whitenw:
                    for el in board:
                        el = list(el)
                        el[indw] = '.'
                        ''.join(el)

        print(board)

        for i in range(len(board)):
            board[i] = _board[i]

#出力

['..#', '###']
['..#', '###']
['..#', '###']
['..#', '###']
['..#', '###']
['..#', '###']
['..#', '###']
['..#', '###']
['..#', '...']
['..#', '...']
['..#', '...']
['..#', '...']
['..#', '...']
['..#', '...']
['..#', '...']
['..#', '...']
['...', '###']
['...', '###']
['...', '###']
['...', '###']
['...', '###']
['...', '###']
['...', '###']
['...', '###']
['...', '...']
['...', '...']
['...', '...']
['...', '...']
['...', '...']
['...', '...']
['...', '...']
['...', '...']

#問題点
どうやら、縦H行についてのパターンは出来ているように見えます。しかし、横W列についてのビット全探索が全く出来ておらず、結果縦の2^2 = 4つのパターンしか出来ていません。if to_whitenwの箇所で横のビット全探索についても上手く出来たと思ったのですが、どのような箇所が理由で期待する結果とならないのでしょうか。素人質問にて恐縮ですが、ご教授のほどよろしくお願い申し上げます。

Answer 1

ビット全探索ができてないわけじゃなくてビットパターンに対する出力をうまく作れてないだけです。
普通に二次元リストを使えばシンプルに書けます。

from itertools import product
+from copy import deepcopy
H, W, K = map(int, input().split())

board = []
for _ in range(H):
-    board.append(str(input()))
+    board.append(list(input()))

-_board = board.copy()
+_board = deepcopy(board)

for bith in list(product([0, 1], repeat = H)):
    for bitw in list(product([0, 1], repeat = W)):

        for indh, to_whitenh in enumerate(bith):
            for indw, to_whitenw in enumerate(bitw):
-                if to_whitenh:
-                    board[indh] = '.' * W
-                if to_whitenw:
-                    for el in board:
-                        el = list(el)
-                        el[indw] = '.'
-                        ''.join(el)
+                if to_whitenh or to_whitenw:
+                    board[indh][indw] = 'W'

        print(board)

-        for i in range(len(board)):
-            board[i] = _board[i]
+        board = deepcopy(_board)

普通のcopyとdeepcopyの違いには気を付けてください。

Comments

[kay_ventris4]

めちゃくちゃ分かり易かったです。
copyとdeepcopyの使い分けも理解することが出来ました。ありがとうございました。