2 test cases not passing for funky chessboad problem

#1

Used dfs approach

#2

Hi Dhiraj,
The problem is that you are not using backtracking and considering the mixture of all possible moves of the knights all together …we have to consider each path of it and count of the number of cells visited in that path and minimise that number. Your code simply counts the number of all the possible cells that the knight can reach in total.

That is ,you have find one path where the knight can cover the maximum no of cells and your knight has to stick to it without going back.

Here’s a testcase for you to understand

Input :
4
1 0 1 0
0 0 1 0
1 1 0 1
0 0 0 0

Expected Output : 2
Your Output : 0
Explanation : There are only two possible paths for the knight to traverse without going back .
( I am using 0 based indexing here )
Path 1 : (0,0) -> (2,1) -> (0,2) -> (2,3)
Path 2 : (0,0) -> (1,2) -> (2,0)

Clearly we would prefer Path 1 as it covers more nodes.
The no of nodes left out in path 1 were 2 and nodes left out in path 2 were 3.
Final answer will be 2 as Path 1 is the better one.
Hope this helps.

Here’s another testcase for you to try when you update your code.

Input :
10
1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 1 1 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1

Expected Output : 17

#3


i could do this still not able to to backtrack

#4

@tarunluthra…

#5

Simple backtracking in your code would give an infinite loop. Basically we need to backtrack to mark the cell as unvisited after we explore all paths from it.
Please refer to my code to get the idea.
Code - https://ide.codingblocks.com/s/97840

#6

please see my code I guess I am backtracking the wrong way I am not getting the second path in that 4 wala testcase please rectify my code so that I can understand better I used dfs along with bckctrack

#7

@tarunluthra …

#8

Hi Dhiraj ,
This problem is not a DFS problem. DFS algorithm picks a branch and sticks to it and does not deviate. Even if you backtrack , you cannot assure that the next time your code would pick a new branch at all. We need to consider the possibility of all branches at all nodes starting from (0,0). DFS Algo won’t work for this problem.
That is why I shared my code with you so you can understand the correct approach.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.