이 게임은 각 면에 1에서 6까지의 숫자가 적힌 주사위 큐브를 사용합니다.
게임은 총 100개의 정사각형으로 나누어진 10×10 보드에서 진행됩니다.
1에서 100까지의 숫자가 칠판에 차례로 쓰여 있습니다.
플레이어는 주사위를 굴려 표시된 숫자만큼 뽑아야 합니다.
예를 들어, 플레이어가 셀 i에 있고 굴린 숫자가 4인 경우 플레이어는 셀 i+4로 이동해야 합니다.
주사위 굴림이 100칸을 넘으면 움직일 수 없습니다.
도착한 사각형이 사다리라면 사다리를 올라갑니다.
뱀이 있는 광장에 도착하면 뱀을 따라 내려가세요. 즉, 사다리를 이용하여 이동한 셀의 개수는 원래의 셀보다 많고, 큐를 이용하여 이동한 셀의 개수는 원래의 셀보다 작다.
게임의 목표는 정사각형 1에서 시작하여 정사각형 100에 도달하는 것입니다.
게임 보드의 상태가 주어지면 셀 100에 도달하기 위해 굴려야 하는 최소 주사위 수를 알아봅시다.
기입
첫 번째 줄은 보드에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)을 나타냅니다.
두 번째 행부터 N행에는 도체 정보를 의미하는 x, y(x < y)가 표시된다.
즉, 정사각형 x에 도달하면 정사각형 y로 이동합니다.
다음 M 행에는 대기열 정보를 나타내는 u 및 v(u > v)가 제공됩니다.
이것은 정사각형 u에 도달하면 정사각형 v로 이동한다는 것을 의미합니다.
사각형 1과 100은 뱀과 사다리의 시작도 끝도 아닙니다.
각 사각형에는 최대 하나의 사다리 또는 뱀이 있으며 동시에 둘 다 있을 수 없습니다.
항상 셀 100에 도달할 수 있는 항목만 제공됩니다.
누르다
셀 100에 도달하는 데 필요한 최소 주사위 굴림 수를 인쇄합니다.
(설명)
import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
x_dict = {}
for _ in range(N+M):
x, y = map(int, sys.stdin.readline().split())
x_dict(x) = y
def bfs(st):
Q = deque()
Q.append(st)
visited = (0) * 101
visited(st) = 0
while Q:
x = Q.popleft()
if visited(100):
break
for i in range(1,7):
nx = x + i
if nx < 101:
if not visited(nx):
if nx in x_dict:
if not visited(x_dict(nx)):
visited(nx) = visited(x) + 1
num = visited(nx)
nx = x_dict(nx)
Q.append(nx)
visited(nx) = num
else:
Q.append(nx)
visited(nx) = visited(x) + 1
print(visited(100))
bfs(1)
(주의)
– 뱀이 시작하는 지역에는 뱀과 사다리가 하나씩만 있을 수 있지만 도착하는 곳에서는 겹칠 수 있습니다.
예) 2 0
7 94
8 94