logo

TechCodeview

Najdaljša možna pot v matrici z ovirami

Preizkusite na GfG Practice Najdaljša možna pot v matrici z ovirami' title=

Podana je 2D binarna matrika skupaj z [][] kjer so nekatere celice ovire (označeno z0), ostalo pa so proste celice (označene z1) vaša naloga je najti dolžino najdaljše možne poti od izvorne celice (xs ys) v ciljno celico (xd yd) .

  • Premaknete se lahko le v sosednje celice (gor dol levo desno).
  • Diagonalni premiki niso dovoljeni.
  • Enkrat obiskane celice na poti ni mogoče ponovno obiskati na isti poti.
  • Če je nemogoče doseči cilj vrnitev-1.

Primeri:
Vnos: xs = 0 ys = 0 xd = 1 yd = 7
z [][] = [ [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] ]
Izhod: 24
Pojasnilo:



ostri kot

Vnos: xs = 0 ys = 3 xd = 2 yd = 2
z [][] =[ [1 0 0 1 0]
[0 0 0 1 0]
[0 1 1 0 0] ]
Izhod: -1
Pojasnilo:
Vidimo, da je nemogoče
doseči celico (22) iz (03).

izberite več tabel sql

Kazalo vsebine



[Pristop] Uporaba sledenja nazaj z obiskano matriko

Ideja je uporaba Sledenje nazaj . Začnemo od izvorne celice matrike naprej v vse štiri dovoljene smeri in rekurzivno preverimo, ali vodijo do rešitve ali ne. Če je cilj najden, posodobimo vrednost najdaljše poti, sicer pa, če nobena od zgornjih rešitev ne deluje, iz naše funkcije vrnemo 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);

Izhod 
24

Časovna zapletenost: O(4^(m*n)) Za vsako celico v matriki m x n algoritem razišče do štiri možne smeri (gor dol levo desno), ki vodijo do eksponentnega števila poti. V najslabšem primeru razišče vse možne poti, kar povzroči časovno kompleksnost 4^(m*n).
Pomožni prostor: O(m*n) Algoritem uporablja matriko obiskanih m x n za sledenje obiskanim celicam in rekurzijski sklad, ki lahko v najslabšem primeru raste do globine m * n (npr. pri raziskovanju poti, ki pokriva vse celice). Tako je pomožni prostor O(m*n).

[Optimiziran pristop] Brez uporabe dodatnega prostora

Namesto vzdrževanja ločene obiskane matrike lahko ponovno uporabite vhodno matriko za označevanje obiskanih celic med prečkanjem. To prihrani dodaten prostor in še vedno zagotavlja, da ne obiščemo iste celice na poti.



k-nn algoritem

Spodaj je pristop po korakih:

  1. Začnite z izvorno celico(xs ys).
  2. Na vsakem koraku raziščite vse štiri možne smeri (desno navzdol levo navzgor).
  3. Za vsako veljavno potezo:
    • Preverite meje in zagotovite, da ima celica vrednost1(prosta celica).
    • Označite celico kot obiskano tako, da jo začasno nastavite na0.
    • Vrnite se v naslednjo celico in povečajte dolžino poti.
  4. Če ciljna celica(xd yd)je dosežena primerjajte trenutno dolžino poti z največjo do sedaj in posodobite odgovor.
  5. Nazaj: obnovi prvotno vrednost celice (1), preden se vrnete, da omogočite drugim potem, da ga raziščejo.
  6. Nadaljujte z raziskovanjem, dokler ne obiščete vseh možnih poti.
  7. Vrni največjo dolžino poti. Če je cilj nedosegljiv vrnitev-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);

Izhod 
24

Časovna zapletenost: O(4^(m*n))Algoritem še vedno raziskuje do štiri smeri na celico v matriki m x n, kar ima za posledico eksponentno število poti. Sprememba na mestu ne vpliva na število raziskanih poti, tako da časovna kompleksnost ostaja 4^(m*n).
Pomožni prostor: O(m*n) Medtem ko se obiskana matrika odstrani s spreminjanjem vhodne matrike na mestu, rekurzivni sklad še vedno zahteva O(m*n) prostora, saj je največja globina rekurzije lahko m * n v najslabšem primeru (npr. pot, ki obišče vse celice v mreži z večinoma 1s).