タイトルの概要#
跳蚤の家の位置 x は数軸上にあります。あなたは、位置 0 から出発して家に到着するのを助ける必要があります。
跳蚤のジャンプのルールは次のとおりです：
正確に a の位置（つまり右に）ジャンプすることができます。
正確に b の位置（つまり左に）ジャンプすることができます。
連続して 2 回後ろにジャンプすることはできません。
ジャンプできない位置にジャンプすることはできません。
跳蚤は家の位置よりも前にジャンプすることができますが、負の整数の位置にジャンプすることはできません。
禁止された配列が与えられるので、禁止された位置にジャンプしないように注意しながら、整数 a、b、x が与えられた場合、跳蚤が家に到着するために必要な最小のジャンプ回数を返してください。x に到達する正確な解決策がない場合は、-1 を返してください。
実行例#
例 1#
入力：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
出力：3
説明：3回前にジャンプすると（0 -> 3 -> 6 -> 9）、跳蚤は家に到着します。
例 2#
入力：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
出力：-1
例 3#
入力：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
出力：2
説明：1回前にジャンプする（0 -> 16）、そして1回後ろにジャンプする（16 -> 7）、跳蚤は家に到着します。
ヒント#
1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
forbidden のすべての位置は互いに異なります。
位置 x は forbidden に含まれていません。
解決策のアイデア#
問題の説明に基づいて、まず forbidden 配列を走査し、ジャンプルールに合わない位置をすべて記録しておきます。次に、ジャンプルールと跳蚤の家の位置 x に基づいて、0 からジャンプして最小の回数を計算してみます。具体的なアイデアは以下の通りです：
forbidden 配列を走査し、ジャンプルールに合わない位置を記録します。
forbidden 配列を走査し、ジャンプルールに合わない位置を前に押し出す距離を記録します。
位置ごとに forbidden 配列を走査し、ジャンプルールに合致するかどうかを判断します。ジャンプルールに合致する場合、跳蚤が到達する最小の回数を計算できます。ジャンプルールに合致しない場合、ジャンプ回数を計算する必要はありません。
ジャンプルールに合わない位置を前に押し出す距離と跳蚤が到達する最小の回数を答えとして返します。
コードの例#
class Solution:
def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
if x==0: return 0
if x%math.gcd(a,b): return -1
fb = set(forbidden)
que = {(0,1)}
visited = {(0,1)}
step = 1
mx = max(max(fb)+a+b,x+b)
while que:
que1 = set()
for pos,back in que:
pos1 = pos+a
pos2 = pos-b
if pos1==x or (back==0 and pos2==x): return step
if pos1<=mx and pos1 not in fb and (pos1,0) not in visited:
visited.add((pos1,0))
que1.add((pos1,0))
if back==0 and pos2>=0 and pos2 not in fb and (pos2,1) not in visited:
visited.add((pos2,1))
que1.add((pos2,1))
que = que1
step+=1
return -1