Python에서 뱀과 사다리 게임에서 최소 이동을 찾는 프로그램

뱀과 사다리 게임을 한다고 가정해 봅시다. 주사위에서 원하는 숫자를 굴릴 수 있다는 조건이 있습니다. 우리는 위치 0에서 시작하고 목적지는 위치 100이며 목적지에 도달하기 위해 주사위를 여러 번 굴립니다. 보드에서 뱀과 사다리의 위치가 제공된 경우 목적지에 도달하는 데 필요한 주사위 굴림의 최소 수를 찾아야 합니다. 뱀과 사다리 배열은 보드에서 뱀과 사다리의 위치와 각 항목을 나타냅니다 배열은 보드의 뱀이나 사다리의 시작 값과 끝 값을 포함합니다.

따라서 입력이 사다리와 같다면 =[(11, 40), (37,67),(47, 73),(15, 72)], 뱀 =[(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)], 출력은 8이 됩니다.

뱀과 사다리의 위치를 ​​고려할 때 보드에서 100번째 위치에 도달하는 데 필요한 최소 이동 횟수는 8입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 배열 스네이크를 배열 사다리에 추가
• 가장자리:=새 지도
• 사다리에 있는 각 쌍 f,t에 대해 다음을 수행합니다.
  • 가장자리[f] :=t
• u :=새로운 세트
• v :=새로운 세트
• v에 추가(1)
• m :=0
• v에 100이 없으면 do
  • m :=m + 1
  • w :=새로운 세트
  • v의 각 f에 대해
    • 1~6 범위의 i에 대해 다음을 수행합니다.
      • n :=f + i
      • n이 가장자리에 있으면
        • n :=가장자리[n]
      • n이 u에 있으면
        • 다음 반복으로 이동
      • 당신에게 추가(n)
      • w에 추가(n)
  • v :=w
• 반환 m

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(사다리, 뱀):사다리.extend(뱀) edge ={} for f,t in 사다리:edge[f] =t u =set() v =set() v.add(1) m =0 동안 100은 v에 없음:m +=1 w =set() for f in v:for i in range(1,7):n =f + i if n in edge:n =edge[n] if n u에서:계속 u.add(n) w.add(n) v =w return mprint(solve([(11, 40), (37,67),(47, 73),(15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]))

입력

출력

8