Gitt en rektangulær matrise mat[][] der noen celler inneholder landminer (angitt med 0) og resten er trygge (angitt med 1), finn lengden på den korteste sikre ruten fra en celle i den første kolonnen til en hvilken som helst celle i den siste kolonnen.
- Landminer er utrygge og deres fire tilstøtende celler (opp ned til venstre til høyre) er også utrygge.
- Kun horisontale og vertikale bevegelser til tilstøtende trygge celler er tillatt.
- Hvis det er umulig å nå den siste kolonnen, returner -1 trygt.
Eksempler:
Inndata:
med[][] = [ [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] ]
Produksjon: 6
Forklaring:
Vi kan se den korteste lengden
sikker rute er 6.
Inndata:
med[][] = [ [1 1 1 1 1]
[1 1 0 1 1]
[1 1 1 1 1] ]
Produksjon: -1
Forklaring: Det er ingen mulig vei fra
første kolonne til siste kolonne.
Innholdsfortegnelse
[Tilnærming] Bruke tilbakesporing
C++Tanken er å bruke Tilbakesporing . Vi merker først alle tilstøtende celler til landminene som usikre. Så for hver sikker celle i første kolonne i matrisen beveger vi oss fremover i alle tillatte retninger og sjekker rekursivt om de fører til destinasjonen eller ikke. Hvis destinasjonen blir funnet, oppdaterer vi verdien av korteste vei ellers hvis ingen av løsningene ovenfor fungerer, returnerer vi false fra funksjonen vår.
#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);
Produksjon
6
Tidskompleksitet: O(4^(r * c)) hvor r er antall rader og c er antall kolonner i den gitte matrisen.
Hjelpeplass: O(r * c) ettersom vi bruker ekstra plass som visted[r][c].
[Optimalisert tilnærming] Bruke Breadth-First Search
C++Det kan løses i polynomisk tid ved å bruke Breadth-First Search. Sett alle sikre celler fra den siste kolonnen i kø i køen med avstand = 1. Når BFS fortsetter, beregnes den korteste veien til hver celle fra den siste kolonnen. Til slutt, blant alle tilgjengelige celler i den første kolonnen, skriver du ut minimumsavstanden.
#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);
Produksjon
6
Tidskompleksitet: O(r * c) hvor r og c er antall rader og kolonner i den gitte matrisen.
Hjelpeplass: O(r * c)