How to solve this

#1

sir , not getting how to do this . I request you to provide me the approach and code for this question

#2

To Solve any Problem related to Recursion All you need to do is Break the Problem into 3 important components which are as follows :-

  1. Bigger Problem : The original Problem statement is your bigger problem.
  2. Smaller Problem : In every recursive prblm there exist a prblm statement which you need to achieve in order to fullfill the prblm statement but by considering such a smaller prblm from the bigger prblm is needed which we need to assume that the recursion will work and will give the answer.
  3. Self Work : The amount of work which one should do in order to make the smaller problem your problem.

For e.gā€¦, In order to find the max of any array, three components will be :-
Bigger Problem : To find the max in whole array viz find max in array from index 0 to n - 1.
Smaller Problem : Assume that the recursion works and will find the max of array from index 1 to n - 1.
__Self Work : In order to make your smaller prblm your bigger prblm all you need to do is to compare the ans return by assuming the smaller prblm works with the 0th index element and return the max among both of them.

Similarly Classification acc to the Given prblm :-

  • Bigger Problem : To find any path available from [0, 0] to [N - 1, N - 1].
  • Smaller Problem : Assume the recursion works and will give you ans whether any path exist for positions [cr, cc + 1] to [N - 1, N - 1] or [cr, cc - 1] to [N - 1, N - 1] or [cr - 1, cc] to [N - 1, N - 1] or [cr + 1, cc] to [N - 1, N - 1].
    Self Work : In order to make you smaller prblm your problem all you need to work for the current position by giving 4 calls to these positions.

Note:

  • In order to make sure you donot caught up in infinite recursion by giving 4 calls to every position without checking if we have explored that particular position or not other our recursion will caught up in infnite recursion, we will use a visited boolean 2D array that will account for the position that has been explored.
  • Also we need to backtrack and undo the visited block as we return from the position.
  • Use either by returning true if found solution or declare a global variable in order to check if you have found a path or not.

you can see this: