logo

TechCodeview

Garākais iespējamais maršruts matricā ar šķēršļiem

Izmēģiniet to GfG Practice Garākais iespējamais maršruts matricā ar šķēršļiem' title=

Dota 2D binārā matrica kopā ar [][] kur dažas šūnas ir šķēršļi (apzīmē ar0) un pārējās ir brīvas šūnas (apzīmētas ar1) jūsu uzdevums ir atrast garākā iespējamā maršruta garumu no avota šūnas (xs ys) uz mērķa šūnu (xd yd) .

  • Jūs varat pāriet tikai uz blakus esošajām šūnām (augšup uz leju pa kreisi pa labi).
  • Diagonālās kustības nav atļautas.
  • Vienreiz ceļā apmeklētu šūnu nevar atkārtoti apmeklēt tajā pašā ceļā.
  • Ja nav iespējams sasniegt galamērķi, atgriezieties-1.

Piemēri:
Ievade: xs = 0 ys = 0 xd = 1 yd = 7
ar [][] = [ [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] ]
Izvade: 24
Paskaidrojums:



ziemas guļas dialekts

Ievade: xs = 0 ys = 3 xd = 2 yd = 2
ar [][] =[ [1 0 0 1 0]
[0 0 0 1 0]
[0 1 1 0 0] ]
Izvade: -1
Paskaidrojums:
Mēs redzam, ka tas nav iespējams
sasniedz šūnu (22) no (03).

Satura rādītājs



[Pieeja] Atkāpšanās izmantošana ar apmeklēto matricu

Ideja ir izmantot Atkāpšanās . Mēs sākam no matricas avota šūnas, virzāmies uz priekšu visos četros atļautajos virzienos un rekursīvi pārbaudām, vai tie noved pie risinājuma vai nē. Ja tiek atrasts galamērķis, mēs atjauninām garākā ceļa vērtību, ja neviens no iepriekš minētajiem risinājumiem nedarbojas, mēs atgriežam savu funkciju false.

kali linux komandas
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);

Izvade 
24

Laika sarežģītība: O(4^(m*n)) Katrai šūnai m x n matricā algoritms izpēta līdz četriem iespējamiem virzieniem (augšup uz leju pa kreisi pa labi), kas noved pie eksponenciāla ceļu skaita. Sliktākajā gadījumā tas pēta visus iespējamos ceļus, kā rezultātā laika sarežģītība ir 4^(m*n).
Palīgtelpa: O(m*n) Algoritms izmanto m x n apmeklēto matricu, lai izsekotu apmeklētajām šūnām, un rekursijas steku, kas sliktākajā gadījumā var izaugt līdz m * n dziļumam (piemēram, pētot ceļu, kas aptver visas šūnas). Tādējādi palīgtelpa ir O(m*n).

[Optimizēta pieeja], neizmantojot papildu vietu

Tā vietā, lai uzturētu atsevišķu apmeklēto matricu, mēs varam atkārtoti izmantojiet ievades matricu lai atzīmētu apmeklētās šūnas šķērsošanas laikā. Tas ietaupa papildu vietu un joprojām nodrošina, ka mēs atkārtoti neapmeklējam to pašu šūnu ceļā.



kas ir strops

Tālāk ir sniegta soli pa solim pieeja:

  1. Sāciet no avota šūnas(xs ys).
  2. Katrā solī izpētiet visus četrus iespējamos virzienus (pa labi uz leju pa kreisi uz augšu).
  3. Par katru derīgo gājienu:
    • Pārbaudiet robežas un pārliecinieties, ka šūnai ir vērtība1(brīva šūna).
    • Atzīmējiet šūnu kā apmeklētu, īslaicīgi iestatot to uz0.
    • Atkārtojieties nākamajā šūnā un palieliniet ceļa garumu.
  4. Ja mērķa šūna(xd yd)ir sasniegts, salīdziniet pašreizējo ceļa garumu ar līdz šim maksimālo un atjauniniet atbildi.
  5. Atpakaļ: atjauno šūnas sākotnējo vērtību (1) pirms atgriešanās, lai citi ceļi varētu to izpētīt.
  6. Turpiniet izpēti, līdz ir apmeklēti visi iespējamie ceļi.
  7. Atgriezt maksimālo ceļa garumu. Ja galamērķis nav sasniedzams, atgriezieties-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);

Izvade 
24

Laika sarežģītība: O(4^(m*n))Algoritms joprojām izpēta līdz četriem virzieniem vienā šūnā m x n matricā, kā rezultātā tiek iegūts eksponenciāls ceļu skaits. Vietējā modifikācija neietekmē izpētīto ceļu skaitu, tāpēc laika sarežģītība paliek 4^(m*n).
Palīgtelpa: O(m*n) Kamēr apmeklētā matrica tiek likvidēta, modificējot ievades matricu savā vietā, rekursijas kaudze joprojām prasa O(m*n) atstarpi, jo maksimālais rekursijas dziļums var būt m * n sliktākajā gadījumā (piemēram, ceļš, kas apmeklē visas režģa šūnas ar pārsvarā 1s).