Data una griglia 2D di dimensioni n*n dove ogni cella rappresenta il costo per attraversare quella cella, il compito è trovare il costo minimo per spostarsi da in alto a sinistra cella al in basso a destra cella. Da una determinata cella possiamo entrare 4 direzioni : sinistra destra su giù.
Nota: Si presuppone che non esistano cicli di costo negativi nella matrice di input.
array di byte Java in stringa
Esempio:
Ingresso: griglia = {{9 4 9 9}
{6 7 6 4}
{8 3 3 7}
{7 4 9 10}}
Produzione: 43
Spiegazione: Il percorso di costo minimo è 9 + 4 + 7 + 3 + 3 + 7 + 10.
Approccio:
L'idea è usare Algoritmo di Dijkstra per trovare il percorso di costo minimo attraverso la griglia. Questo approccio tratta la griglia come un grafico in cui ogni cella è un nodo e l'algoritmo esplora dinamicamente il percorso più conveniente verso la cella in basso a destra espandendo sempre per primi i percorsi dal costo più basso.
Approccio passo dopo passo:
Java altrimenti se
- Utilizzare un heap minimo per elaborare sempre per primo il percorso dal costo più basso e inserirvi la cella in alto a sinistra.
- Inizializza una matrice di costo con valori massimi impostando il costo della cella iniziale sul relativo valore griglia.
- Per ogni cella controlla tutte e 4 le celle vicine
- Se viene trovato un percorso a costo inferiore, aggiorna il costo della cella e inseriscila nell'heap.
- Restituisce il costo minimo per raggiungere la cella in basso a destra.
Di seguito è riportata l’implementazione dell’approccio di cui sopra:
C++// C++ program to find minimum Cost Path with // Left Right Bottom and Up moves allowed #include
// Java program to find minimum Cost Path with // Left Right Bottom and Up moves allowed import java.util.PriorityQueue; import java.util.Arrays; class GfG { // Function to check if cell is valid. static boolean isValidCell(int i int j int n) { return i >= 0 && i < n && j >= 0 && j < n; } static int minimumCostPath(int[][] grid) { int n = grid.length; // Min heap to implement Dijkstra PriorityQueue<int[]> pq = new PriorityQueue<>((a b) -> Integer.compare(a[0] b[0])); // 2D grid to store minimum cost // to reach every cell. int[][] cost = new int[n][n]; for (int[] row : cost) { Arrays.fill(row Integer.MAX_VALUE); } cost[0][0] = grid[0][0]; // Direction vector to move in 4 directions int[][] dir = {{-1 0} {1 0} {0 -1} {0 1}}; pq.offer(new int[]{grid[0][0] 0 0}); while (!pq.isEmpty()) { int[] top = pq.poll(); int c = top[0] i = top[1] j = top[2]; // Check for all 4 neighbouring cells. for (int[] d : dir) { int x = i + d[0]; int y = j + d[1]; // If cell is valid and cost to reach this cell // from current cell is less if (isValidCell(x y n) && cost[i][j] + grid[x][y] < cost[x][y]) { // Update cost to reach this cell. cost[x][y] = cost[i][j] + grid[x][y]; // Push the cell into heap. pq.offer(new int[]{cost[x][y] x y}); } } } // Return minimum cost to // reach bottom right cell. return cost[n - 1][n - 1]; } public static void main(String[] args) { int[][] grid = { {9 4 9 9} {6 7 6 4} {8 3 3 7} {7 4 9 10} }; System.out.println(minimumCostPath(grid)); } }
# Python program to find minimum Cost Path with # Left Right Bottom and Up moves allowed import heapq # Function to check if cell is valid. def isValidCell(i j n): return i >= 0 and i < n and j >= 0 and j < n def minimumCostPath(grid): n = len(grid) # Min heap to implement Dijkstra pq = [] # 2D grid to store minimum cost # to reach every cell. cost = [[float('inf')] * n for _ in range(n)] cost[0][0] = grid[0][0] # Direction vector to move in 4 directions dir = [[-1 0] [1 0] [0 -1] [0 1]] heapq.heappush(pq [grid[0][0] 0 0]) while pq: c i j = heapq.heappop(pq) # Check for all 4 neighbouring cells. for d in dir: x y = i + d[0] j + d[1] # If cell is valid and cost to reach this cell # from current cell is less if isValidCell(x y n) and cost[i][j] + grid[x][y] < cost[x][y]: # Update cost to reach this cell. cost[x][y] = cost[i][j] + grid[x][y] # Push the cell into heap. heapq.heappush(pq [cost[x][y] x y]) # Return minimum cost to # reach bottom right cell. return cost[n - 1][n - 1] if __name__ == '__main__': grid = [ [9 4 9 9] [6 7 6 4] [8 3 3 7] [7 4 9 10] ] print(minimumCostPath(grid))
// C# program to find minimum Cost Path with // Left Right Bottom and Up moves allowed using System; using System.Collections.Generic; class GfG { // Function to check if cell is valid. static bool isValidCell(int i int j int n) { return i >= 0 && i < n && j >= 0 && j < n; } static int minimumCostPath(int[][] grid) { int n = grid.Length; // Min heap to implement Dijkstra var pq = new SortedSet<(int cost int x int y)>(); // 2D grid to store minimum cost // to reach every cell. int[][] cost = new int[n][]; for (int i = 0; i < n; i++) { cost[i] = new int[n]; Array.Fill(cost[i] int.MaxValue); } cost[0][0] = grid[0][0]; // Direction vector to move in 4 directions int[][] dir = { new int[] {-1 0} new int[] {1 0} new int[] {0 -1} new int[] {0 1} }; pq.Add((grid[0][0] 0 0)); while (pq.Count > 0) { var top = pq.Min; pq.Remove(top); int i = top.x j = top.y; // Check for all 4 neighbouring cells. foreach (var d in dir) { int x = i + d[0]; int y = j + d[1]; // If cell is valid and cost to reach this cell // from current cell is less if (isValidCell(x y n) && cost[i][j] + grid[x][y] < cost[x][y]) { // Update cost to reach this cell. cost[x][y] = cost[i][j] + grid[x][y]; // Push the cell into heap. pq.Add((cost[x][y] x y)); } } } // Return minimum cost to // reach bottom right cell. return cost[n - 1][n - 1]; } static void Main(string[] args) { int[][] grid = new int[][] { new int[] {9 4 9 9} new int[] {6 7 6 4} new int[] {8 3 3 7} new int[] {7 4 9 10} }; Console.WriteLine(minimumCostPath(grid)); } }
// JavaScript program to find minimum Cost Path with // Left Right Bottom and Up moves allowed function comparator(a b) { if (a[0] > b[0]) return -1; if (a[0] < b[0]) return 1; return 0; } class PriorityQueue { constructor(compare) { this.heap = []; this.compare = compare; } enqueue(value) { this.heap.push(value); this.bubbleUp(); } bubbleUp() { let index = this.heap.length - 1; while (index > 0) { let element = this.heap[index] parentIndex = Math.floor((index - 1) / 2) parent = this.heap[parentIndex]; if (this.compare(element parent) < 0) break; this.heap[index] = parent; this.heap[parentIndex] = element; index = parentIndex; } } dequeue() { let max = this.heap[0]; let end = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = end; this.sinkDown(0); } return max; } sinkDown(index) { let left = 2 * index + 1 right = 2 * index + 2 largest = index; if ( left < this.heap.length && this.compare(this.heap[left] this.heap[largest]) > 0 ) { largest = left; } if ( right < this.heap.length && this.compare(this.heap[right] this.heap[largest]) > 0 ) { largest = right; } if (largest !== index) { [this.heap[largest] this.heap[index]] = [ this.heap[index] this.heap[largest] ]; this.sinkDown(largest); } } isEmpty() { return this.heap.length === 0; } } // Function to check if cell is valid. function isValidCell(i j n) { return i >= 0 && i < n && j >= 0 && j < n; } function minimumCostPath(grid) { let n = grid.length; // Min heap to implement Dijkstra const pq = new PriorityQueue(comparator) // 2D grid to store minimum cost // to reach every cell. let cost = Array.from({ length: n } () => Array(n).fill(Infinity)); cost[0][0] = grid[0][0]; // Direction vector to move in 4 directions let dir = [[-1 0] [1 0] [0 -1] [0 1]]; pq.enqueue([grid[0][0] 0 0]); while (!pq.isEmpty()) { let [c i j] = pq.dequeue(); // Check for all 4 neighbouring cells. for (let d of dir) { let x = i + d[0]; let y = j + d[1]; // If cell is valid and cost to reach this cell // from current cell is less if (isValidCell(x y n) && cost[i][j] + grid[x][y] < cost[x][y]) { // Update cost to reach this cell. cost[x][y] = cost[i][j] + grid[x][y]; // Push the cell into heap. pq.enqueue([cost[x][y] x y]); } } } // Return minimum cost to // reach bottom right cell. return cost[n - 1][n - 1]; } let grid = [ [9 4 9 9] [6 7 6 4] [8 3 3 7] [7 4 9 10] ]; console.log(minimumCostPath(grid));
Produzione
43
Complessità temporale: O(n^2 log(n^2))
Spazio ausiliario: O(n^2 log(n^2))
Perché non è possibile utilizzare la programmazione dinamica?
La programmazione dinamica qui fallisce perché consentire il movimento in tutte e quattro le direzioni crea cicli in cui le cellule possono essere rivisitate rompendo il presupposto della sottostruttura ottimale. Ciò significa che il costo per raggiungere una cella da una determinata cella non è fisso ma dipende dall'intero percorso.
Articoli correlati:
Percorso costo minimo
Crea quiz