Minimum number of moves to jump from start to end?

Revision en2, by Ahmad, 2017-02-05 21:52:55

Let's say you're given a string where the start point is the beginning of the string and the end point is the end of the string. For each turn, you can jump at most s positions in the string but there are obstacles in the string which you are not allowed to land on.

So for example a string like "SOOOXOE" (where "O" represents a free space and "X" represents an obstacle) and there's an s value of 3. The minimum number of moves in this case to get from S to E is 2. But in a case like "SOOOXXOE" with the same s value, the minimum number of moves is 3.

I came up with a greedy where you jump as far as possible as long as it's valid position each turn and it works. But I need to calculate the minimum number where the difference between S and E is at most 1,000,000,000 so simulating the jumping is too slow. Does anyone have any ideas about how to solve this efficiently?

*Note that I'm not actually given a string of length 1,000,000,000 but I visualized it as a string so it's easier to understand. Also if it helps, there will be at most 40 obstacles per string and s is always greater than 1 and less than or equal to 6. It is always possible to reach E from S.

Tags help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Ahmad 2017-02-05 21:52:55 41 Tiny change: 'qual to 6.' -> 'qual to 6. It is always possible to reach E from S.'
en1 English Ahmad 2017-02-05 21:48:46 1195 Initial revision (published)