aboutsummaryrefslogtreecommitdiff
path: root/minimum_sideways_jumps.py
blob: 01e1cd6379a1bdfe2161c7943b00d4366c16f39f (plain)
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
32
33
34
35
36
37
# 1824. Minimum Sideway Jumps

"""
there is a 3 lane road of length 'n' that consists of 'n + 1' points labeled
from 0 to 'n'. a frog starts at point 0 in the second lane and wants to jump
to point 'n'. however there could be obstacles along the way. you are given
an array 'obstacles' of length 'n + 1' where each 'obstacles[i]' (ranging
from 0 to 3) describes an obstacle on the lane 'obstacles[i]' at point 'i'.
if 'obstacles[i] == 0' there are no obstacles at point 'i'. there will be at
most one obstacles in the 3 lanes at each point. the frog can only travel
from point 'i' to point 'i + 1' on the same lane if there is not an obstacle
on the lane at point 'i + 1'. return the minimum number of side jumps the
frog needs to reach any lane at point 'n' starting from lane 2 at point 0.
"""


class Solution(object):
    def minSideJumps(self, obstacles):
        """
        :type obstacles: List[int]
        :rtype: int
        """
        dp = [1, 0, 1]
        for i in obstacles:
            if i:
                dp[i - 1] = float("inf")
            for j in range(3):
                if i != j + 1:
                    dp[j] = min(dp[j], dp[(j + 1) % 3] + 1, dp[(j + 2) % 3] + 1)
        return min(dp)


if __name__ == "__main__":
    obj = Solution()
    print(obj.minSideJumps(obstacles=[0, 1, 2, 3, 0]))
    print(obj.minSideJumps(obstacles=[0, 1, 1, 3, 3, 0]))
    print(obj.minSideJumps(obstacles=[0, 2, 1, 0, 3, 0]))