Closed ChrisVilches closed 1 year ago
What to do:
Either comment the source code and indicate that it's deprecated and doesn't work.
Or, fix the code so that it works!
Commented here: https://github.com/ChrisVilches/Algorithms/commit/f0add904b8f0002879ddb95ab6e5fa6913acc7bb
I won't fix the code, but I commented the source. The program still gets AC so I'll just leave it there.
These two cases. The first one is OK, but the second one fails.
The correct answer should be (obtained using Dijkstra's algorithm):
(These correct answers were confirmed using multiple solutions from Aizu judge)
But the backtracking implementation returns the following results:
The cause: The backtracking algorithm incorrectly assumes that every pole is visited at most once, but this case actually needs a second visit in order to get to the goal. It seems that in the official test data (100 cases in total) this never happened, so it gets accepted anyway.