네 개의 값 n, x, y 및 k가 있다고 가정합니다. 여기서 n은 n x n 체스판을 나타내고 x, y 좌표는 기사가 (x, y)에 배치되어 있음을 나타냅니다. 기사는 정확히 k 단계를 거쳐야 하며 각 단계에서 무작위로 균일하게 8방향을 이동할 수 있습니다. 기사가 k 이동 후 체스판에 남아 있을 확률(가장 가까운 정수)을 찾아야 합니다. 보드를 떠난 후에는 다시 들어갈 수 없다는 조건을 따라야 합니다.
따라서 입력이 n =8, (x =0, y =0), k =1과 같으면 출력은 50이 됩니다. 여기에는 8x8 체스판이 있고 기사의 초기 위치는 (1, 1 ). k =1 단계가 걸릴 수 있습니다. 한 걸음 내딛으면 8개 위치 중 4개 위치에서만 보드 내부에 놓이고 다른 위치에서는 외부에 놓입니다. 50%입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 움직임 목록 만들기 [(1, 2) ,(1, -2) ,(-1, 2) ,(-1, -2) ,(2, 1) ,(2, -1) , (-2, 1) ,(-2, -1) ]
- dfs() 함수를 정의합니다. x, y, k 가 필요합니다.
- (x, y)가 보드 범위에 없으면
- 0을 반환
- k가 0과 같으면
- 1을 반환
- =빈 목록
- 동작의 모든 동작(dx, dy)에 대해 -
- x =dfs(x + dx, y + dy, k - 1) / 8
- s에 x 삽입
- s에 있는 요소의 합계를 반환
- 메인 방법에서 다음을 수행하십시오 -
- (dfs(x, y, k) * 100)의 반올림된 결과를 가장 가까운 정수로 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
moves = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)] class Solution: def solve(self, n, x, y, k): def dfs(x, y, k): if x < 0 or y < 0 or x >= n or y >= n: return 0 if k == 0: return 1 return sum(dfs(x + dx, y + dy, k - 1) / 8 for dx, dy in moves) return int(dfs(x, y, k) * 100) ob = Solution() n = 8 x = 1 y = 1 k = 1 print(ob.solve(n, x, y, k))
입력
8, 1, 1, 1
출력
0