장애물이 있는 매트릭스에서 가능한 가장 긴 경로
GfG Practice에서 사용해 보세요. 
산출
산출
2D 이진 행렬이 주어지면 [][]와 함께 일부 세포는 장애물(로 표시됨)인 경우 0 ) 나머지는 자유 셀(로 표시됨)입니다. 1 ) 당신의 임무는 소스 셀에서 가능한 가장 긴 경로의 길이를 찾는 것입니다 (xs ys) 대상 셀로 (xd yd) .
- 인접한 셀(위 아래 왼쪽 오른쪽)로만 이동할 수 있습니다.
- 대각선 이동은 허용되지 않습니다.
- 경로에서 한 번 방문한 셀은 동일한 경로에서 다시 방문할 수 없습니다.
- 목적지까지 도달이 불가능할 경우 귀국
-1.
예:
입력: 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] ]
산출: 24
설명:
입력: xs = 0 ys = 3 xd = 2 yd = 2
with[][] =[ [1 0 0 1 0]
[0 0 0 1 0]
[0 1 1 0 0] ]
산출: -1
설명:
불가능하다는 것을 알 수 있습니다
(03)에서 셀 (22)에 도달합니다.
목차
[접근법] Visited Matrix를 이용한 역추적 활용
CPP아이디어는 사용하는 것입니다 역추적 . 우리는 매트릭스의 소스 셀에서 시작하여 허용된 네 방향 모두로 이동하고 그것이 솔루션으로 이어지는지 여부를 재귀적으로 확인합니다. 대상을 찾으면 가장 긴 경로의 값을 업데이트하고 위의 솔루션 중 어느 것도 작동하지 않으면 함수에서 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 );
산출
24
시간 복잡도: O(4^(m*n)) m x n 행렬의 각 셀에 대해 알고리즘은 기하급수적인 경로 수로 이어지는 최대 4개의 가능한 방향(위 아래 왼쪽 오른쪽)을 탐색합니다. 최악의 경우 가능한 모든 경로를 탐색하여 4^(m*n)의 시간 복잡도를 초래합니다.
보조 공간: O(m*n) 알고리즘은 m x n 방문 행렬을 사용하여 방문한 셀을 추적하고 최악의 경우(예: 모든 셀을 포함하는 경로를 탐색할 때) m * n 깊이까지 성장할 수 있는 재귀 스택을 사용합니다. 따라서 보조 공간은 O(m*n)입니다.
[최적화된 접근 방식] 추가 공간을 사용하지 않고
별도의 방문 행렬을 유지하는 대신 다음을 수행할 수 있습니다. 입력 행렬 재사용 순회 중에 방문한 셀을 표시합니다. 이렇게 하면 추가 공간이 절약되고 경로에서 동일한 셀을 다시 방문하지 않게 됩니다.
다음은 단계별 접근 방식입니다.
- 소스 셀에서 시작
(xs ys). - 각 단계에서 가능한 네 가지 방향(오른쪽 아래 왼쪽 위)을 모두 탐색합니다.
- 각 유효한 이동에 대해 다음을 수행합니다.
- 경계를 확인하고 셀에 값이 있는지 확인하세요.
1(무료 셀). - 임시로 설정하여 셀을 방문한 것으로 표시합니다.
0. - 다음 셀로 재귀하여 경로 길이를 늘립니다.
- 경계를 확인하고 셀에 값이 있는지 확인하세요.
- 대상 셀인 경우
(xd yd)도달하면 현재 경로 길이를 지금까지의 최대 길이와 비교하고 답변을 업데이트합니다. - 역추적: 셀의 원래 값을 복원합니다(
1) 다른 경로에서 탐색할 수 있도록 돌아오기 전에. - 가능한 모든 경로를 방문할 때까지 계속 탐색하세요.
- 최대 경로 길이를 반환합니다. 목적지에 도달할 수 없는 경우 귀국
-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 );
산출
24
시간 복잡도: O(4^(m*n)) 알고리즘은 m x n 행렬의 셀당 최대 4개의 방향을 탐색하여 기하급수적인 경로 수를 생성합니다. 내부 수정은 탐색된 경로 수에 영향을 미치지 않으므로 시간 복잡도는 4^(m*n)으로 유지됩니다.
보조 공간: O(m*n) 방문 행렬은 입력 행렬을 내부 수정하여 제거되지만 최악의 경우(예: 대부분 1인 그리드의 모든 셀을 방문하는 경로) 최대 재귀 깊이가 m * n이 될 수 있으므로 재귀 스택에는 여전히 O(m*n) 공간이 필요합니다.
