fork download
  1. def minimum_moves(n, instructions):
  2. # Define the four tiles
  3. tiles = ["up", "down", "right", "left"]
  4.  
  5. # Initialize a dictionary to store the minimum moves required to each position
  6. dp = {tile: float("inf") for tile in tiles}
  7.  
  8. # Start with any position (0 moves initially)
  9. for tile in tiles:
  10. dp[tile] = 0
  11.  
  12. for instr in instructions:
  13. new_dp = {tile: float("inf") for tile in tiles}
  14. for current_tile in tiles:
  15. for target_tile in tiles:
  16. # If same tile, no movement needed; otherwise, 1 move
  17. cost = 0 if current_tile == target_tile else 1
  18. new_dp[target_tile] = min(new_dp[target_tile], dp[current_tile] + cost)
  19. dp = new_dp
  20.  
  21. # Find the minimum moves among all final positions
  22. return min(dp.values())
  23.  
  24. # Input
  25. n = int(input())
  26. instructions = [input().strip() for _ in range(n)]
  27.  
  28. # Output
  29. print(minimum_moves(n, instructions))
Success #stdin #stdout 0.05s 9892KB
stdin
6
down
right
down
up
right
down
stdout
0