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?
I am using same solution, and getting right count with test input, but the actual input gives too many.
Annoying, and really hard to debug. I made renderer to visualize, but unable to find the bug.
One misunderstanding was that I counted same walls twice, because the result should not count same added wall twice if it has same x,y.
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.