[BOJ]ジャンプゲーム(no.1558)

質問する

尚根はゲームを作り、右図に示す地図で行います.
地図は2行に分かれており、各行はN個の格子に分かれている.格子は危険格子と安全格子に分けられ、安全格子はプレイヤーが移動できる格子であり、危険格子は移動できない格子である.
最初は、プレイヤーは左の列の1号車の上に立って、毎秒以下の3つの行為の1つをします.
1つ前に移動します.たとえば、現在のセルがi番の場合、i+1番のセルに移動します.
1つ後ろに移動します.たとえば、現在のセルがi番の場合、i-1番のセルに移動します.
向こうのロープに飛び込む.このとき,元のセルよりk個前のセルに移動する.たとえば、現在のセルが左行のi番セルの場合、右行のi+k番セルに移動する必要があります.
N号車よりも大きな車両に移動すれば、ゲームは完了です.
ゲームをおもしろくするために、尚根は毎秒1コマを消す機能を作った.すなわち、ゲーム開始1秒後には1号車が消え、2秒後には2号車が消える.勝手にプレイヤーが先に移動し、格子が消えると仮定します.つまり、今回消えるのは3号車で、尚根が3号車で、3号車から別の車両に移動すると、3号車は消えてしまいます.
各欄の情報が提供される場合は、ゲームをクリアできるかどうかを判断するプログラムを作成します.

入力

第1行はNとKを与える.(1 ≤ N, k ≤ 100,000)
2行目には、左の行の情報が表示されます.i最初の文字が0の場合は危険なスペース、1の場合は安全なスペースです.3行目は右の行の情報を与え、各文字の意味は左の行の意味と同じである.
左の列の1号車はいつも安全です.

しゅつりょく

ゲームがクリアできたら出力1、なければ出力0.

🤔 の意見を打診

これは比較的条件の多いbfs問題である.

0と1からなるので、비트마스킹で解くのは簡単かもしれませんが、演算量が大きすぎるため、通常のTrue False配列で扱うことにしました.

i-1,i+1,i+kの場合は,アクセス配列検査とともにnが超えると停止することを提示する.

論理は難しくない...
中間インデックスがあまりにも葛藤して、髪の毛を少しつかんだ.

📌 説明する

import sys
input = sys.stdin.readline

def main():
    n,k = map(int, input().split())
    q = [(0,0)]
    dirs = [input(), input()]
    cache = [[False]*n for _ in range(2)]
    rm = 0

    while q:
        tmp = []

        for i,d in q:
            if i+1 >=n or i+k >= n:
                print(1)
                sys.exit()

            if dirs[d][i+1] == '1' and not cache[d][i+1]:
                cache[d][i+1] = True
                tmp.append((i+1,d))
            if i-1 > rm and dirs[d][i-1] == '1' and not cache[d][i-1]:
                cache[d][i-1] = True
                tmp.append((i-1,d))
            if dirs[1-d][i+k] == '1' and not cache[1-d][i+k]:
                cache[1-d][i+k] = True
                tmp.append((i+k,1-d))

        rm += 1
        q = tmp

    print(0)

if __name__ == "__main__":
    sys.exit(main())

レビュー

インデックス...索引索引索引ㅠ

が1本も見えなければ、死んでも見えない.

最初はどうやって編んだほうがいいか整理しておきましょう.