Flvx's blog

By Flvx, history, 12 months ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Oh, I did not expect that, ok, thank you :)