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 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)に到達します。
目次
[アプローチ] 訪問済み行列でバックトラッキングを使用する
CPPアイデアは使用することです 後戻り 。行列のソース セルから開始して、許可される 4 つの方向すべてに前進し、それらが解につながるかどうかを再帰的にチェックします。宛先が見つかった場合は最長パスの値を更新し、上記の解決策がいずれも機能しない場合は関数から false を返します。
#include
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); } }
# 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()
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); } }
// 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)。 - 各ステップで、可能な 4 つの方向 (右下、左上) をすべて探索します。
- それぞれの有効な動きについて:
- 境界をチェックし、セルに値があることを確認します
1(フリーセル)。 - 一時的にセルを次のように設定して、セルを訪問済みとしてマークします。
0。 - 次のセルに再帰し、パスの長さを増やします。
- 境界をチェックし、セルに値があることを確認します
- 宛先セルの場合
(xd yd)に達すると、現在のパスの長さとこれまでの最大値を比較し、答えを更新します。 - バックトラック: セルの元の値を復元します (
1) に戻る前に、他のパスが探索できるようにします。 - 考えられるすべてのパスを訪問するまで探索を続けます。
- 最大パス長を返します。目的地に到達できない場合は戻る
-1
#include
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); } }
# 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()
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); } }
// 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) スペースが必要です。