https://leetcode.com/problems/race-car/description/

818.race_car.py

class Solution(object):
    def racecar(self, target):
        """
        :type target: int
        :rtype: int
        """
        curstep = set([])
        curstep.add((0,1))
        allstep = set([])
        allstep.add((0,1))
        
        t = 0 
        while curstep:
            t += 1
            nxtstep = set([])
            for (p,s) in curstep:
                np = p + s 
                if abs(np) <= target * 2:
                    if np == target:
                        return t 
                    ns = s*2
                    if (np, ns) in allstep:
                        continue 
                    nxtstep.add((np, ns))
                    allstep.add((np, ns))
                np = p 
                if s > 0:
                    ns = -1
                else:
                    ns = 1
                if (np, ns) in allstep:
                    continue 
                nxtstep.add((np, ns))
                allstep.add((np, ns))
            
            curstep = nxtstep 
        return -1