Je dána obdélníková matice mat[][] kde některé buňky obsahují nášlapné miny (označené 0) a ostatní jsou bezpečné (označené 1), najděte délku nejkratší bezpečné cesty z libovolné buňky v prvním sloupci do libovolné buňky v posledním sloupci.
- Nášlapné miny nejsou bezpečné a jejich čtyři sousední buňky (nahoře dole vlevo vpravo) jsou také nebezpečné.
- Jsou povoleny pouze horizontální a vertikální přesuny do sousedních bezpečných buněk.
- Pokud není možné bezpečně dosáhnout posledního sloupce, vraťte -1.
Příklady:
repl v Javě
Vstup:
s[][] = [ [1 0 1 1 1]
[1 1 1 1 1]
[1 1 1 1 1]
[1 1 1 0 1]
[1 1 1 1 0] ]
výstup: 6
Vysvětlení:
Vidíme tu nejkratší délku
bezpečná cesta je 6.
Vstup:
s[][] = [ [1 1 1 1 1]
[1 1 0 1 1]
[1 1 1 1 1] ]
výstup: -1
Vysvětlení: Neexistuje žádná možná cesta z
od prvního sloupce k poslednímu sloupci.
Obsah
smazat poslední commit git
[Přístup] Použití Backtracking
C++Myšlenka je použít Zpětné sledování . Nejprve označíme všechny sousední buňky nášlapných min jako nebezpečné. Poté pro každou bezpečnou buňku prvního sloupce matice postupujeme vpřed všemi povolenými směry a rekurzivně kontrolujeme, zda vedou k cíli nebo ne. Pokud je cíl nalezen, aktualizujeme hodnotu nejkratší cesty, jinak pokud žádné z výše uvedených řešení nefunguje, vrátíme z naší funkce hodnotu false.
#include
import java.util.Arrays; class Solution { // Function to mark unsafe cells (landmines and their adjacent cells) private void markUnsafeCells(int[][] mat) { int r = mat.length; int c = mat[0].length; int[] row = {-1 1 0 0}; int[] col = {0 0 -1 1}; // Create a copy to avoid modifying original safe cells prematurely int[][] temp = new int[r][c]; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { temp[i][j] = mat[i][j]; } } // Mark adjacent cells of landmines (0) as unsafe (0) for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (temp[i][j] == 0) { for (int k = 0; k < 4; k++) { int ni = i + row[k]; int nj = j + col[k]; if (ni >= 0 && ni < r && nj >= 0 && nj < c) { mat[ni][nj] = 0; } } } } } } // DFS to find shortest path from (i j) to any cell in last column private int dfs(int[][] mat boolean[][] visited int i int j int c) { int r = mat.length; // If out of bounds blocked or visited if (i < 0 || i >= r || j < 0 || j >= c || mat[i][j] == 0 || visited[i][j]) { return Integer.MAX_VALUE; } if (j == c - 1) { return 1; } visited[i][j] = true; int[] row = {-1 1 0 0}; int[] col = {0 0 -1 1}; int minPath = Integer.MAX_VALUE; // Try all four directions for (int k = 0; k < 4; k++) { int ni = i + row[k]; int nj = j + col[k]; int pathLength = dfs(mat visited ni nj c); if (pathLength != Integer.MAX_VALUE) { minPath = Math.min(minPath 1 + pathLength); } } // Backtrack - unmark current cell visited[i][j] = false; return minPath; } public int findShortestPath(int[][] mat) { int r = mat.length; int c = mat[0].length; // Mark all adjacent cells of landmines as unsafe markUnsafeCells(mat); boolean[][] visited = new boolean[r][c]; int minPath = Integer.MAX_VALUE; // Try starting from each safe cell in the first column for (int i = 0; i < r; i++) { if (mat[i][0] == 1) { int pathLength = dfs(mat visited i 0 c); if (pathLength != Integer.MAX_VALUE) { minPath = Math.min(minPath pathLength); } } } return minPath == Integer.MAX_VALUE ? -1 : minPath; } public static void main(String[] args) { int[][] mat = { {1 0 1 1 1} {1 1 1 1 1} {1 1 1 1 1} {1 1 1 0 1} {1 1 1 1 0} }; Solution solution = new Solution(); int result = solution.findShortestPath(mat); System.out.println(result); } }
# Function to mark unsafe cells (landmines and their adjacent cells) def mark_unsafe_cells(mat): r = len(mat) c = len(mat[0]) # Directions for adjacent cells: up down left right row = [-1 1 0 0] col = [0 0 -1 1] # Create a copy to avoid modifying original safe cells prematurely temp = [row[:] for row in mat] # Mark adjacent cells of landmines (0) as unsafe (0) for i in range(r): for j in range(c): if temp[i][j] == 0: for k in range(4): ni = i + row[k] nj = j + col[k] if 0 <= ni < r and 0 <= nj < c: mat[ni][nj] = 0 # DFS to find shortest path from (i j) to any cell in last column def dfs(mat visited i j c): r = len(mat) # If out of bounds blocked or visited if i < 0 or i >= r or j < 0 or j >= c or mat[i][j] == 0 or visited[i][j]: return float('inf') if j == c - 1: return 1 visited[i][j] = True # Four possible moves: up down left right row = [-1 1 0 0] col = [0 0 -1 1] min_path = float('inf') # Try all four directions for k in range(4): ni = i + row[k] nj = j + col[k] path_length = dfs(mat visited ni nj c) if path_length != float('inf'): min_path = min(min_path 1 + path_length) # Backtrack - unmark current cell visited[i][j] = False return min_path def findShortestPath(mat): r = len(mat) c = len(mat[0]) # Mark all adjacent cells of landmines as unsafe mark_unsafe_cells(mat) visited = [[False] * c for _ in range(r)] min_path = float('inf') # Try starting from each safe cell in the first column for i in range(r): if mat[i][0] == 1: path_length = dfs(mat visited i 0 c) if path_length != float('inf'): min_path = min(min_path path_length) return -1 if min_path == float('inf') else min_path def main(): mat = [ [1 0 1 1 1] [1 1 1 1 1] [1 1 1 1 1] [1 1 1 0 1] [1 1 1 1 0] ] result = findShortestPath(mat) print(result) if __name__ == '__main__': main()
using System; class GFG { // Function to mark unsafe cells (landmines and their adjacent cells) private void MarkUnsafeCells(int[][] mat) { int r = mat.Length; int c = mat[0].Length; // Directions for adjacent cells: up down left right int[] row = { -1 1 0 0 }; int[] col = { 0 0 -1 1 }; // Create a copy to avoid modifying original safe cells prematurely int[][] temp = new int[r][]; for (int i = 0; i < r; i++) { temp[i] = new int[c]; Array.Copy(mat[i] temp[i] c); } // Mark adjacent cells of landmines (0) as unsafe (0) for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (temp[i][j] == 0) { for (int k = 0; k < 4; k++) { int ni = i + row[k]; int nj = j + col[k]; if (ni >= 0 && ni < r && nj >= 0 && nj < c) { mat[ni][nj] = 0; } } } } } } // DFS to find shortest path from (i j) to any cell in last column private int Dfs(int[][] mat bool[][] visited int i int j int c) { int r = mat.Length; // If out of bounds blocked or visited if (i < 0 || i >= r || j < 0 || j >= c || mat[i][j] == 0 || visited[i][j]) { return int.MaxValue; } if (j == c - 1) { return 1; } visited[i][j] = true; int[] row = { -1 1 0 0 }; int[] col = { 0 0 -1 1 }; int minPath = int.MaxValue; // Try all four directions for (int k = 0; k < 4; k++) { int ni = i + row[k]; int nj = j + col[k]; int pathLength = Dfs(mat visited ni nj c); if (pathLength != int.MaxValue) { minPath = Math.Min(minPath 1 + pathLength); } } // Backtrack - unmark current cell visited[i][j] = false; return minPath; } public int FindShortestPath(int[][] mat) { int r = mat.Length; int c = mat[0].Length; // Mark all adjacent cells of landmines as unsafe MarkUnsafeCells(mat); bool[][] visited = new bool[r][]; for (int i = 0; i < r; i++) { visited[i] = new bool[c]; } int minPath = int.MaxValue; // Try starting from each safe cell in the first column for (int i = 0; i < r; i++) { if (mat[i][0] == 1) { int pathLength = Dfs(mat visited i 0 c); if (pathLength != int.MaxValue) { minPath = Math.Min(minPath pathLength); } } } return minPath == int.MaxValue ? -1 : minPath; } static void Main(string[] args) { int[][] mat = new int[][] { new int[] { 1 0 1 1 1 } new int[] { 1 1 1 1 1 } new int[] { 1 1 1 1 1 } new int[] { 1 1 1 0 1 } new int[] { 1 1 1 1 0 } }; GFG solution = new GFG(); int result = solution.FindShortestPath(mat); Console.WriteLine(result); } }
function markUnsafeCells(mat) { const r = mat.length; const c = mat[0].length; // Directions for adjacent cells: up down left right const row = [-1 1 0 0]; const col = [0 0 -1 1]; // Create a copy to avoid modifying original safe cells prematurely const temp = mat.map(row => [...row]); // Mark adjacent cells of landmines (0) as unsafe (0) for (let i = 0; i < r; i++) { for (let j = 0; j < c; j++) { if (temp[i][j] === 0) { for (let k = 0; k < 4; k++) { const ni = i + row[k]; const nj = j + col[k]; if (ni >= 0 && ni < r && nj >= 0 && nj < c) { mat[ni][nj] = 0; } } } } } } function dfs(mat visited i j c) { const r = mat.length; // If out of bounds blocked or visited if (i < 0 || i >= r || j < 0 || j >= c || mat[i][j] === 0 || visited[i][j]) { return Infinity; } // If reached the last column if (j === c - 1) { return 1; } visited[i][j] = true; const row = [-1 1 0 0]; const col = [0 0 -1 1]; let minPath = Infinity; // Try all four directions for (let k = 0; k < 4; k++) { const ni = i + row[k]; const nj = j + col[k]; const pathLength = dfs(mat visited ni nj c); if (pathLength !== Infinity) { minPath = Math.min(minPath 1 + pathLength); } } // Backtrack - unmark current cell visited[i][j] = false; return minPath; } function findShortestPath(mat) { const r = mat.length; const c = mat[0].length; // Mark all adjacent cells of landmines as unsafe markUnsafeCells(mat); const visited = Array(r).fill().map(() => Array(c).fill(false)); let minPath = Infinity; // Try starting from each safe cell in the first column for (let i = 0; i < r; i++) { if (mat[i][0] === 1) { const pathLength = dfs(mat visited i 0 c); if (pathLength !== Infinity) { minPath = Math.min(minPath pathLength); } } } return minPath === Infinity ? -1 : minPath; } const mat = [ [1 0 1 1 1] [1 1 1 1 1] [1 1 1 1 1] [1 1 1 0 1] [1 1 1 1 0] ]; const result = findShortestPath(mat); console.log(result);
Výstup
6
Časová náročnost: O(4^(r * c)) kde r je počet řádků a c je počet sloupců v dané matici.
Pomocný prostor: O(r * c) protože využíváme prostor navíc jako visted[r][c].
hostitelský linux
[Optimalizovaný přístup] Pomocí vyhledávání napřed
C++Lze to vyřešit v polynomiálním čase pomocí Breadth-First Search. Všechny bezpečné buňky z posledního sloupce zařaďte do fronty se vzdáleností = 1. Při postupu BFS se vypočítá nejkratší cesta ke každé buňce z posledního sloupce. Nakonec ze všech dosažitelných buněk v prvním sloupci uveďte minimální vzdálenost.
#include
import java.util.*; public class Solution { static int[] rowNum = {-1 0 0 1}; static int[] colNum = {0 -1 1 0}; public static int findShortestPath(int[][] mat) { int n = mat.length; int m = mat[0].length; Queue<int[]> q = new LinkedList<>(); int[][] d = new int[n][m]; // Initializing distance array with large values for (int i = 0; i < n; i++) { Arrays.fill(d[i] (int) 1e9); } // Lambda-like helper function: check if cell is valid java.util.function.BiFunction<Integer Integer Boolean> isValid = (i j) -> { return !(i < 0 || i >= n || j < 0 || j >= m); }; // Helper function: check if cell and adjacent cells are safe java.util.function.BiFunction<Integer Integer Boolean> check = (i j) -> { if (!isValid.apply(i j)) return false; for (int k = 0; k < 4; k++) { int ni = i + rowNum[k]; int nj = j + colNum[k]; if (isValid.apply(ni nj) && mat[ni][nj] == 0) return false; } return true; }; // Pushing cells from the rightmost column into the queue for (int i = 0; i < n; i++) { if (check.apply(i m - 1)) { q.add(new int[]{i m - 1 1}); } } // BFS traversal while (!q.isEmpty()) { int[] z = q.poll(); int x = z[0] y = z[1] dis = z[2]; if (d[x][y] > dis) { d[x][y] = dis; for (int k = 0; k < 4; k++) { int ni = x + rowNum[k]; int nj = y + colNum[k]; if (check.apply(ni nj)) { q.add(new int[]{ni nj dis + 1}); } } } } // Finding the minimum distance in the first column int ans = (int) 1e9; for (int i = 0; i < n; i++) { ans = Math.min(ans d[i][0]); } // If no safe path found return -1 if (ans >= 1e9) ans = -1; return ans; } public static void main(String[] args) { int[][] mat = { {1 0 1 1 1} {1 1 1 1 1} {1 1 1 1 1} {1 1 1 0 1} {1 1 1 1 0} }; int result = findShortestPath(mat); System.out.println(result); } }
from collections import deque rowNum = [-1 0 0 1] colNum = [0 -1 1 0] def findShortestPath(mat): n = len(mat) m = len(mat[0]) q = deque() d = [[10**9 for _ in range(m)] for _ in range(n)] # Check if cell is valid def isValid(i j): return not (i < 0 or i >= n or j < 0 or j >= m) # Check if cell and its adjacent cells are safe def check(i j): if not isValid(i j): return False for k in range(4): ni nj = i + rowNum[k] j + colNum[k] if isValid(ni nj) and mat[ni][nj] == 0: return False return True # Pushing cells from the rightmost column into the queue for i in range(n): if check(i m - 1): q.append((i m - 1 1)) # BFS traversal while q: x y dis = q.popleft() if d[x][y] > dis: d[x][y] = dis for k in range(4): ni nj = x + rowNum[k] y + colNum[k] if check(ni nj): q.append((ni nj dis + 1)) # Finding the minimum distance in the first column ans = min(d[i][0] for i in range(n)) # If no safe path found return -1 if ans >= 10**9: ans = -1 return ans if __name__ == '__main__': mat = [ [1 0 1 1 1] [1 1 1 1 1] [1 1 1 1 1] [1 1 1 0 1] [1 1 1 1 0] ] result = findShortestPath(mat) print(result)
using System; using System.Collections.Generic; class Solution { static int[] rowNum = { -1 0 0 1 }; static int[] colNum = { 0 -1 1 0 }; // Check if cell is valid static bool IsValid(int i int j int n int m) { return !(i < 0 || i >= n || j < 0 || j >= m); } // Check if cell and its adjacent cells are safe static bool Check(int i int j int[][] mat int n int m) { if (!IsValid(i j n m)) return false; for (int k = 0; k < 4; k++) { int ni = i + rowNum[k]; int nj = j + colNum[k]; if (IsValid(ni nj n m) && mat[ni][nj] == 0) return false; } return true; } public static int FindShortestPath(int[][] mat) { int n = mat.Length; int m = mat[0].Length; Queue<(int int int)> q = new Queue<(int int int)>(); int[] d = new int[n m]; // Initialize distance array with large value for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) d[i j] = int.MaxValue / 2; // Push safe cells from rightmost column for (int i = 0; i < n; i++) { if (Check(i m - 1 mat n m)) { q.Enqueue((i m - 1 1)); } } // BFS traversal while (q.Count > 0) { var (x y dis) = q.Dequeue(); if (d[x y] > dis) { d[x y] = dis; for (int k = 0; k < 4; k++) { int ni = x + rowNum[k]; int nj = y + colNum[k]; if (Check(ni nj mat n m)) { q.Enqueue((ni nj dis + 1)); } } } } // Find minimum distance in the first column int ans = int.MaxValue / 2; for (int i = 0; i < n; i++) ans = Math.Min(ans d[i 0]); return ans >= int.MaxValue / 2 ? -1 : ans; } static void Main() { int[][] mat = new int[][] { new int[] {1 0 1 1 1} new int[] {1 1 1 1 1} new int[] {1 1 1 1 1} new int[] {1 1 1 0 1} new int[] {1 1 1 1 0} }; int result = FindShortestPath(mat); Console.WriteLine(result); } }
function findShortestPath(mat) { const n = mat.length; const m = mat[0].length; const rowNum = [-1 0 0 1]; const colNum = [0 -1 1 0]; // Distance matrix initialized to large value const d = Array.from({ length: n } () => Array(m).fill(Number.MAX_SAFE_INTEGER)); // Check if cell is valid function isValid(i j) { return !(i < 0 || i >= n || j < 0 || j >= m); } // Check if cell and its adjacent cells are safe function check(i j) { if (!isValid(i j)) return false; for (let k = 0; k < 4; k++) { let ni = i + rowNum[k]; let nj = j + colNum[k]; if (isValid(ni nj) && mat[ni][nj] === 0) return false; } return true; } // Queue for BFS let q = []; // Push safe cells from rightmost column for (let i = 0; i < n; i++) { if (check(i m - 1)) { q.push([i m - 1 1]); } } // BFS traversal while (q.length > 0) { let [x y dis] = q.shift(); if (d[x][y] > dis) { d[x][y] = dis; for (let k = 0; k < 4; k++) { let ni = x + rowNum[k]; let nj = y + colNum[k]; if (check(ni nj)) { q.push([ni nj dis + 1]); } } } } // Find minimum distance in first column let ans = Number.MAX_SAFE_INTEGER; for (let i = 0; i < n; i++) { ans = Math.min(ans d[i][0]); } return ans >= Number.MAX_SAFE_INTEGER ? -1 : ans; } const mat = [ [1 0 1 1 1] [1 1 1 1 1] [1 1 1 1 1] [1 1 1 0 1] [1 1 1 1 0] ]; const result = findShortestPath(mat); console.log(result);
Výstup
6
Časová náročnost: O(r * c) kde r a c jsou počet řádků a sloupců v dané matici.
Pomocný prostor: O(r * c)