I know that we can brute force it by placing an obstacle at every valid position in the path, but is there a more elegant / efficient solution?

  • lwhjp
    1•5 days ago

    You gave me an idea!

    • Give each obstacle in the initial map an ID, and build three indexes by ID, by row, and by column.
    • Use the list of obstacles to build up a map from (ID, direction) to (next ID, direction) (if any) – that is, for each obstacle, update the map entry for any preceding obstacle that could reach it.
    • This map can be used to compute the path very cheaply.
    • And crucially, you can easily update the map for new obstacles using the same method above.

    I think this would give a pretty good speed up, and you might not need to worry about only checking intersections.