I think reflecting after solving is important.
Find the shortest path from the start position to the goal position on a 2D plane. However, there are some blocks on the plane, and those cells cannot be passed through. Furthermore, in one move, you can advance an arbitrary number of cells from $1 … K$ in the same direction.
Consider the graph with vertices as $(y, x, dir)$ and calculate the shortest path using Dijkstra’s algorithm. Transitions from vertex $(y, x, dir)$ are as follows. It’s good to multiply the movement cost by $K$.
- When changing direction, round up with $K$.
- $cost(y, x, new dir) \leftarrow ((cost(y, x, dir) + K -1) / K) * K$
- Move in the same direction. $dir$ has 4 types: up, down, left, right. $dx$, $dy$ are differences for each direction.
- $cost(y + dy, x + dx, dir) \leftarrow cost(y, x, dir) + 1$
The computational complexity is probably $O(HW log(HW))$.
