Najduža moguća ruta u Matrixu s preponama
Isprobajte na GfG Practice 
Izlaz
Izlaz
Zadana je 2D binarna matrica zajedno sa [][] gdje su neke ćelije prepreke (označene sa 0 ), a ostalo su slobodne ćelije (označene sa 1 ) vaš zadatak je pronaći duljinu najduže moguće rute od izvorne ćelije (xs ys) (xd yd) .
- Možete se pomicati samo na susjedne ćelije (gore dolje lijevo desno).
- Dijagonalni potezi nisu dopušteni.
- Ćelija jednom posjećena na putu ne može se ponovno posjetiti na tom istom putu.
- Ako je nemoguće doći do odredišta povratak
-1.
Primjeri:
Ulazni: xs = 0 ys = 0 xd = 1 yd = 7
s [][] = [ [1 1 1 1 1 1 1 1 1 1]
Izlaz: 24
Obrazloženje:
Ulazni: xs = 0 ys = 3 xd = 2 yd = 2
Izlaz: -1
Obrazloženje:
Vidimo da je nemoguće
doći do ćelije (22) iz (03).
Sadržaj
- [Pristup] Korištenje povratnog praćenja s matricom posjeta
- [Optimizirani pristup] Bez korištenja dodatnog prostora
[Pristup] Korištenje povratnog praćenja s matricom posjeta
CPPIdeja je koristiti . Krećemo od ishodišne ćelije matrice i krećemo se naprijed u sva četiri dozvoljena smjera i rekurzivno provjeravamo vode li oni do rješenja ili ne. Ako je odredište pronađeno, ažuriramo vrijednost najduže staze, inače ako nijedno od gore navedenih rješenja ne radi, vraćamo false iz naše funkcije.
#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 );
Izlaz
24
Vremenska složenost: O(4^(m*n)) Za svaku ćeliju u m x n matrici algoritam istražuje do četiri moguća smjera (gore dolje lijevo desno) što dovodi do eksponencijalnog broja staza. U najgorem slučaju istražuje sve moguće putove što rezultira vremenskom složenošću od 4^(m*n).
Pomoćni prostor: O(m*n) Algoritam koristi m x n posjećenu matricu za praćenje posjećenih ćelija i rekurzivni stog koji može narasti do dubine od m * n u najgorem slučaju (npr. kada se istražuje put koji pokriva sve ćelije). Tako je pomoćni prostor O(m*n).
[Optimizirani pristup] Bez korištenja dodatnog prostora
Umjesto održavanja zasebne posjećene matrice možemo ponovno koristiti ulaznu matricu za označavanje posjećenih ćelija tijekom obilaska. To štedi dodatni prostor i još uvijek osigurava da nećemo ponovno posjećivati istu ćeliju na putu.
Ispod je pristup korak po korak:
- Počnite od izvorne ćelije
(xs ys). - Na svakom koraku istražite sva četiri moguća smjera (desno dolje lijevo gore).
- Za svaki važeći potez:
- Provjerite granice i osigurajte da ćelija ima vrijednost
1(slobodna ćelija). - Označite ćeliju kao posjećenu tako da je privremeno postavite na
0. - Vratite se u sljedeću ćeliju i povećajte duljinu puta.
- Provjerite granice i osigurajte da ćelija ima vrijednost
- Ako odredišna ćelija
(xd yd)je dosegnuta usporedi trenutnu duljinu puta s maksimalnom do sada i ažuriraj odgovor. - Povratak: vrati izvornu vrijednost ćelije (
1) prije povratka kako biste omogućili drugim stazama da ga istraže. - Nastavite istraživati dok ne obiđete sve moguće staze.
- Vrati maksimalnu duljinu puta. Ako je odredište nedostupno povratak
-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 );
Izlaz
24
Vremenska složenost: O(4^(m*n))Algoritam i dalje istražuje do četiri smjera po ćeliji u m x n matrici što rezultira eksponencijalnim brojem putanja. Modifikacija na mjestu ne utječe na broj istraženih staza tako da vremenska složenost ostaje 4^(m*n).
Pomoćni prostor: O(m*n) Dok se posjećena matrica eliminira modificiranjem ulazne matrice na mjestu, rekurzivni stog i dalje zahtijeva O(m*n) prostora jer maksimalna dubina rekurzije može biti m * n u najgorem slučaju (npr. put koji posjećuje sve ćelije u mreži s većinom 1).
