It’s solution can be done using Backtracking easily. How to do it via linked list as the question is given under LL challenges?
Rat chases its cheese
HI @vivek21,
It is a backtracking question . There is no as such linked list based solution .Try solving it using backtracking only.
Please check this code. 1 testcase failed out of 5
You need to add a counter in this code which restricts going up if you just moved down so as to avoid the infinite loop of moving up and down . So for that i have added a turn counter in your code … Check for the comment .
To deal with that, I had already applied these type of conditions.
that if left is 1 then don’t go left, up is 1, then don’t go up, etc.
And also in case of infinite loop, it should give me timelimit or run-error, but its giving wrong answer, that means that program is getting executed within bound time.
This is your output of code you sent
1 1 0 0 0
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
while the correct output is this
1 0 0 0 0
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
This line of code you used to check does not backtrack and also is not sufficient. That’s why you are getting wrong error and not time limit or run-erro . And sorry i cannot reveal the testcase so please don’t ask but your algorithm was a bit incorrect and i corrected it with a small change.
And regarding your condition ->“if left is 1 then don’t go left, up is 1, then don’t go up, etc.” Here the problem is if you go left and feel that it is not the right path then you go right to check and if you feel right is not a correct path then in that case you must not have a option of going left again cause it will have a infinite loop . That’s what i meant not what you did with those conditions.
See this updated code. line number 72.
I made just a small change in main function after debugging the problem in eclipse and all 5 testcases passed. Hurray!!!
I debugged the following case to find out the problem :
Thanks
Great … Happy to help …