please check where the code is wrong
dont pass any test case
Dfs not working
Gagan u r using recursion in dfs and there is no base condition thats why run error will come and also u have to backtrack the path
just make
Also make ur dfs func bool type
base condition : if(i==n && j==n) return
the visit the block x,y if it is safe to visit then visited of x,y =true
make these changes
Hi there,
I am not getting run-time error , but instead WRONG ANSWER .
Moreover, no base condition in DFS allows to explore all possible paths and isValid() function would stop function from going into infinite loop.
Using DFS I explore all the paths possible , then is there a need for backtracking ?
I do a DFS from a node to each and every path which can be visited from that node and that path is only VALID CELLS(refer isValid() for same ).
After DFS I count which were the cells which were valid but was not visited during DFS.
This would be my answer.Why shall I make it a bool type ? I am just doing DFS , to explore all possible paths , so what is the use of bool return type.
I though changed it as you suggested , still getting WRONG ANSWER.
Please go-to through code once again and suggest any changes if any.
Thanks
yes there is a need of backtracking
look there are many possibilities to visit a particuar cell and u have to find the best possibility so that unvisited one will minimize
for eg: if u goto a cell from where all possibility to move are visited one and on the other side there are many unvisited one so u have to change ur path which is only done by backtrack
Also in ur valid one function remove chess[nx][ny] condition as the horse can move upto border
(Read in question)
Hey Gagan,
As you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required.
Please mark your doubts as resolved in your course’s “ Ask Doubt ” section, when your doubt is resolved.