Ilgiausias įmanomas maršrutas matricoje su kliūtimis
Išbandykite GfG praktikoje 
Išvestis
Išvestis
Duota 2D dvejetainė matrica kartu su [][] kur kai kurios ląstelės yra kliūtys (žymima 0 ), o likusios yra laisvos ląstelės (žymimos 1 ) jūsų užduotis yra rasti ilgiausio įmanomo maršruto iš šaltinio langelio ilgį (xs ys) į paskirties langelį (xd yd) .
- Galite pereiti tik į gretimus langelius (aukštyn žemyn į kairę į dešinę).
- Įstrižiniai judesiai neleidžiami.
- Vieną kartą aplankytas langelis negali būti pakartotinai aplankytas tame pačiame kelyje.
- Jei neįmanoma pasiekti kelionės tikslo, grįžkite
-1.
Pavyzdžiai:
Įvestis: xs = 0 ys = 0 xd = 1 yd = 7
su[][] = [ [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] ]
Išvestis: 24
Paaiškinimas:
Įvestis: xs = 0 ys = 3 xd = 2 yd = 2
su [][] =[ [1 0 0 1 0]
[0 0 0 1 0]
[0 1 1 0 0] ]
Išvestis: -1
Paaiškinimas:
Matome, kad tai neįmanoma
pasiekti kamerą (22) iš (03).
Turinio lentelė
- [Metodas] Atgalinio sekimo naudojimas su aplankyta matrica
- [Optimizuotas požiūris] Nenaudojant papildomos vietos
[Metodas] Atgalinio sekimo naudojimas su aplankyta matrica
CPPIdėja yra naudoti Atsitraukimas . Pradedame nuo matricos šaltinio langelio, judame į priekį visomis keturiomis leidžiamomis kryptimis ir rekursyviai tikriname, ar jos veda į sprendimą, ar ne. Jei tikslas randamas, atnaujiname ilgiausio kelio reikšmę, kitaip, jei nė vienas iš aukščiau pateiktų sprendimų neveikia, iš savo funkcijos grąžiname 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 );
Išvestis
24
Laiko sudėtingumas: O(4^(m*n)) Kiekvienam m x n matricos langeliui algoritmas tiria iki keturių galimų krypčių (aukštyn žemyn į kairę į dešinę), vedančią į eksponentinį kelių skaičių. Blogiausiu atveju jis ištiria visus galimus kelius, todėl laiko sudėtingumas yra 4^(m*n).
Pagalbinė erdvė: O(m*n) Algoritmas naudoja m x n aplankytą matricą aplankytoms ląstelėms sekti ir rekursijos krūvą, kuri blogiausiu atveju gali išaugti iki m * n gylio (pvz., tyrinėjant kelią, apimantį visas ląsteles). Taigi pagalbinė erdvė yra O(m*n).
[Optimizuotas požiūris] Nenaudojant papildomos vietos
Užuot palaikę atskirą lankomą matricą, galime pakartotinai naudokite įvesties matricą pažymėti aplankytas ląsteles perėjimo metu. Taip sutaupoma papildomos vietos ir vis tiek užtikrinama, kad daugiau nekartosime to paties kelio langelio.
Žemiau pateikiamas žingsnis po žingsnio metodas:
- Pradėkite nuo šaltinio langelio
(xs ys). - Kiekviename žingsnyje tyrinėkite visas keturias galimas kryptis (dešinėn žemyn, kairėn aukštyn).
- Už kiekvieną teisingą judėjimą:
- Patikrinkite ribas ir įsitikinkite, kad langelis turi vertę
1(laisva ląstelė). - Pažymėkite langelį kaip aplankytą laikinai nustatydami jį į
0. - Pereikite į kitą langelį ir padidinkite kelio ilgį.
- Patikrinkite ribas ir įsitikinkite, kad langelis turi vertę
- Jei paskirties langelis
(xd yd)pasiektas, palyginkite esamą kelio ilgį su maksimaliu iki šiol ir atnaujinkite atsakymą. - Atgal: atkurti pradinę langelio vertę (
1) prieš grįždami, kad kiti keliai galėtų jį ištirti. - Tęskite tyrinėjimą, kol aplankysite visus įmanomus kelius.
- Grąžinkite maksimalų kelio ilgį. Jei kelionės tikslas nepasiekiamas, grįžkite
-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 );
Išvestis
24
Laiko sudėtingumas: O(4^(m*n))Algoritmas vis tiek tiria iki keturių krypčių viename m x n matricos langelyje, todėl gaunamas eksponentinis kelių skaičius. Modifikacija vietoje neturi įtakos ištirtų kelių skaičiui, todėl laiko sudėtingumas išlieka 4^(m*n).
Pagalbinė erdvė: O(m*n) Nors aplankyta matrica pašalinama modifikuojant įvesties matricą vietoje, rekursijos krūvai vis tiek reikia O(m*n) vietos, nes didžiausias rekursijos gylis gali būti m * n blogiausiu atveju (pvz., kelias, aplankantis visus tinklelio langelius, kuriuose daugiausia 1s).
