logo

TechCodeview

장애물이 있는 매트릭스에서 가능한 가장 긴 경로

GfG Practice에서 사용해 보세요. 장애물이 있는 매트릭스에서 가능한 가장 긴 경로' title=

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를 이용한 역추적 활용

아이디어는 사용하는 것입니다 역추적 . 우리는 매트릭스의 소스 셀에서 시작하여 허용된 네 방향 모두로 이동하고 그것이 솔루션으로 이어지는지 여부를 재귀적으로 확인합니다. 대상을 찾으면 가장 긴 경로의 값을 업데이트하고 위의 솔루션 중 어느 것도 작동하지 않으면 함수에서 false를 반환합니다.

CPP 
#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)입니다.

안드로이드의 imessage 게임

[최적화된 접근 방식] 추가 공간을 사용하지 않고

별도의 방문 행렬을 유지하는 대신 다음을 수행할 수 있습니다. 입력 행렬 재사용 순회 중에 방문한 셀을 표시합니다. 이렇게 하면 추가 공간이 절약되고 경로에서 동일한 셀을 다시 방문하지 않게 됩니다.



다음은 단계별 접근 방식입니다.

  1. 소스 셀에서 시작(xs ys).
  2. 각 단계에서 가능한 네 가지 방향(오른쪽 아래 왼쪽 위)을 모두 탐색합니다.
  3. 각 유효한 이동에 대해 다음을 수행합니다.
    • 경계를 확인하고 셀에 값이 있는지 확인하세요.1(무료 셀).
    • 임시로 설정하여 셀을 방문한 것으로 표시합니다.0.
    • 다음 셀로 재귀하여 경로 길이를 늘립니다.
  4. 대상 셀인 경우(xd yd)도달하면 현재 경로 길이를 지금까지의 최대 길이와 비교하고 답변을 업데이트합니다.
  5. 역추적: 셀의 원래 값을 복원합니다(1) 다른 경로에서 탐색할 수 있도록 돌아오기 전에.
  6. 가능한 모든 경로를 방문할 때까지 계속 탐색하세요.
  7. 최대 경로 길이를 반환합니다. 목적지에 도달할 수 없는 경우 귀국-1
C++ 
#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) 공간이 필요합니다.