#include          #include         #include         #include          using     namespace     std  ;   // Function to find the longest path using backtracking   int     dfs  (  vector   <  vector   <  int  >>     &  mat           vector   <  vector   <  bool  >>     &  visited       int     i           int     j       int     x       int     y  )     {      int     m     =     mat  .  size  ();      int     n     =     mat  [  0  ].  size  ();          // If destination is reached      if     (  i     ==     x     &&     j     ==     y  )     {      return     0  ;      }          // If cell is invalid blocked or already visited      if     (  i      <     0     ||     i     >=     m     ||     j      <     0     ||     j     >=     n     ||         mat  [  i  ][  j  ]     ==     0     ||     visited  [  i  ][  j  ])     {      return     -1  ;         }          // Mark current cell as visited      visited  [  i  ][  j  ]     =     true  ;          int     maxPath     =     -1  ;          // Four possible moves: up down left right      int     row  []     =     {  -1       1       0       0  };      int     col  []     =     {  0       0       -1       1  };          for     (  int     k     =     0  ;     k      <     4  ;     k  ++  )     {      int     ni     =     i     +     row  [  k  ];      int     nj     =     j     +     col  [  k  ];          int     pathLength     =     dfs  (  mat       visited           ni       nj       x       y  );          // If a valid path is found from this direction      if     (  pathLength     !=     -1  )     {      maxPath     =     max  (  maxPath       1     +     pathLength  );      }      }          // Backtrack - unmark current cell      visited  [  i  ][  j  ]     =     false  ;          return     maxPath  ;   }   int     findLongestPath  (  vector   <  vector   <  int  >>     &  mat           int     xs       int     ys       int     xd       int     yd  )     {      int     m     =     mat  .  size  ();      int     n     =     mat  [  0  ].  size  ();          // Check if source or destination is blocked      if     (  mat  [  xs  ][  ys  ]     ==     0     ||     mat  [  xd  ][  yd  ]     ==     0  )     {      return     -1  ;      }          vector   <  vector   <  bool  >>     visited  (  m       vector   <  bool  >  (  n       false  ));      return     dfs  (  mat       visited       xs       ys       xd       yd  );   }   int     main  ()     {      vector   <  vector   <  int  >>     mat     =     {      {  1       1       1       1       1       1       1       1       1       1  }      {  1       1       0       1       1       0       1       1       0       1  }      {  1       1       1       1       1       1       1       1       1       1  }      };          int     xs     =     0       ys     =     0  ;         int     xd     =     1       yd     =     7  ;             int     result     =     findLongestPath  (  mat       xs       ys       xd       yd  );          if     (  result     !=     -1  )      cout      < <     result      < <     endl  ;      else      cout      < <     -1      < <     endl  ;          return     0  ;   }   

   import     java.util.Arrays  ;   public     class   GFG     {          // Function to find the longest path using backtracking      public     static     int     dfs  (  int  [][]     mat       boolean  [][]     visited        int     i       int     j       int     x       int     y  )     {      int     m     =     mat  .  length  ;      int     n     =     mat  [  0  ]  .  length  ;          // If destination is reached      if     (  i     ==     x     &&     j     ==     y  )     {      return     0  ;      }          // If cell is invalid blocked or already visited      if     (  i      <     0     ||     i     >=     m     ||     j      <     0     ||     j     >=     n     ||     mat  [  i  ][  j  ]     ==     0     ||     visited  [  i  ][  j  ]  )     {      return     -  1  ;     // Invalid path      }          // Mark current cell as visited      visited  [  i  ][  j  ]     =     true  ;          int     maxPath     =     -  1  ;          // Four possible moves: up down left right      int  []     row     =     {  -  1       1       0       0  };      int  []     col     =     {  0       0       -  1       1  };          for     (  int     k     =     0  ;     k      <     4  ;     k  ++  )     {      int     ni     =     i     +     row  [  k  ]  ;      int     nj     =     j     +     col  [  k  ]  ;          int     pathLength     =     dfs  (  mat       visited       ni       nj       x       y  );          // If a valid path is found from this direction      if     (  pathLength     !=     -  1  )     {      maxPath     =     Math  .  max  (  maxPath       1     +     pathLength  );      }      }          // Backtrack - unmark current cell      visited  [  i  ][  j  ]     =     false  ;          return     maxPath  ;      }          public     static     int     findLongestPath  (  int  [][]     mat       int     xs       int     ys       int     xd       int     yd  )     {      int     m     =     mat  .  length  ;      int     n     =     mat  [  0  ]  .  length  ;          // Check if source or destination is blocked      if     (  mat  [  xs  ][  ys  ]     ==     0     ||     mat  [  xd  ][  yd  ]     ==     0  )     {      return     -  1  ;      }          boolean  [][]     visited     =     new     boolean  [  m  ][  n  ]  ;      return     dfs  (  mat       visited       xs       ys       xd       yd  );      }          public     static     void     main  (  String  []     args  )     {      int  [][]     mat     =     {      {  1       1       1       1       1       1       1       1       1       1  }      {  1       1       0       1       1       0       1       1       0       1  }      {  1       1       1       1       1       1       1       1       1       1  }      };          int     xs     =     0       ys     =     0  ;      int     xd     =     1       yd     =     7  ;          int     result     =     findLongestPath  (  mat       xs       ys       xd       yd  );          if     (  result     !=     -  1  )      System  .  out  .  println  (  result  );      else      System  .  out  .  println  (  -  1  );      }   }   

   # Function to find the longest path using backtracking   def   dfs  (  mat     visited     i     j     x     y  ):   m   =   len  (  mat  )   n   =   len  (  mat  [  0  ])   # If destination is reached   if   i   ==   x   and   j   ==   y  :   return   0   # If cell is invalid blocked or already visited   if   i    <   0   or   i   >=   m   or   j    <   0   or   j   >=   n   or   mat  [  i  ][  j  ]   ==   0   or   visited  [  i  ][  j  ]:   return   -  1   # Invalid path   # Mark current cell as visited   visited  [  i  ][  j  ]   =   True   maxPath   =   -  1   # Four possible moves: up down left right   row   =   [  -  1     1     0     0  ]   col   =   [  0     0     -  1     1  ]   for   k   in   range  (  4  ):   ni   =   i   +   row  [  k  ]   nj   =   j   +   col  [  k  ]   pathLength   =   dfs  (  mat     visited     ni     nj     x     y  )   # If a valid path is found from this direction   if   pathLength   !=   -  1  :   maxPath   =   max  (  maxPath     1   +   pathLength  )   # Backtrack - unmark current cell   visited  [  i  ][  j  ]   =   False   return   maxPath   def   findLongestPath  (  mat     xs     ys     xd     yd  ):   m   =   len  (  mat  )   n   =   len  (  mat  [  0  ])   # Check if source or destination is blocked   if   mat  [  xs  ][  ys  ]   ==   0   or   mat  [  xd  ][  yd  ]   ==   0  :   return   -  1   visited   =   [[  False   for   _   in   range  (  n  )]   for   _   in   range  (  m  )]   return   dfs  (  mat     visited     xs     ys     xd     yd  )   def   main  ():   mat   =   [   [  1     1     1     1     1     1     1     1     1     1  ]   [  1     1     0     1     1     0     1     1     0     1  ]   [  1     1     1     1     1     1     1     1     1     1  ]   ]   xs     ys   =   0     0   xd     yd   =   1     7   result   =   findLongestPath  (  mat     xs     ys     xd     yd  )   if   result   !=   -  1  :   print  (  result  )   else  :   print  (  -  1  )   if   __name__   ==   '__main__'  :   main  ()   

   using     System  ;   class     GFG   {      // Function to find the longest path using backtracking      static     int     dfs  (  int  []     mat       bool  []     visited           int     i       int     j       int     x       int     y  )      {      int     m     =     mat  .  GetLength  (  0  );      int     n     =     mat  .  GetLength  (  1  );          // If destination is reached      if     (  i     ==     x     &&     j     ==     y  )      {      return     0  ;      }          // If cell is invalid blocked or already visited      if     (  i      <     0     ||     i     >=     m     ||     j      <     0     ||     j     >=     n     ||     mat  [  i       j  ]     ==     0     ||     visited  [  i       j  ])      {      return     -  1  ;     // Invalid path      }          // Mark current cell as visited      visited  [  i       j  ]     =     true  ;          int     maxPath     =     -  1  ;          // Four possible moves: up down left right      int  []     row     =     {  -  1       1       0       0  };      int  []     col     =     {  0       0       -  1       1  };          for     (  int     k     =     0  ;     k      <     4  ;     k  ++  )      {      int     ni     =     i     +     row  [  k  ];      int     nj     =     j     +     col  [  k  ];          int     pathLength     =     dfs  (  mat       visited       ni       nj       x       y  );          // If a valid path is found from this direction      if     (  pathLength     !=     -  1  )      {      maxPath     =     Math  .  Max  (  maxPath       1     +     pathLength  );      }      }          // Backtrack - unmark current cell      visited  [  i       j  ]     =     false  ;          return     maxPath  ;      }          static     int     FindLongestPath  (  int  []     mat       int     xs       int     ys       int     xd       int     yd  )      {      int     m     =     mat  .  GetLength  (  0  );      int     n     =     mat  .  GetLength  (  1  );          // Check if source or destination is blocked      if     (  mat  [  xs       ys  ]     ==     0     ||     mat  [  xd       yd  ]     ==     0  )      {      return     -  1  ;      }          bool  []     visited     =     new     bool  [  m       n  ];      return     dfs  (  mat       visited       xs       ys       xd       yd  );      }          static     void     Main  ()      {      int  []     mat     =     {      {  1       1       1       1       1       1       1       1       1       1  }      {  1       1       0       1       1       0       1       1       0       1  }      {  1       1       1       1       1       1       1       1       1       1  }      };          int     xs     =     0       ys     =     0  ;         int     xd     =     1       yd     =     7  ;             int     result     =     FindLongestPath  (  mat       xs       ys       xd       yd  );          if     (  result     !=     -  1  )      Console  .  WriteLine  (  result  );      else      Console  .  WriteLine  (  -  1  );      }   }   

   // Function to find the longest path using backtracking   function     dfs  (  mat       visited       i       j       x       y  )     {      const     m     =     mat  .  length  ;      const     n     =     mat  [  0  ].  length  ;          // If destination is reached      if     (  i     ===     x     &&     j     ===     y  )     {      return     0  ;      }          // If cell is invalid blocked or already visited      if     (  i      <     0     ||     i     >=     m     ||     j      <     0     ||     j     >=     n     ||         mat  [  i  ][  j  ]     ===     0     ||     visited  [  i  ][  j  ])     {      return     -  1  ;         }          // Mark current cell as visited      visited  [  i  ][  j  ]     =     true  ;          let     maxPath     =     -  1  ;          // Four possible moves: up down left right      const     row     =     [  -  1       1       0       0  ];      const     col     =     [  0       0       -  1       1  ];          for     (  let     k     =     0  ;     k      <     4  ;     k  ++  )     {      const     ni     =     i     +     row  [  k  ];      const     nj     =     j     +     col  [  k  ];          const     pathLength     =     dfs  (  mat       visited           ni       nj       x       y  );          // If a valid path is found from this direction      if     (  pathLength     !==     -  1  )     {      maxPath     =     Math  .  max  (  maxPath       1     +     pathLength  );      }      }          // Backtrack - unmark current cell      visited  [  i  ][  j  ]     =     false  ;          return     maxPath  ;   }   function     findLongestPath  (  mat       xs       ys       xd       yd  )     {      const     m     =     mat  .  length  ;      const     n     =     mat  [  0  ].  length  ;          // Check if source or destination is blocked      if     (  mat  [  xs  ][  ys  ]     ===     0     ||     mat  [  xd  ][  yd  ]     ===     0  )     {      return     -  1  ;      }          const     visited     =     Array  (  m  ).  fill  ().  map  (()     =>     Array  (  n  ).  fill  (  false  ));      return     dfs  (  mat       visited       xs       ys       xd       yd  );   }      const     mat     =     [      [  1       1       1       1       1       1       1       1       1       1  ]      [  1       1       0       1       1       0       1       1       0       1  ]      [  1       1       1       1       1       1       1       1       1       1  ]      ];          const     xs     =     0       ys     =     0  ;         const     xd     =     1       yd     =     7  ;             const     result     =     findLongestPath  (  mat       xs       ys       xd       yd  );          if     (  result     !==     -  1  )      console  .  log  (  result  );      else      console  .  log  (  -  1  );   

   #include          #include         #include         #include          using     namespace     std  ;   // Function to find the longest path using backtracking without extra space   int     dfs  (  vector   <  vector   <  int  >>     &  mat       int     i       int     j       int     x       int     y  )     {      int     m     =     mat  .  size  ();      int     n     =     mat  [  0  ].  size  ();          // If destination is reached      if     (  i     ==     x     &&     j     ==     y  )     {      return     0  ;      }          // If cell is invalid or blocked (0 means blocked or visited)      if     (  i      <     0     ||     i     >=     m     ||     j      <     0     ||     j     >=     n     ||     mat  [  i  ][  j  ]     ==     0  )     {      return     -1  ;         }          // Mark current cell as visited by temporarily setting it to 0      mat  [  i  ][  j  ]     =     0  ;          int     maxPath     =     -1  ;          // Four possible moves: up down left right      int     row  []     =     {  -1       1       0       0  };      int     col  []     =     {  0       0       -1       1  };          for     (  int     k     =     0  ;     k      <     4  ;     k  ++  )     {      int     ni     =     i     +     row  [  k  ];      int     nj     =     j     +     col  [  k  ];          int     pathLength     =     dfs  (  mat       ni       nj       x       y  );          // If a valid path is found from this direction      if     (  pathLength     !=     -1  )     {      maxPath     =     max  (  maxPath       1     +     pathLength  );      }      }          // Backtrack - restore the cell's original value (1)      mat  [  i  ][  j  ]     =     1  ;          return     maxPath  ;   }   int     findLongestPath  (  vector   <  vector   <  int  >>     &  mat       int     xs       int     ys       int     xd       int     yd  )     {      int     m     =     mat  .  size  ();      int     n     =     mat  [  0  ].  size  ();          // Check if source or destination is blocked      if     (  mat  [  xs  ][  ys  ]     ==     0     ||     mat  [  xd  ][  yd  ]     ==     0  )     {      return     -1  ;      }          return     dfs  (  mat       xs       ys       xd       yd  );   }   int     main  ()     {      vector   <  vector   <  int  >>     mat     =     {      {  1       1       1       1       1       1       1       1       1       1  }      {  1       1       0       1       1       0       1       1       0       1  }      {  1       1       1       1       1       1       1       1       1       1  }      };          int     xs     =     0       ys     =     0  ;         int     xd     =     1       yd     =     7  ;             int     result     =     findLongestPath  (  mat       xs       ys       xd       yd  );          if     (  result     !=     -1  )      cout      < <     result      < <     endl  ;      else      cout      < <     -1      < <     endl  ;          return     0  ;   }   

   public     class   GFG     {          // Function to find the longest path using backtracking without extra space      public     static     int     dfs  (  int  [][]     mat       int     i       int     j       int     x       int     y  )     {      int     m     =     mat  .  length  ;      int     n     =     mat  [  0  ]  .  length  ;          // If destination is reached      if     (  i     ==     x     &&     j     ==     y  )     {      return     0  ;      }          // If cell is invalid or blocked (0 means blocked or visited)      if     (  i      <     0     ||     i     >=     m     ||     j      <     0     ||     j     >=     n     ||     mat  [  i  ][  j  ]     ==     0  )     {      return     -  1  ;         }          // Mark current cell as visited by temporarily setting it to 0      mat  [  i  ][  j  ]     =     0  ;          int     maxPath     =     -  1  ;          // Four possible moves: up down left right      int  []     row     =     {  -  1       1       0       0  };      int  []     col     =     {  0       0       -  1       1  };          for     (  int     k     =     0  ;     k      <     4  ;     k  ++  )     {      int     ni     =     i     +     row  [  k  ]  ;      int     nj     =     j     +     col  [  k  ]  ;          int     pathLength     =     dfs  (  mat       ni       nj       x       y  );          // If a valid path is found from this direction      if     (  pathLength     !=     -  1  )     {      maxPath     =     Math  .  max  (  maxPath       1     +     pathLength  );      }      }          // Backtrack - restore the cell's original value (1)      mat  [  i  ][  j  ]     =     1  ;          return     maxPath  ;      }          public     static     int     findLongestPath  (  int  [][]     mat       int     xs       int     ys       int     xd       int     yd  )     {      int     m     =     mat  .  length  ;      int     n     =     mat  [  0  ]  .  length  ;          // Check if source or destination is blocked      if     (  mat  [  xs  ][  ys  ]     ==     0     ||     mat  [  xd  ][  yd  ]     ==     0  )     {      return     -  1  ;      }          return     dfs  (  mat       xs       ys       xd       yd  );      }          public     static     void     main  (  String  []     args  )     {      int  [][]     mat     =     {      {  1       1       1       1       1       1       1       1       1       1  }      {  1       1       0       1       1       0       1       1       0       1  }      {  1       1       1       1       1       1       1       1       1       1  }      };          int     xs     =     0       ys     =     0  ;         int     xd     =     1       yd     =     7  ;             int     result     =     findLongestPath  (  mat       xs       ys       xd       yd  );          if     (  result     !=     -  1  )      System  .  out  .  println  (  result  );      else      System  .  out  .  println  (  -  1  );      }   }   

   # Function to find the longest path using backtracking without extra space   def   dfs  (  mat     i     j     x     y  ):   m   =   len  (  mat  )   n   =   len  (  mat  [  0  ])   # If destination is reached   if   i   ==   x   and   j   ==   y  :   return   0   # If cell is invalid or blocked (0 means blocked or visited)   if   i    <   0   or   i   >=   m   or   j    <   0   or   j   >=   n   or   mat  [  i  ][  j  ]   ==   0  :   return   -  1   # Mark current cell as visited by temporarily setting it to 0   mat  [  i  ][  j  ]   =   0   maxPath   =   -  1   # Four possible moves: up down left right   row   =   [  -  1     1     0     0  ]   col   =   [  0     0     -  1     1  ]   for   k   in   range  (  4  ):   ni   =   i   +   row  [  k  ]   nj   =   j   +   col  [  k  ]   pathLength   =   dfs  (  mat     ni     nj     x     y  )   # If a valid path is found from this direction   if   pathLength   !=   -  1  :   maxPath   =   max  (  maxPath     1   +   pathLength  )   # Backtrack - restore the cell's original value (1)   mat  [  i  ][  j  ]   =   1   return   maxPath   def   findLongestPath  (  mat     xs     ys     xd     yd  ):   m   =   len  (  mat  )   n   =   len  (  mat  [  0  ])   # Check if source or destination is blocked   if   mat  [  xs  ][  ys  ]   ==   0   or   mat  [  xd  ][  yd  ]   ==   0  :   return   -  1   return   dfs  (  mat     xs     ys     xd     yd  )   def   main  ():   mat   =   [   [  1     1     1     1     1     1     1     1     1     1  ]   [  1     1     0     1     1     0     1     1     0     1  ]   [  1     1     1     1     1     1     1     1     1     1  ]   ]   xs     ys   =   0     0   xd     yd   =   1     7   result   =   findLongestPath  (  mat     xs     ys     xd     yd  )   if   result   !=   -  1  :   print  (  result  )   else  :   print  (  -  1  )   if   __name__   ==   '__main__'  :   main  ()   

   using     System  ;   class     GFG   {      // Function to find the longest path using backtracking without extra space      static     int     dfs  (  int  []     mat       int     i       int     j       int     x       int     y  )      {      int     m     =     mat  .  GetLength  (  0  );      int     n     =     mat  .  GetLength  (  1  );          // If destination is reached      if     (  i     ==     x     &&     j     ==     y  )      {      return     0  ;      }          // If cell is invalid or blocked (0 means blocked or visited)      if     (  i      <     0     ||     i     >=     m     ||     j      <     0     ||     j     >=     n     ||     mat  [  i       j  ]     ==     0  )      {      return     -  1  ;         }          // Mark current cell as visited by temporarily setting it to 0      mat  [  i       j  ]     =     0  ;          int     maxPath     =     -  1  ;          // Four possible moves: up down left right      int  []     row     =     {  -  1       1       0       0  };      int  []     col     =     {  0       0       -  1       1  };          for     (  int     k     =     0  ;     k      <     4  ;     k  ++  )      {      int     ni     =     i     +     row  [  k  ];      int     nj     =     j     +     col  [  k  ];          int     pathLength     =     dfs  (  mat       ni       nj       x       y  );          // If a valid path is found from this direction      if     (  pathLength     !=     -  1  )      {      maxPath     =     Math  .  Max  (  maxPath       1     +     pathLength  );      }      }          // Backtrack - restore the cell's original value (1)      mat  [  i       j  ]     =     1  ;          return     maxPath  ;      }          static     int     FindLongestPath  (  int  []     mat       int     xs       int     ys       int     xd       int     yd  )      {      // Check if source or destination is blocked      if     (  mat  [  xs       ys  ]     ==     0     ||     mat  [  xd       yd  ]     ==     0  )      {      return     -  1  ;      }          return     dfs  (  mat       xs       ys       xd       yd  );      }          static     void     Main  ()      {      int  []     mat     =     {      {  1       1       1       1       1       1       1       1       1       1  }      {  1       1       0       1       1       0       1       1       0       1  }      {  1       1       1       1       1       1       1       1       1       1  }      };          int     xs     =     0       ys     =     0  ;         int     xd     =     1       yd     =     7  ;             int     result     =     FindLongestPath  (  mat       xs       ys       xd       yd  );          if     (  result     !=     -  1  )      Console  .  WriteLine  (  result  );      else      Console  .  WriteLine  (  -  1  );      }   }   

   // Function to find the longest path using backtracking without extra space   function     dfs  (  mat       i       j       x       y  )     {      const     m     =     mat  .  length  ;      const     n     =     mat  [  0  ].  length  ;          // If destination is reached      if     (  i     ===     x     &&     j     ===     y  )     {      return     0  ;      }          // If cell is invalid or blocked (0 means blocked or visited)      if     (  i      <     0     ||     i     >=     m     ||     j      <     0     ||     j     >=     n     ||     mat  [  i  ][  j  ]     ===     0  )     {      return     -  1  ;         }          // Mark current cell as visited by temporarily setting it to 0      mat  [  i  ][  j  ]     =     0  ;          let     maxPath     =     -  1  ;          // Four possible moves: up down left right      const     row     =     [  -  1       1       0       0  ];      const     col     =     [  0       0       -  1       1  ];          for     (  let     k     =     0  ;     k      <     4  ;     k  ++  )     {      const     ni     =     i     +     row  [  k  ];      const     nj     =     j     +     col  [  k  ];          const     pathLength     =     dfs  (  mat       ni       nj       x       y  );          // If a valid path is found from this direction      if     (  pathLength     !==     -  1  )     {      maxPath     =     Math  .  max  (  maxPath       1     +     pathLength  );      }      }          // Backtrack - restore the cell's original value (1)      mat  [  i  ][  j  ]     =     1  ;          return     maxPath  ;   }   function     findLongestPath  (  mat       xs       ys       xd       yd  )     {      const     m     =     mat  .  length  ;      const     n     =     mat  [  0  ].  length  ;          // Check if source or destination is blocked      if     (  mat  [  xs  ][  ys  ]     ===     0     ||     mat  [  xd  ][  yd  ]     ===     0  )     {      return     -  1  ;      }          return     dfs  (  mat       xs       ys       xd       yd  );   }      const     mat     =     [      [  1       1       1       1       1       1       1       1       1       1  ]      [  1       1       0       1       1       0       1       1       0       1  ]      [  1       1       1       1       1       1       1       1       1       1  ]      ];          const     xs     =     0       ys     =     0  ;         const     xd     =     1       yd     =     7  ;             const     result     =     findLongestPath  (  mat       xs       ys       xd       yd  );          if     (  result     !==     -  1  )      console  .  log  (  result  );      else      console  .  log  (  -  1  );