logo

TechCodeview

Nejdelší možná trasa v matici s překážkami

Zkuste to na GfG Practice Nejdelší možná trasa v matici s překážkami' title=

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í

Myš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.

java scan.nextstring
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);

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:

  1. Začněte od zdrojové buňky(xs ys).
  2. V každém kroku prozkoumejte všechny čtyři možné směry (zprava dolů doleva nahoru).
  3. Pro každý platný tah:
    • Zkontrolujte hranice a ujistěte se, že buňka má hodnotu1(volná buňka).
    • Označte buňku jako navštívenou tím, že ji dočasně nastavíte na0.
    • Vraťte se do další buňky a zvyšte délku cesty.
  4. Pokud cílová buňka(xd yd)je dosaženo, porovnejte aktuální délku cesty s dosavadním maximem a aktualizujte odpověď.
  5. Backtrack: obnovte původní hodnotu buňky (1), než se vrátíte, abyste ji mohli prozkoumat jinými cestami.
  6. Pokračujte v průzkumu, dokud nenajdete všechny možné cesty.
  7. Vraťte maximální délku cesty. Pokud je cíl nedosažitelný, vraťte se-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);

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).