ヘビとはしご遊び

白駿16928

100号車に到着するためには、最低何回かサイコロを投げます.

ゲームでは正六面体サイコロを使用し、サイコロの各面に1から6までの数字が書かれています.ゲームサイズは10×10で、全部で100個の格子の碁盤で行います.黒板には1から100まで順番に数字が書いてあります.

プレイヤーはサイコロの数に従って移動する必要があります.例えば、プレイヤーがi号車でサイコロが転がった数字が4であれば、i+4号車に移動すべきである.サイコロ投げの結果が100回を超えると移動できません.到着した部屋ははしごで、はしごに登ります.ヘビの巣に着いたら、ヘビについて行きます.つまり、はしごで移動したセルの番号は元のセルの番号より大きく、ヘビで移動したセルの番号は元のセルの番号より小さい.

ゲームのターゲットは1号車から100号車までです.
ゲームボードの状態を取得するには、100番までにサイコロを投げる回数の最高値が必要です.

i#の変数宣言が表示されます.この場合、各変数の右側にあるすべての変数型を左側に移動し、プログラムを作成し、各行に変数を宣言します.

の第1行は、ゲームボード上の梯子の数N(1≦N≦15)およびヘビの数M(1≦M≦15)を与える.

の2行目から、N行は勾配情報を表すx,y(x

の次のM行は、ヘビを表す情報のu,v(u>v)を与える.u号車に到着すると、v号車に移動することを意味します.

1号車と100号車は蛇や梯子の始まりや終わりではありません.各格には最大1つの梯子や蛇があり、同時に両方がある場合はありません.常に100号車までの入力しか与えられません.

にゅうしゅつりょく

入出力3 732 6242 6812 9895 1397 2593 3779 2775 1949 4767 1734 98526 8026 7251 1939 1137 2981 359 579 2353 743 3377215

方法

:bfsを使用します.梯子と蛇のためのディックラウンジを作り、その数が出たときに対応する数に移動します.

知るところ

次の動作は梯子、蛇、スペースで、それぞれ並んでいます.関係ありません.

移動中にメアリーがいなかったので(もっと時間が短い…)同様の追加.

コード#コード#

from collections import deque

def bfs(ladder, snake, visited):
    q = deque()
    q.append(1)
    visited[1] = 0

    while q:
        x = q.popleft()
        if x==100:
            print(visited[100])
            return
        
        for i in range(6, 0, -1):
            move = x+i
            if move <= 100:
                if move in ladder and visited[ladder[move]] == -1:
                    visited[ladder[move]] = visited[x]+1
                    q.append(ladder[move])
                
                if move not in ladder and move not in snake and visited[move] == -1:
                    visited[move] = visited[x]+1
                    q.append(move)
                
                if move in snake and visited[snake[move]] == -1:
                    visited[snake[move]] = visited[x]+1
                    q.append(snake[move])
        

n, m = map(int, input().split())
ladder = {}
snake = {}
for _ in range(n):
    s, e = map(int, input().split())
    ladder[s] = e
for _ in range(m):
    s, e = map(int, input().split())
    snake[s] = e
visited = [-1]*101
bfs(ladder, snake, visited)