1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution(object):
def canCross(self, stones):
"""
:type stones: List[int]
:rtype bool
"""
self.memo = set()
target = stones[-1]
stones = set(stones)
ans = self.bt(stones, 1, 1, target)
return ans
def bt(self, stones, curr, speed, target):
if (curr, speed) in self.memo:
return False
if curr == target:
return True
if curr > target or curr < 0 or speed <= 0 or curr not in stones:
return False
candidate = [speed - 1, speed, speed + 1]
for c in candidate:
if (curr + c) in stones:
if self.bt(stones, curr + c, c, target):
return True
self.memo.add((curr, speed))
return False
if __name__ == "__main__":
obj = Solution()
print(obj.canCross([0,1,3,5,6,8,12,17])) # expect: True
print(obj.canCross([0,1,2,3,4,8,9,11])) # expect: False
|