[python]伯準14939:消灯

質問リンク
https://www.acmicpc.net/problem/14939

に近づく

電球はオン/オフなので、ビットマスクを思い浮かべました.
ただし、行ごとに2^10=1024のスペースが必要で、正しく分割するには、そのスペースに10回乗算する必要があります(2^100.)状況です.
行きたいと思ってどうしても思い出せず、別のブログを参考に…
https://lem0nad3.tistory.com/7

に答える

思ったより解答が簡単でした.(思い出せないけど…)

の第1行に現れる可能性のある(電球を押す)すべての場合(1024個)、
1-1. 現在の数に電球を設定します.
1-2. 2行目から、各列は、現在位置の1つの格子に電球が点灯している場合、現在位置の電球pressを巡回する.
1-3. 最後の列まで確認したら、最後の列に電球がなかったら成功!もしあったら失敗!

最小値

で

を出力.
コードで見るのが簡単かもしれません.

first_line_press_case = [101] * (1 << 10)
for case in range(1 << 10):
    tmp_board = [board[i][:] for i in range(10)]  # copy board to tmp board
    cnt = 0

    # set case
    mask = 1
    for j in range(9, -1, -1):
        if case & mask:
            press(tmp_board, 0, j)
            cnt += 1
        mask <<= 1

    # 2번 줄부터 끝까지
    for i in range(1, 10):
        for j in range(10):
            if tmp_board[i - 1][j]:  # 현재 위치 위에 전구가 켜져있으면
                press(tmp_board, i, j)  # 현재 위치 press
                cnt += 1

    # 만일 마지막줄 전구 다 꺼져있으면 성공!
    if sum(tmp_board[9]) == 0:
        first_line_press_case[case] = cnt

1行目の電球を押すと閲覧します.最初の行が標準です.
setcase部分は現在のcaseに従って電球を設定しますか?押します.
(現在の状況では、各ビットが電球位置に対応している)
2番線から10番線まで、各行の列を確認します.
確認バーの上のバーが表示され、上のバーの電球が開いている場合は、現在の確認バーを押します.(クリック数も増えた!)
コア!!!i号線の操作(i号線を1回見終わった)が完了し、i-1号線の電球がオフになっています
10行目を検索すると、最後の行(10行目)が表示されます.
最後の列の電球が切れたら成功します.どうせ上の作業で9列目までの電球は閉まっていて、10列目までの電球が閉まっていれば、すべての電球が閉まっています.
この考えはまだ思い出せないようだ.
こんな質問がコセトに出てきたら、答えられるかどうか疑問ですが・・・
まず、できるだけ多くのタイプとアルゴリズムを熟知することが重要らしい.

正しいコード

import sys

sys.setrecursionlimit(10 ** 8)  # pypy 제출시 삭제!
input = lambda: sys.stdin.readline().rstrip()
in_range = lambda y, x: 0 <= y < 10 and 0 <= x < 10

dy = [0, 0, 1, 0, -1]
dx = [0, 1, 0, -1, 0]


def press(b, y, x):
    for i in range(5):
        ny, nx = y + dy[i], x + dx[i]
        if in_range(ny, nx):
            b[ny][nx] = (b[ny][nx] + 1) % 2


board = [[0 for _ in range(10)] for _ in range(10)]

for i in range(10):
    line = input()
    for j in range(len(line)):
        if line[j] == "O":
            board[i][j] = 1

first_line_press_case = [101] * (1 << 10)
for case in range(1 << 10):
    tmp_board = [board[i][:] for i in range(10)]  # copy board to tmp board
    cnt = 0

    # set case
    mask = 1
    for j in range(9, -1, -1):
        if case & mask:
            press(tmp_board, 0, j)
            cnt += 1
        mask <<= 1

    # 2번 줄부터 끝까지
    for i in range(1, 10):
        for j in range(10):
            if tmp_board[i - 1][j]:  # 현재 위치 위에 전구가 켜져있으면
                press(tmp_board, i, j)  # 현재 위치 press
                cnt += 1

    # 만일 마지막줄 전구 다 꺼져있으면 성공!
    if sum(tmp_board[9]) == 0:
        first_line_press_case[case] = cnt


print(min(first_line_press_case))