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?
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?
Yeah something like that happend for me too, and later I counted too little because it would not recognise some possible solutions. Finally I solved it by just walking along the path and at each location put an obstacle in front of it and then check if the changed map results in a path enters longer than 10000 steps. Not pretty but at least it lead to the right result with a runtime of ~3 seconds. I would have saved a lot of time if I had tried the “brute force” way before, so I guess lesson learned.
You can track by just keeping list of all positions and movement direction, if two are same, it means that it is in a loop.