Dada una mat[][] de array 2d que consta de números enteros positivos, la tarea es encontrar el número mínimo de pasos necesarios para llegar al final de la array. Si estamos en la celda (i, j) podemos ir a las celdas (i, j + arr[i][j]) o (i + arr[i][j], j) . No podemos salirnos de los límites. Si no existe una ruta, imprima -1 .
Ejemplos:
Entrada: mat[][] = {
{2, 1, 2},
{1, 1, 1},
{1, 1, 1}}
Salida: 2
La ruta será {0, 0} -> {0, 2} -> {2, 2}
Por lo tanto, estamos llegando allí en dos pasos.
Entrada: mat[][] = {
{1, 1, 1},
{1, 1, 1},
{1, 1, 1}}
Salida: 4
Enfoque: Ya hemos discutido un enfoque basado en programación dinámica para este problema en este artículo. Este problema también se puede resolver utilizando la búsqueda primero en amplitud (BFS) .
El algoritmo es como sigue:
- Empuje (0, 0) en una cola.
- Traverse (0, 0), es decir, empuja todas las celdas que puede visitar en la cola.
- Repita los pasos anteriores, es decir, vuelva a recorrer todos los elementos de la cola individualmente si no se han visitado/recorrido antes.
- Repita hasta que no lleguemos a la celda (N-1, 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 2D.
¿Por qué funciona BFS?
- Todo este escenario puede considerarse equivalente a un gráfico dirigido en el que cada celda está conectada como máximo a dos celdas más ({i, j+arr[i][j]} y {i+arr[i][j], j}).
- El gráfico no está ponderado. BFS puede encontrar el camino más corto en tales escenarios.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#define n 3
using namespace std;
// Function to return the minimum steps
// required to reach the end of the matrix
int minSteps(int arr[][n])
{
// Array to determine whether
// a cell has been visited before
bool v[n][n] = { 0 };
// Queue for bfs
queue<pair<int, int> > q;
// Initializing queue
q.push({ 0, 0 });
// 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
pair<int, int> y = q.front();
// To store index of cell
// for simplicity
int i = y.first, j = y.second;
q.pop();
// Base case
if (v[i][j])
continue;
// If we reach (n-1, n-1)
if (i == n - 1 && j == n - 1)
return depth;
// Marking the cell visited
v[i][j] = 1;
// Pushing the adjacent cells in the
// queue that can be visited
// from the current cell
if (i + arr[i][j] < n)
q.push({ i + arr[i][j], j });
if (j + arr[i][j] < n)
q.push({ i, j + arr[i][j] });
}
depth++;
}
return -1;
}
// Driver code
int main()
{
int arr[n][n] = { { 1, 1, 1 },
{ 1, 1, 1 },
{ 1, 1, 1 } };
cout << minSteps(arr);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int n= 3 ;
static class Pair
{
int first , second;
Pair(int a, int b)
{
first = a;
second = b;
}
}
// Function to return the minimum steps
// required to reach the end of the matrix
static int minSteps(int arr[][])
{
// Array to determine whether
// a cell has been visited before
boolean v[][] = new boolean[n][n];
// Queue for bfs
Queue<Pair> q = new LinkedList<Pair>();
// Initializing queue
q.add(new Pair( 0, 0 ));
// 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
Pair y = q.peek();
// To store index of cell
// for simplicity
int i = y.first, j = y.second;
q.remove();
// Base case
if (v[i][j])
continue;
// If we reach (n-1, n-1)
if (i == n - 1 && j == n - 1)
return depth;
// Marking the cell visited
v[i][j] = true;
// Pushing the adjacent cells in the
// queue that can be visited
// from the current cell
if (i + arr[i][j] < n)
q.add(new Pair( i + arr[i][j], j ));
if (j + arr[i][j] < n)
q.add(new Pair( i, j + arr[i][j] ));
}
depth++;
}
return -1;
}
// Driver code
public static void main(String args[])
{
int arr[][] = { { 1, 1, 1 },
{ 1, 1, 1 },
{ 1, 1, 1 } };
System.out.println(minSteps(arr));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python 3 implementation of the approach n = 3 # Function to return the minimum steps # required to reach the end of the matrix def minSteps(arr): # Array to determine whether # a cell has been visited before v = [[0 for i in range(n)] for j in range(n)] # Queue for bfs q = [[0,0]] # To store the depth of search depth = 0 # BFS algorithm while (len(q) != 0): # Current queue size x = len(q) while (x > 0): # Top-most element of queue y = q[0] # To store index of cell # for simplicity i = y[0] j = y[1] q.remove(q[0]) x -= 1 # Base case if (v[i][j]): continue # If we reach (n-1, n-1) if (i == n - 1 and j == n - 1): return depth # Marking the cell visited v[i][j] = 1 # Pushing the adjacent cells in the # queue that can be visited # from the current cell if (i + arr[i][j] < n): q.append([i + arr[i][j], j]) if (j + arr[i][j] < n): q.append([i, j + arr[i][j]]) depth += 1 return -1 # Driver code if __name__ == '__main__': arr = [[1, 1, 1], [1, 1, 1], [1, 1, 1]] print(minSteps(arr)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static int n= 3 ;
public class Pair
{
public int first , second;
public Pair(int a, int b)
{
first = a;
second = b;
}
}
// Function to return the minimum steps
// required to reach the end of the matrix
static int minSteps(int [,]arr)
{
// Array to determine whether
// a cell has been visited before
Boolean [,]v = new Boolean[n,n];
// Queue for bfs
Queue<Pair> q = new Queue<Pair>();
// Initializing queue
q.Enqueue(new Pair( 0, 0 ));
// 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
Pair y = q.Peek();
// To store index of cell
// for simplicity
int i = y.first, j = y.second;
q.Dequeue();
// Base case
if (v[i,j])
continue;
// If we reach (n-1, n-1)
if (i == n - 1 && j == n - 1)
return depth;
// Marking the cell visited
v[i,j] = true;
// Pushing the adjacent cells in the
// queue that can be visited
// from the current cell
if (i + arr[i,j] < n)
q.Enqueue(new Pair( i + arr[i,j], j ));
if (j + arr[i,j] < n)
q.Enqueue(new Pair( i, j + arr[i,j] ));
}
depth++;
}
return -1;
}
// Driver code
public static void Main()
{
int [,]arr = { { 1, 1, 1 },
{ 1, 1, 1 },
{ 1, 1, 1 } };
Console.WriteLine(minSteps(arr));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
var n = 3;
// Function to return the minimum steps
// required to reach the end of the matrix
function minSteps(arr)
{
// Array to determine whether
// a cell has been visited before
var v = Array.from(Array(n), ()=> Array(n).fill(0));
// Queue for bfs
var q = [];
// Initializing queue
q.push([0, 0 ]);
// 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 y = q[0];
// To store index of cell
// for simplicity
var i = y[0], j = y[1];
q.shift();
// Base case
if (v[i][j])
continue;
// If we reach (n-1, n-1)
if (i == n - 1 && j == n - 1)
return depth;
// Marking the cell visited
v[i][j] = 1;
// Pushing the adjacent cells in the
// queue that can be visited
// from the current cell
if (i + arr[i][j] < n)
q.push([ i + arr[i][j], j ]);
if (j + arr[i][j] < n)
q.push([i, j + arr[i][j] ]);
}
depth++;
}
return -1;
}
// Driver code
var arr = [ [ 1, 1, 1 ],
[ 1, 1, 1 ],
[ 1, 1, 1 ] ];
document.write( minSteps(arr));
</script>
Producción:
4
Complejidad temporal: O(n 2 )
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA