금지된 배열이 있다고 가정합니다. 여기서 금지된[i]는 버그가 금지된 위치[i]로 이동할 수 없음을 나타내고 우리는 또한 세 개의 값, b 및 x를 가지고 있습니다. 벌레의 집은 숫자 라인의 x 위치에 있습니다. 처음에는 위치 0에 있습니다. 다음 규칙에 따라 점프할 수 있습니다 -
-
버그는 정확히 오른쪽 위치로 이동할 수 있습니다.
-
버그는 왼쪽으로 정확히 b 위치로 이동할 수 있습니다.
-
버그는 뒤로 두 번 연속으로 점프할 수 없습니다.
-
버그는 배열에 지정된 금지된 위치로 이동할 수 없습니다.
-
버그는 집 너머로 앞으로 이동할 수 있지만 음수 값으로 번호가 매겨진 위치로 이동할 수는 없습니다.
버그가 목적지에 도달하는 데 필요한 최소 점프 수를 찾아야 합니다. 가능한 시퀀스가 없으면 -1을 반환합니다.
따라서 입력이 금지 =[2,3,7,9, 12], a =4, b =2, x =16인 경우 출력은 0에서 시작하여 a =4 앞으로 점프하기 때문에 7이 됩니다. 4와 8에 도달하기 위해 두 번, 그러나 이것이 금지되어 12로 점프할 수 없습니다. 그런 다음 6에서 b =2로 뒤로 물러난 다음 10, 14, 18로 점프한 다음 2를 뒤로 이동하여 16에 도달하므로 7개의 단계가 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
queue :=튜플(x,0,True)이 있는 큐, 금지됨 :=금지된 목록에서 새 집합 및 삽입 요소
-
lim :=a + b + (x의 최대값과 금지된 집합의 최대값)
-
대기열이 비어 있지 않은 동안 수행
-
(curr,jumps,is_b) :=대기열에서 첫 번째 요소 및 대기열에서 제거
-
curr이 금지되어 있거나 (0 <=curr <=lim)이 거짓이면
-
다음 반복으로 이동
-
-
금지된 곳에 curr 삽입
-
curr이 0과 같으면
-
리턴 점프
-
-
is_b가 참이면
-
대기열에 (curr+b, jumps+1,False) 삽입
-
-
대기열에 (curr-a, jumps+1,True) 삽입
-
-
반환 -1
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(forbidden, a, b, x):
queue, forbidden = [(x,0,True)], set(forbidden)
lim = max(max(forbidden),x)+a+b
while queue:
curr,jumps,is_b = queue.pop(0)
if curr in forbidden or not 0 <= curr <= lim:
continue
forbidden.add(curr)
if curr==0:
return jumps
if is_b:
queue.append((curr+b,jumps+1,False))
queue.append((curr-a,jumps+1,True))
return -1
forbidden = [2,3,7,9, 12]
a = 4
b = 2
x = 16
print(solve(forbidden, a, b, x)) 입력
[2,3,7,9, 12], 4, 2, 16
출력
7