Дадена е 2D двоична матрица заедно с [][] където някои клетки са препятствия (обозначени с0), а останалите са свободни клетки (означени с1) вашата задача е да намерите дължината на най-дългия възможен маршрут от изходна клетка (xs ys) към целева клетка (xd yd) .
- Можете да се придвижвате само до съседни клетки (нагоре, надолу, наляво, надясно).
- Диагоналните движения не са разрешени.
- Клетка, посетена веднъж в дадена пътека, не може да бъде посетена отново в същата тази пътека.
- Ако е невъзможно да се стигне до местоназначението се върнете
-1.
Примери:
вход: xs = 0 ys = 0 xd = 1 yd = 7
с [][] = [ [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
Обяснение:
8 към 1 мултиплексор
вход: xs = 0 ys = 3 xd = 2 yd = 2
с[][] =[ [1 0 0 1 0]
[0 0 0 1 0]
[0 1 1 0 0] ]
Изход: -1
Обяснение:
Виждаме, че е невъзможно
достигнете клетката (22) от (03).
Съдържание
- [Подход] Използване на обратно проследяване с посетена матрица
- [Оптимизиран подход] Без използване на допълнително пространство
[Подход] Използване на обратно проследяване с посетена матрица
CPPИдеята е да се използва Обратно проследяване . Започваме от изходната клетка на матрицата, придвижваме се напред във всичките четири разрешени посоки и рекурсивно проверяваме дали водят до решението или не. Ако местоназначението бъде намерено, актуализираме стойността на най-дългия път, в противен случай, ако нито едно от горните решения не работи, връщаме 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^(m*n).
Помощно пространство: O(m*n) Алгоритъмът използва m x n посетена матрица за проследяване на посетени клетки и стек за рекурсия, който може да нарасне до дълбочина m * n в най-лошия случай (напр. при изследване на път, покриващ всички клетки). Така спомагателното пространство е O(m*n).
[Оптимизиран подход] Без използване на допълнително пространство
Вместо да поддържаме отделна посетена матрица, можем повторно използване на входната матрица за маркиране на посетените клетки по време на обхождането. Това спестява допълнително място и все още гарантира, че няма да преразгледаме същата клетка в пътя.
По-долу е подходът стъпка по стъпка:
- Започнете от изходната клетка
(xs ys). - На всяка стъпка изследвайте всичките четири възможни посоки (надясно надолу наляво нагоре).
- За всеки валиден ход:
- Проверете границите и се уверете, че клетката има стойност
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^(m*n).
Помощно пространство: O(m*n) Докато посетената матрица се елиминира чрез модифициране на входната матрица на място, стекът за рекурсия все още изисква O(m*n) пространство, тъй като максималната дълбочина на рекурсия може да бъде m * n в най-лошия случай (напр. път, посещаващ всички клетки в мрежа с предимно 1s).
java стойност на низ