파이썬에서 체스 기사가 목표 위치에 도달하기 위한 최소 단계를 찾는 프로그램

<시간/>

두 개의 값 r과 c가 있다고 가정합니다. 체스 기사가 무한히 큰 체스 판의 시작 부분에 좌표 (0, 0)에 배치되면 위치 (r, c)에 도달하는 데 필요한 최소 이동 수를 찾아야 합니다. 기사는 체스와 같은 이동 스타일을 따릅니다. 가로로 2칸, 세로로 1칸, 세로로 2칸, 가로로 1칸 이동합니다.

따라서 입력이 r =6, c =1과 같으면 출력은 3이 되고 빨간색은 초기 위치, 녹색은 최종 단계, 노란색은 중간 단계가 됩니다.

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

r
r과 c 교체

(r, c)가 (1, 0)과 같으면

3 반환

(r, c)가 (2, 2)와 같으면

4 반환

델타 :=r - c

c> 델타이면

반환 델타 - 2 *((델타 - c) / 3의 몫)

그렇지 않으면

반환 델타 - 2 *((델타 - c) / 4의 몫)

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

예시

class Solution:
   def solve(self, r, c):
      if r < c:
         r, c = c, r
      if (r, c) == (1, 0):
         return 3
      if (r, c) == (2, 2):
         return 4
      delta = r - c
      if c > delta:
         return delta - 2 * ((delta - c) // 3)
      else:
         return delta - 2 * ((delta - c) // 4)
ob = Solution()
r = 6
c = 1
print(ob.solve(r, c))

입력

6, 1