Nejdelší možná trasa v matici s překážkami
Zkuste to na GfG Practice 
Výstup
Výstup
Je dána 2D binární matice spolu s[][] kde některé buňky představují překážky (označené 0 ) a zbytek jsou volné buňky (označené 1 ) vaším úkolem je najít délku nejdelší možné trasy ze zdrojové buňky (xs ys) do cílové buňky (xd yd) .
- Můžete se přesunout pouze do sousedních buněk (nahoru dolů vlevo vpravo).
- Diagonální pohyby nejsou povoleny.
- Buňku jednou navštívenou v cestě nelze znovu navštívit ve stejné cestě.
- Pokud není možné dosáhnout cíle, vraťte se
-1.
Příklady:
Vstup: xs = 0 ys = 0 xd = 1 yd = 7
s[][] = [ [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] ]
výstup: 24
Vysvětlení:
Vstup: xs = 0 ys = 3 xd = 2 yd = 2
s[][] =[ [1 0 0 1 0]
[0 0 0 1 0]
[0 1 1 0 0] ]
výstup: -1
Vysvětlení:
Vidíme, že je to nemožné
dosáhnout buňky (22) z (03).
Obsah
- [Přístup] Použití Backtracking s navštívenou maticí
- [Optimalizovaný přístup] Bez využití prostoru navíc
[Přístup] Použití Backtracking s navštívenou maticí
CPPMyšlenka je použít Zpětné sledování . Začneme od zdrojové buňky matice posouvat se vpřed všemi čtyřmi povolenými směry a rekurzivně kontrolujeme, zda vedou k řešení nebo ne. Pokud je cíl nalezen, aktualizujeme hodnotu nejdelší cesty, jinak pokud žádné z výše uvedených řešení nefunguje, vrátíme z naší funkce hodnotu false.
#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 );
Výstup
24
Časová náročnost: O(4^(m*n)) Pro každou buňku v matici m x n algoritmus zkoumá až čtyři možné směry (nahoru dolů vlevo vpravo) vedoucí k exponenciálnímu počtu cest. V nejhorším případě prozkoumá všechny možné cesty, což má za následek časovou složitost 4^(m*n).
Pomocný prostor: O(m*n) Algoritmus používá matici m x n navštívených buněk ke sledování navštívených buněk a rekurzní zásobník, který může v nejhorším případě narůst až do hloubky m * n (např. při zkoumání cesty pokrývající všechny buňky). Pomocný prostor je tedy O(m*n).
[Optimalizovaný přístup] Bez využití prostoru navíc
Místo udržování samostatné navštívené matice můžeme znovu použít vstupní matici k označení navštívených buněk během průchodu. To šetří místo navíc a stále zajišťuje, že nebudeme znovu navštěvovat stejnou buňku na cestě.
Níže je uveden postup krok za krokem:
- Začněte od zdrojové buňky
(xs ys). - V každém kroku prozkoumejte všechny čtyři možné směry (zprava dolů doleva nahoru).
- Pro každý platný tah:
- Zkontrolujte hranice a ujistěte se, že buňka má hodnotu
1(volná buňka). - Označte buňku jako navštívenou tím, že ji dočasně nastavíte na
0. - Vraťte se do další buňky a zvyšte délku cesty.
- Zkontrolujte hranice a ujistěte se, že buňka má hodnotu
- Pokud cílová buňka
(xd yd)je dosaženo, porovnejte aktuální délku cesty s dosavadním maximem a aktualizujte odpověď. - Backtrack: obnovte původní hodnotu buňky (
1), než se vrátíte, abyste ji mohli prozkoumat jinými cestami. - Pokračujte v průzkumu, dokud nenajdete všechny možné cesty.
- Vraťte maximální délku cesty. Pokud je cíl nedosažitelný, vraťte se
-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 );
Výstup
24
Časová náročnost: O(4^(m*n))Algoritmus stále zkoumá až čtyři směry na buňku v matici m x n, což vede k exponenciálnímu počtu cest. Úprava na místě neovlivňuje počet prozkoumaných cest, takže časová složitost zůstává 4^(m*n).
Pomocný prostor: O(m*n) Zatímco navštívená matice je eliminována úpravou vstupní matice na místě, zásobník rekurze stále vyžaduje prostor O(m*n), protože maximální hloubka rekurze může být v nejhorším případě m * n (např. cesta navštěvující všechny buňky v mřížce s většinou 1s).
