The problem in question is Hamiltonian wall and I wrote a solution to this that works, but I suspect that it is the wrong solution. My solution is this. The reason I suspect that my solution is incorrect is because, if in the DFS function I change the order of the two loops, I get the wrong answer(when that should not be happening). I would really appreciate if anybody could point out what is wrong with DFS function.
Thanks, if you need any clarification regarding some of the terms in my template or regarding my approach, feel free to comment down below EDIT: I removed the lengthy template
If you remove the lengthy prefix from your code, more people will be willing to help you.
sure
Auto comment: topic has been updated by Flvx (previous revision, new revision, compare).
It's actually a correct solution.
You have realized the problem in your second submission: the "erase" missing. But the time complexity of dfs is to large for this problem, so you get TLE.
Then, without the erase, your dfs is actually a greedy, because it will never try another route. The strategy of your code is: if going up/down is possible, then go up/down, else go right.
This greedy is (accidentially) correct. I can't show the proof, but try to draw a few examples out and you will understand.
Oh, I did not expect that, ok, thank you :)