Dada una array de enteros arr[] de longitud N que consta de enteros positivos, la tarea es minimizar el número de pasos necesarios para llegar a arr[N – 1] a partir de arr[0] . En un paso dado, si estamos en el índice i , podemos ir al índice i – arr[i] o i + arr[i] dado que no hemos visitado esos índices antes. Además, no podemos salirnos de los límites de la array. Imprime -1 si no hay forma posible.
Ejemplos:
Entrada: arr[] = {1, 1, 1}
Salida: 2
La ruta será 0 -> 1 -> 2.
Entrada: arr[] = {2, 1}
Salida: -1
Enfoque: Ya hemos discutido un enfoque basado en programación dinámica en este artículo que tiene una complejidad de tiempo de O(n * 2 n ) .
Aquí vamos a discutir una solución basada en BFS :
- Este problema se puede visualizar como un gráfico dirigido donde la i -ésima celda está conectada con las celdas i + arr[i] e i – arr[i] .
- Y el gráfico no está ponderado.
Debido a lo anterior, BFS se puede utilizar para encontrar la ruta más corta entre el índice 0 y el (N – 1) ésimo . Usaremos el siguiente algoritmo:
- Empuje el índice 0 en una cola.
- Empuje todas las celdas adyacentes a 0 en la cola.
- Repita los pasos anteriores, es decir, recorra todos los elementos de la cola individualmente de nuevo si no se han visitado/recorrido antes.
- Repita hasta que no alcancemos el índice N – 1 .
- La profundidad de este recorrido dará los pasos mínimos necesarios para llegar al final.
Recuerde marcar una celda visitada después de haberla recorrido. Para esto, usaremos una array booleana.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum steps
// required to reach the end
// of the given array
int minSteps(int arr[], int n)
{
// Array to determine whether
// a cell has been visited before
bool v[n] = { 0 };
// Queue for bfs
queue<int> q;
// Push the source i.e. index 0
q.push(0);
// Variable to store
// the depth of search
int depth = 0;
// BFS algorithm
while (q.size() != 0) {
// Current queue size
int x = q.size();
while (x--) {
// Top-most element of queue
int i = q.front();
q.pop();
// Base case
if (v[i])
continue;
// If we reach the destination
// i.e. index (n - 1)
if (i == n - 1)
return depth;
// Marking the cell visited
v[i] = 1;
// Pushing the adjacent nodes
// i.e. indices reachable
// from the current index
if (i + arr[i] < n)
q.push(i + arr[i]);
if (i - arr[i] >= 0)
q.push(i - arr[i]);
}
depth++;
}
return -1;
}
// Driver code
int main()
{
int arr[] = { 1, 1, 1, 1, 1, 1 };
int n = sizeof(arr) / sizeof(int);
cout << minSteps(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the minimum steps
// required to reach the end
// of the given array
static int minSteps(int arr[], int n)
{
// Array to determine whether
// a cell has been visited before
boolean[] v = new boolean[n];
// Queue for bfs
Queue<Integer> q = new LinkedList<>();
// Push the source i.e. index 0
q.add(0);
// Variable to store
// the depth of search
int depth = 0;
// BFS algorithm
while (q.size() > 0)
{
// Current queue size
int x = q.size();
while (x-- > 0)
{
// Top-most element of queue
int i = q.peek();
q.poll();
// Base case
if (v[i])
continue;
// If we reach the destination
// i.e. index (n - 1)
if (i == n - 1)
return depth;
// Marking the cell visited
v[i] = true;
// Pushing the adjacent nodes
// i.e. indices reachable
// from the current index
if (i + arr[i] < n)
q.add(i + arr[i]);
if (i - arr[i] >= 0)
q.add(i - arr[i]);
}
depth++;
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 1, 1, 1, 1, 1 };
int n = arr.length;
System.out.println(minSteps(arr, n));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python 3 implementation of the approach # Function to return the minimum steps # required to reach the end # of the given array def minSteps(arr,n): # Array to determine whether # a cell has been visited before v = [0 for i in range(n)] # Queue for bfs q = [] # Push the source i.e. index 0 q.append(0) # Variable to store # the depth of search depth = 0 # BFS algorithm while (len(q) != 0): # Current queue size x = len(q) while (x >= 1): # Top-most element of queue i = q[0] q.remove(i) x -= 1 # Base case if (v[i]): continue; # If we reach the destination # i.e. index (n - 1) if (i == n - 1): return depth # Marking the cell visited v[i] = 1 # Pushing the adjacent nodes # i.e. indices reachable # from the current index if (i + arr[i] < n): q.append(i + arr[i]) if (i - arr[i] >= 0): q.append(i - arr[i]) depth += 1 return -1 # Driver code if __name__ == '__main__': arr = [1, 1, 1, 1, 1, 1] n = len(arr) print(minSteps(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// A C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the minimum steps
// required to reach the end
// of the given array
static int minSteps(int []arr, int n)
{
// Array to determine whether
// a cell has been visited before
Boolean[] v = new Boolean[n];
// Queue for bfs
Queue<int> q = new Queue<int>();
// Push the source i.e. index 0
q.Enqueue(0);
// Variable to store
// the depth of search
int depth = 0;
// BFS algorithm
while (q.Count > 0)
{
// Current queue size
int x = q.Count;
while (x-- > 0)
{
// Top-most element of queue
int i = q.Peek();
q.Dequeue();
// Base case
if (v[i])
continue;
// If we reach the destination
// i.e. index (n - 1)
if (i == n - 1)
return depth;
// Marking the cell visited
v[i] = true;
// Pushing the adjacent nodes
// i.e. indices reachable
// from the current index
if (i + arr[i] < n)
q.Enqueue(i + arr[i]);
if (i - arr[i] >= 0)
q.Enqueue(i - arr[i]);
}
depth++;
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 1, 1, 1, 1, 1 };
int n = arr.Length;
Console.WriteLine(minSteps(arr, n));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum steps
// required to reach the end
// of the given array
function minSteps(arr, n)
{
// Array to determine whether
// a cell has been visited before
var v = Array(n).fill(0);
// Queue for bfs
var q = [];
// Push the source i.e. index 0
q.push(0);
// Variable to store
// the depth of search
var depth = 0;
// BFS algorithm
while (q.length != 0) {
// Current queue size
var x = q.length;
while (x--) {
// Top-most element of queue
var i = q[0];
q.shift();
// Base case
if (v[i])
continue;
// If we reach the destination
// i.e. index (n - 1)
if (i == n - 1)
return depth;
// Marking the cell visited
v[i] = 1;
// Pushing the adjacent nodes
// i.e. indices reachable
// from the current index
if (i + arr[i] < n)
q.push(i + arr[i]);
if (i - arr[i] >= 0)
q.push(i - arr[i]);
}
depth++;
}
return -1;
}
// Driver code
var arr = [1, 1, 1, 1, 1, 1];
var n = arr.length;
document.write( minSteps(arr, n));
</script>
Producción:
5
Complejidad del tiempo: O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA