Längstmögliche Route in einer Matrix mit Hürden
Probieren Sie es bei GfG Practice aus 
Ausgabe
Ausgabe
Gegeben sei eine 2D-Binärmatrix zusammen mit[][] wobei einige Zellen Hürden darstellen (gekennzeichnet mit 0 ) und der Rest sind freie Zellen (gekennzeichnet mit 1 ) Ihre Aufgabe besteht darin, die Länge der längstmöglichen Route von einer Quellzelle aus zu ermitteln (xs ys) zu einer Zielzelle (xd yd) .
- Sie können sich nur zu benachbarten Zellen bewegen (oben, unten, links, rechts).
- Diagonale Bewegungen sind nicht erlaubt.
- Eine einmal in einem Pfad besuchte Zelle kann auf demselben Pfad nicht erneut besucht werden.
- Wenn es unmöglich ist, das Ziel zu erreichen, kehren Sie zurück
-1.
Beispiele:
Eingang: xs = 0 ys = 0 xd = 1 yd = 7
with[][] = [ [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] ]
Ausgabe: 24
Erläuterung:
Eingang: xs = 0 ys = 3 xd = 2 yd = 2
mit[][] =[ [1 0 0 1 0]
[0 0 0 1 0]
[0 1 1 0 0] ]
Ausgabe: -1
Erläuterung:
Wir sehen, dass es unmöglich ist
Erreichen Sie die Zelle (22) von (03).
Inhaltsverzeichnis
- [Ansatz] Verwendung von Backtracking mit Visited Matrix
- [Optimierter Ansatz] Ohne zusätzlichen Platzbedarf
[Ansatz] Verwendung von Backtracking mit Visited Matrix
CPPDie Idee ist zu verwenden Zurückverfolgen . Wir gehen von der Quellzelle der Matrix aus vorwärts in alle vier erlaubten Richtungen und prüfen rekursiv, ob sie zur Lösung führen oder nicht. Wenn das Ziel gefunden wird, aktualisieren wir den Wert des längsten Pfads. Wenn keine der oben genannten Lösungen funktioniert, geben wir von unserer Funktion „false“ zurück.
#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 ; }
Java 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 ); } }
Python # 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 ()
C# 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 ); } }
JavaScript // 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 );
Ausgabe
24
Zeitkomplexität: O(4^(m*n)) Für jede Zelle in der m x n-Matrix untersucht der Algorithmus bis zu vier mögliche Richtungen (oben unten links rechts), was zu einer exponentiellen Anzahl von Pfaden führt. Im schlimmsten Fall werden alle möglichen Pfade untersucht, was zu einer Zeitkomplexität von 4^(m*n) führt.
Hilfsraum: O(m*n) Der Algorithmus verwendet eine m x n besuchte Matrix, um besuchte Zellen zu verfolgen, und einen Rekursionsstapel, der im schlimmsten Fall (z. B. beim Erkunden eines Pfads, der alle Zellen abdeckt) bis zu einer Tiefe von m * n anwachsen kann. Somit ist der Hilfsraum O(m*n).
[Optimierter Ansatz] Ohne zusätzlichen Platzbedarf
Anstatt eine separate besuchte Matrix zu verwalten, können wir dies tun Wiederverwendung der Eingabematrix um besuchte Zellen während der Durchquerung zu markieren. Dies spart zusätzlichen Platz und stellt dennoch sicher, dass wir nicht dieselbe Zelle in einem Pfad erneut aufrufen.
Nachfolgend finden Sie die schrittweise Vorgehensweise:
- Beginnen Sie mit der Quellzelle
(xs ys). - Erkunden Sie bei jedem Schritt alle vier möglichen Richtungen (rechts unten, links oben).
- Für jeden gültigen Zug:
- Überprüfen Sie die Grenzen und stellen Sie sicher, dass die Zelle einen Wert hat
1(freie Zelle). - Markieren Sie die Zelle als besucht, indem Sie sie vorübergehend auf setzen
0. - Rekursieren Sie in die nächste Zelle und erhöhen Sie die Pfadlänge.
- Überprüfen Sie die Grenzen und stellen Sie sicher, dass die Zelle einen Wert hat
- Wenn die Zielzelle
(xd yd)Ist erreicht, vergleichen Sie die aktuelle Pfadlänge mit dem bisherigen Maximum und aktualisieren Sie die Antwort. - Zurückverfolgen: Stellen Sie den ursprünglichen Wert der Zelle wieder her (
1), bevor Sie zurückkehren, damit andere Pfade es erkunden können. - Fahren Sie mit der Erkundung fort, bis alle möglichen Pfade besucht sind.
- Gibt die maximale Pfadlänge zurück. Wenn das Ziel nicht erreichbar ist, kehren Sie zurück
-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 ; }
Java 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 ); } }
Python # 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 ()
C# 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 ); } }
JavaScript // 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 );
Ausgabe
24
Zeitkomplexität: O(4^(m*n))Der Algorithmus untersucht immer noch bis zu vier Richtungen pro Zelle in der m x n-Matrix, was zu einer exponentiellen Anzahl von Pfaden führt. Die direkte Änderung hat keinen Einfluss auf die Anzahl der untersuchten Pfade, sodass die Zeitkomplexität weiterhin 4^(m*n) beträgt.
Hilfsraum: O(m*n) Während die besuchte Matrix durch direktes Ändern der Eingabematrix eliminiert wird, benötigt der Rekursionsstapel immer noch O(m*n) Platz, da die maximale Rekursionstiefe im schlimmsten Fall m * n betragen kann (z. B. ein Pfad, der alle Zellen in einem Gitter mit überwiegend Einsen besucht).
