logo

TechCodeview

La ruta més llarga possible en una matriu amb tanques

Prova-ho a GfG Practice La ruta més llarga possible en una matriu amb tanques' title=

Donada una matriu binària 2D juntament amb[][] on algunes cèl·lules són obstacles (indicats per0) i la resta són cel·les lliures (indicades per1) la vostra tasca és trobar la longitud de la ruta més llarga possible des d'una cel·la font (xs ys) a una cel·la de destinació (xd yd) .

idea intel·ligent vs eclipsi
  • Només us podeu moure a cel·les adjacents (a dalt a baix, a l'esquerra, a la dreta).
  • No es permeten moviments en diagonal.
  • Una cel·la visitada un cop en un camí no es pot tornar a visitar en aquest mateix camí.
  • Si és impossible arribar al destí torna-1.

Exemples:
Entrada: xs = 0 ys = 0 xd = 1 yd = 7
amb[][] = [[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] ]
Sortida: 24
Explicació:



Entrada: xs = 0 ys = 3 xd = 2 yd = 2
amb[][] =[ [1 0 0 1 0]
[0 0 0 1 0]
[0 1 1 0 0] ]
Sortida: -1
Explicació:
Podem veure que és impossible
arribar a la cel·la (22) des de (03).

Taula de continguts



data d'utilitat java

[Enfocament] Ús del backtracking amb la matriu visitada

La idea és utilitzar Fes marxa enrere . Partim de la cel·la font de la matriu avançant en les quatre direccions permeses i comprovem recursivament si porten a la solució o no. Si es troba la destinació, actualitzem el valor del camí més llarg; si no funciona cap de les solucions anteriors, retornem false de la nostra funció.

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

Sortida 
24

Complexitat temporal: O(4^(m*n)) Per a cada cel·la de la matriu m x n, l'algorisme explora fins a quatre direccions possibles (a dalt a baix, a l'esquerra a la dreta) que condueixen a un nombre exponencial de camins. En el pitjor dels casos, explora tots els camins possibles donant com a resultat una complexitat temporal de 4^(m*n).
Espai auxiliar: O(m*n) L'algorisme utilitza una matriu visitada m x n per fer un seguiment de les cel·les visitades i una pila de recursivitat que pot créixer a una profunditat de m * n en el pitjor dels casos (per exemple, quan s'explora un camí que cobreix totes les cel·les). Així, l'espai auxiliar és O(m*n).

[Enfocament optimitzat] sense utilitzar espai addicional

En lloc de mantenir una matriu visitada separada, podem reutilitza la matriu d'entrada per marcar les cel·les visitades durant el recorregut. Això estalvia espai addicional i encara garanteix que no tornem a visitar la mateixa cel·la en un camí.



bash altrament si

A continuació es mostra l'enfocament pas a pas:

  1. Comenceu des de la cel·la font(xs ys).
  2. A cada pas, exploreu les quatre direccions possibles (dreta avall, esquerra amunt).
  3. Per a cada moviment vàlid:
    • Comproveu els límits i assegureu-vos que la cel·la tingui valor1(cel·la lliure).
    • Marqueu la cel·la com a visitada configurant-la temporalment0.
    • Recorreu a la següent cel·la i incrementeu la longitud del camí.
  4. Si la cel·la de destinació(xd yd)s'arriba a comparar la longitud del camí actual amb la màxima fins ara i actualitzar la resposta.
  5. Retrocés: restaura el valor original de la cel·la (1) abans de tornar per permetre que altres camins l'explorin.
  6. Continueu explorant fins que es visitin tots els camins possibles.
  7. Retorna la longitud màxima del camí. Si la destinació és inabastable torna-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);

Sortida 
24

Complexitat temporal: O(4^(m*n))L'algorisme encara explora fins a quatre direccions per cel·la a la matriu m x n donant com a resultat un nombre exponencial de camins. La modificació in situ no afecta el nombre de camins explorats, de manera que la complexitat temporal es manté en 4^(m*n).
Espai auxiliar: O(m*n) Mentre que la matriu visitada s'elimina modificant la matriu d'entrada al seu lloc, la pila de recursivitat encara requereix espai O(m*n), ja que la profunditat màxima de recursió pot ser m * n en el pitjor dels casos (per exemple, un camí que visita totes les cel·les d'una quadrícula amb majoritàriament 1s).