Dada una array NXM, donde a i, j = 1 indica que la celda no está vacía, a i, j = 0 indica que la celda está vacía y a i, j = 2 indica que está parado en esa celda. Puede moverse verticalmente hacia arriba o hacia abajo y horizontalmente hacia la izquierda o hacia la derecha a cualquier celda que esté vacía. La tarea es encontrar el número mínimo de pasos para llegar a cualquier borde límite de la array. Imprima -1 si no es posible llegar a ninguno de los bordes del límite.
Nota : Solo habrá una celda con un valor de 2 en toda la array.
Ejemplos:
Input: matrix[] = {1, 1, 1, 0, 1}
{1, 0, 2, 0, 1}
{0, 0, 1, 0, 1}
{1, 0, 1, 1, 0}
Output: 2
Move to the right and then move
upwards to reach the nearest boundary
edge.
Input: matrix[] = {1, 1, 1, 1, 1}
{1, 0, 2, 0, 1}
{1, 0, 1, 0, 1}
{1, 1, 1, 1, 1}
Output: -1
Enfoque : el problema se puede resolver utilizando un enfoque de programación dinámica. A continuación se muestra el algoritmo para resolver el problema anterior.
- Encuentre la posición que tiene ‘2’ en la array.
- Inicialice dos arrays 2-D de tamaño igual que la array. El dp[][] que almacena el número mínimo de pasos para llegar a cualquier índice i, j y vis[][] marca si alguna posición i, j en particular ha sido visitada o no previamente.
- Llame a la función recursiva que tiene el caso base de la siguiente manera:
- si el recorrido en cualquier punto alcanza cualquiera de los bordes del límite, devuelva 0.
- si la posición de los puntos n, m ha almacenado el número mínimo de pasos previamente, entonces devuelve dp[n][m].
- Vuelva a llamar a la recursividad con los cuatro movimientos posibles que se pueden realizar desde la posición n, m. Los movimientos solo son posibles si mat[n][m] es 0 y la posición no ha sido visitada previamente.
- Guarda el mínimo de los cuatro movimientos.
- Si la recursión devuelve cualquier valor menor que 1e9, que habíamos almacenado como valor máximo, entonces hay una respuesta, de lo contrario no tiene respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find Minimum steps
// to reach any of the boundary
// edges of a matrix
#include <bits/stdc++.h>
using namespace std;
#define r 4
#define col 5
// Function to find out minimum steps
int findMinSteps(int mat[r][col], int n, int m, int dp[r][col], bool vis[r][col])
{
// boundary edges reached
if (n == 0 || m == 0 || n == (r - 1) || m == (col - 1)) {
return 0;
}
// already had a route through this
// point, hence no need to re-visit
if (dp[n][m] != -1)
return dp[n][m];
// visiting a position
vis[n][m] = true;
int ans1, ans2, ans3, ans4;
ans1 = ans2 = ans3 = ans4 = 1e9;
// vertically up
if (mat[n - 1][m] == 0) {
if (!vis[n - 1][m])
ans1 = 1 + findMinSteps(mat, n - 1, m, dp, vis);
}
// horizontally right
if (mat[n][m + 1] == 0) {
if (!vis[n][m + 1])
ans2 = 1 + findMinSteps(mat, n, m + 1, dp, vis);
}
// horizontally left
if (mat[n][m - 1] == 0) {
if (!vis[n][m - 1])
ans3 = 1 + findMinSteps(mat, n, m - 1, dp, vis);
}
// vertically down
if (mat[n + 1][m] == 0) {
if (!vis[n + 1][m])
ans4 = 1 + findMinSteps(mat, n + 1, m, dp, vis);
}
// minimum of every path
dp[n][m] = min(ans1, min(ans2, min(ans3, ans4)));
return dp[n][m];
}
// Function that returns the minimum steps
int minimumSteps(int mat[r][col], int n, int m)
{
// index to store the location at
// which you are standing
int twox = -1;
int twoy = -1;
// find '2' in the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 2) {
twox = i;
twoy = j;
break;
}
}
if (twox != -1)
break;
}
// Initialize dp matrix with -1
int dp[r][col];
memset(dp, -1, sizeof dp);
// Initialize vis matrix with false
bool vis[r][col];
memset(vis, false, sizeof vis);
// Call function to find out minimum steps
// using memoization and recursion
int res = findMinSteps(mat, twox, twoy, dp, vis);
// if not possible
if (res >= 1e9)
return -1;
else
return res;
}
// Driver Code
int main()
{
int mat[r][col] = { { 1, 1, 1, 0, 1 },
{ 1, 0, 2, 0, 1 },
{ 0, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 0 } };
cout << minimumSteps(mat, r, col);
}
Java
// Java program to find Minimum steps
// to reach any of the boundary
// edges of a matrix
class Solution
{
static final int r=4,c=5;
// Function to find out minimum steps
static int findMinSteps(int mat[][], int n, int m, int dp[][], boolean vis[][])
{
// boundary edges reached
if (n == 0 || m == 0 || n == (r - 1) || m == (c - 1)) {
return 0;
}
// already had a route through this
// point, hence no need to re-visit
if (dp[n][m] != -1)
return dp[n][m];
// visiting a position
vis[n][m] = true;
int ans1, ans2, ans3, ans4;
ans1 = ans2 = ans3 = ans4 = (int)1e9;
// vertically up
if (mat[n - 1][m] == 0) {
if (!vis[n - 1][m])
ans1 = 1 + findMinSteps(mat, n - 1, m, dp, vis);
}
// horizontally right
if (mat[n][m + 1] == 0) {
if (!vis[n][m + 1])
ans2 = 1 + findMinSteps(mat, n, m + 1, dp, vis);
}
// horizontally left
if (mat[n][m - 1] == 0) {
if (!vis[n][m - 1])
ans3 = 1 + findMinSteps(mat, n, m - 1, dp, vis);
}
// vertically down
if (mat[n + 1][m] == 0) {
if (!vis[n + 1][m])
ans4 = 1 + findMinSteps(mat, n + 1, m, dp, vis);
}
// minimum of every path
dp[n][m] = Math.min(ans1, Math.min(ans2, Math.min(ans3, ans4)));
return dp[n][m];
}
// Function that returns the minimum steps
static int minimumSteps(int mat[][], int n, int m)
{
// index to store the location at
// which you are standing
int twox = -1;
int twoy = -1;
// find '2' in the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 2) {
twox = i;
twoy = j;
break;
}
}
if (twox != -1)
break;
}
// Initialize dp matrix with -1
int dp[][]=new int[r][r];
for(int j=0;j<r;j++)
for(int i=0;i<r;i++)dp[j][i]=-1;
// Initialize vis matrix with false
boolean vis[][]= new boolean[r][r];
for(int j=0;j<r;j++)
for(int i=0;i<r;i++)vis[j][i]=false;
// Call function to find out minimum steps
// using memoization and recursion
int res = findMinSteps(mat, twox, twoy, dp, vis);
// if not possible
if (res >= 1e9)
return -1;
else
return res;
}
// Driver Code
public static void main(String args[])
{
int mat[][] = { { 1, 1, 1, 0, 1 },
{ 1, 0, 2, 0, 1 },
{ 0, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 0 } };
System.out.println( minimumSteps(mat, r, c));
}
}
//contributed by Arnab Kundu
Python
# Python program to find Minimum steps # to reach any of the boundary # edges of a matrix r=4 col=5 # Function to find out minimum steps def findMinSteps(mat, n, m, dp,vis): # boundary edges reached if (n == 0 or m == 0 or n == (r - 1) or m == (col - 1)): return 0 # already had a route through this # point, hence no need to re-visit if (dp[n][m] != -1): return dp[n][m] # visiting a position vis[n][m] = True ans1, ans2, ans3, ans4=10**9,10**9,10**9,10**9 # vertically up if (mat[n - 1][m] == 0): if (vis[n - 1][m]==False): ans1 = 1 + findMinSteps(mat, n - 1, m, dp, vis) # horizontally right if (mat[n][m + 1] == 0): if (vis[n][m + 1]==False): ans2 = 1 + findMinSteps(mat, n, m + 1, dp, vis) # horizontally left if (mat[n][m - 1] == 0): if (vis[n][m - 1]==False): ans3 = 1 + findMinSteps(mat, n, m - 1, dp, vis) # vertically down if (mat[n + 1][m] == 0): if (vis[n + 1][m]==False): ans4 = 1 + findMinSteps(mat, n + 1, m, dp, vis) # minimum of every path dp[n][m] = min(ans1, min(ans2, min(ans3, ans4))) return dp[n][m] # Function that returns the minimum steps def minimumSteps(mat, n, m): # index to store the location at # which you are standing twox = -1 twoy = -1 # find '2' in the matrix for i in range(n): for j in range(m): if (mat[i][j] == 2): twox = i twoy = j break if (twox != -1): break # Initialize dp matrix with -1 dp=[[-1 for i in range(col)] for i in range(r)] # Initialize vis matrix with false vis=[[False for i in range(col)] for i in range(r)] # Call function to find out minimum steps # using memoization and recursion res = findMinSteps(mat, twox, twoy, dp, vis) # if not possible if (res >= 10**9): return -1 else: return res # Driver Code mat= [ [ 1, 1, 1, 0, 1 ], [ 1, 0, 2, 0, 1 ], [ 0, 0, 1, 0, 1 ], [ 1, 0, 1, 1, 0 ] ] print(minimumSteps(mat, r, col)) #this is contributed by Mohit kumar 29
C#
// C# program to find Minimum steps
// to reach any of the boundary
// edges of a matrix
using System;
class Solution
{
static int r=4,c=5;
// Function to find out minimum steps
static int findMinSteps(int [,]mat, int n, int m, int [,]dp, bool [,]vis)
{
// boundary edges reached
if (n == 0 || m == 0 || n == (r - 1) || m == (c - 1)) {
return 0;
}
// already had a route through this
// point, hence no need to re-visit
if (dp[n,m] != -1)
return dp[n,m];
// visiting a position
vis[n,m] = true;
int ans1, ans2, ans3, ans4;
ans1 = ans2 = ans3 = ans4 = (int)1e9;
// vertically up
if (mat[n - 1,m] == 0) {
if (!vis[n - 1,m])
ans1 = 1 + findMinSteps(mat, n - 1, m, dp, vis);
}
// horizontally right
if (mat[n,m + 1] == 0) {
if (!vis[n,m + 1])
ans2 = 1 + findMinSteps(mat, n, m + 1, dp, vis);
}
// horizontally left
if (mat[n,m - 1] == 0) {
if (!vis[n,m - 1])
ans3 = 1 + findMinSteps(mat, n, m - 1, dp, vis);
}
// vertically down
if (mat[n + 1,m] == 0) {
if (!vis[n + 1,m])
ans4 = 1 + findMinSteps(mat, n + 1, m, dp, vis);
}
// minimum of every path
dp[n,m] = Math.Min(ans1, Math.Min(ans2, Math.Min(ans3, ans4)));
return dp[n,m];
}
// Function that returns the minimum steps
static int minimumSteps(int [,]mat, int n, int m)
{
// index to store the location at
// which you are standing
int twox = -1;
int twoy = -1;
// find '2' in the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i,j] == 2) {
twox = i;
twoy = j;
break;
}
}
if (twox != -1)
break;
}
// Initialize dp matrix with -1
int [,]dp = new int[r,r];
for(int j=0;j<r;j++)
for(int i=0;i<r;i++)
dp[j,i]=-1;
// Initialize vis matrix with false
bool [,]vis= new bool [r,r];
for(int j=0;j<r;j++)
for(int i=0;i<r;i++)
vis[j,i]=false;
// Call function to find out minimum steps
// using memoization and recursion
int res = findMinSteps(mat, twox, twoy, dp, vis);
// if not possible
if (res >= 1e9)
return -1;
else
return res;
}
// Driver Code
public static void Main()
{
int [,]mat = { { 1, 1, 1, 0, 1 },
{ 1, 0, 2, 0, 1 },
{ 0, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 0 }, };
Console.WriteLine(minimumSteps(mat, r, c));
}
// This code is contributed by Ryuga
}
Javascript
<script>
// Javascript program to find Minimum steps
// to reach any of the boundary
// edges of a matrix
let r=4,c=5;
// Function to find out minimum steps
function findMinSteps(mat, n, m, dp, vis)
{
// boundary edges reached
if (n == 0 || m == 0 || n == (r - 1) || m == (c - 1)) {
return 0;
}
// already had a route through this
// point, hence no need to re-visit
if (dp[n][m] != -1)
return dp[n][m];
// visiting a position
vis[n][m] = true;
let ans1, ans2, ans3, ans4;
ans1 = ans2 = ans3 = ans4 = 1e9;
// vertically up
if (mat[n - 1][m] == 0) {
if (!vis[n - 1][m])
ans1 = 1 + findMinSteps(mat, n - 1, m, dp, vis);
}
// horizontally right
if (mat[n][m + 1] == 0) {
if (!vis[n][m + 1])
ans2 = 1 + findMinSteps(mat, n, m + 1, dp, vis);
}
// horizontally left
if (mat[n][m - 1] == 0) {
if (!vis[n][m - 1])
ans3 = 1 + findMinSteps(mat, n, m - 1, dp, vis);
}
// vertically down
if (mat[n + 1][m] == 0) {
if (!vis[n + 1][m])
ans4 = 1 + findMinSteps(mat, n + 1, m, dp, vis);
}
// minimum of every path
dp[n][m] = Math.min(ans1, Math.min(ans2, Math.min(ans3, ans4)));
return dp[n][m];
}
// Function that returns the minimum steps
function minimumSteps(mat, n, m)
{
// index to store the location at
// which you are standing
let twox = -1;
let twoy = -1;
// find '2' in the matrix
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (mat[i][j] == 2) {
twox = i;
twoy = j;
break;
}
}
if (twox != -1)
break;
}
// Initialize dp matrix with -1
let dp = new Array(r);
for(let j=0;j<r;j++)
{
dp[j] = new Array(r);
for(let i=0;i<r;i++)
{
dp[j][i]=-1;
}
}
// Initialize vis matrix with false
let vis = new Array(r);
for(let j=0;j<r;j++)
{
vis[j] = new Array(r);
for(let i=0;i<r;i++)
{
vis[j][i]=false;
}
}
// Call function to find out minimum steps
// using memoization and recursion
let res = findMinSteps(mat, twox, twoy, dp, vis);
// if not possible
if (res >= 1e9)
return -1;
else
return res;
}
let mat = [ [ 1, 1, 1, 0, 1 ],
[ 1, 0, 2, 0, 1 ],
[ 0, 0, 1, 0, 1 ],
[ 1, 0, 1, 1, 0 ] ];
document.write( minimumSteps(mat, r, c));
// This code is contributed by suresh07.
</script>
Producción:
2
Complejidad de tiempo: O(N^2), ya que estamos usando un ciclo for para recorrer N veces y en cada recorrido, estamos llamando a la función findMinSteps que cuesta O(N) tiempo, por lo que el tiempo efectivo será O(N* NORTE).
Espacio auxiliar: O(N^2), ya que estamos usando espacio extra para la array dp.
Pasos mínimos para alcanzar cualquiera de las aristas límite de una array | Conjunto-2