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 se encuentra 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 valor 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 ha sido resuelto en el Set-1 usando Programación Dinámica. En este artículo, discutiremos un método que usa BFS . A continuación se detallan los pasos para resolver el problema anterior.
- Encuentre el índice del ‘2’ en la array.
- Compruebe si este índice es un borde de límite o no, si lo es, entonces no se requieren movimientos.
- Inserte el índice x y el índice y de ‘2’ en la cola con movimientos como 0.
- Use una array vis 2-D para marcar las posiciones de visita en la array.
- Iterar hasta que la cola esté vacía o lleguemos a cualquier límite.
- Obtenga el elemento frontal (x, y, val = movimientos) en la cola y marque vis[x][y] como visitado. Haz todos los movimientos posibles (derecha, izquierda, arriba y abajo) posibles.
- Vuelva a insertar val+1 y sus índices de todos los movimientos válidos en la cola.
- Si x e y se convierten en los bordes del límite en cualquier momento, devuelve val.
- Si se realizan todos los movimientos y la cola está vacía, entonces no es posible, por lo tanto, devuelve -1.
A continuación se muestra la implementación del enfoque anterior:
CPP
// 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 c 5
// Function to check validity
bool check(int i, int j, int n, int m, int mat[r])
{
if (i >= 0 && i < n && j >= 0 && j < m) {
if (mat[i][j] == 0)
return true;
}
return false;
}
// Function to find out minimum steps
int findMinSteps(int mat[r], int n, int m)
{
int indx, indy;
indx = indy = -1;
// Find index of only 2 in matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 2) {
indx = i, indy = j;
break;
}
}
if (indx != -1)
break;
}
// Push elements in the queue
queue<pair<int, pair<int, int> > > q;
// Push the position 2 with moves as 0
q.push(make_pair(0, make_pair(indx, indy)));
// If already at boundary edge
if (check(indx, indy, n, m, mat))
return 0;
// Marks the visit
bool vis[r];
memset(vis, 0, sizeof vis);
// Iterate in the queue
while (!q.empty()) {
// Get the front of the queue
auto it = q.front();
// Pop the first element from the queue
q.pop();
// Get the position
int x = it.second.first;
int y = it.second.second;
// Moves
int val = it.first;
// If a boundary edge
if (x == 0 || x == (n - 1) || y == 0 || y == (m - 1)) {
return val;
}
// Marks the visited array
vis[x][y] = 1;
// If a move is possible
if (check(x - 1, y, n, m, mat)) {
// If not visited previously
if (!vis[x - 1][y])
q.push(make_pair(val + 1, make_pair(x - 1, y)));
}
// If a move is possible
if (check(x + 1, y, n, m, mat)) {
// If not visited previously
if (!vis[x + 1][y])
q.push(make_pair(val + 1, make_pair(x + 1, y)));
}
// If a move is possible
if (check(x, y + 1, n, m, mat)) {
// If not visited previously
if (!vis[x][y + 1])
q.push(make_pair(val + 1, make_pair(x, y + 1)));
}
// If a move is possible
if (check(x, y - 1, n, m, mat)) {
// If not visited previously
if (!vis[x][y - 1])
q.push(make_pair(val + 1, make_pair(x, y - 1)));
}
}
return -1;
}
// Driver Code
int main()
{
int mat[r] = { { 1, 1, 1, 0, 1 },
{ 1, 0, 2, 0, 1 },
{ 0, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 0 } };
cout << findMinSteps(mat, r, c);
}
Python3
# Python3 program to find Minimum steps # to reach any of the boundary # edges of a matrix from collections import deque r = 4 c = 5 # Function to check validity def check(i, j, n, m, mat): if (i >= 0 and i < n and j >= 0 and j < m): if (mat[i][j] == 0): return True return False # Function to find out minimum steps def findMinSteps(mat, n, m): indx = indy = -1; # Find index of only 2 in matrix for i in range(n): for j in range(m): if (mat[i][j] == 2): indx = i indy = j break if (indx != -1): break # Push elements in the queue q = deque() # Push the position 2 with moves as 0 q.append([0, indx, indy]) # If already at boundary edge if (check(indx, indy, n, m, mat)): return 0 # Marks the visit vis=[ [0 for i in range(r)]for i in range(r)] # Iterate in the queue while len(q) > 0: # Get the front of the queue it = q.popleft() #Pop the first element from the queue # Get the position x = it[1] y = it[2] # Moves val = it[0] # If a boundary edge if (x == 0 or x == (n - 1) or y == 0 or y == (m - 1)): return val # Marks the visited array vis[x][y] = 1 # If a move is possible if (check(x - 1, y, n, m, mat)): # If not visited previously if (not vis[x - 1][y]): q.append([val + 1, x - 1, y]) # If a move is possible if (check(x + 1, y, n, m, mat)): # If not visited previously if (not vis[x + 1][y]): q.append([val + 1, x + 1, y]) # If a move is possible if (check(x, y + 1, n, m, mat)): # If not visited previously if (not vis[x][y + 1]): q.append([val + 1, x, y + 1]) # If a move is possible if (check(x, y - 1, n, m, mat)): # If not visited previously if (not vis[x][y - 1]): q.append([val + 1, x, y - 1]) return -1 # Driver Code mat = [[1, 1, 1, 0, 1 ], [1, 0, 2, 0, 1 ], [0, 0, 1, 0, 1 ], [1, 0, 1, 1, 0 ] ]; print(findMinSteps(mat, r, c)) # This code is contributed by mohit kumar 29
Javascript
<script>
// JavaScript program to find Minimum steps
// to reach any of the boundary
// edges of a matrix
const r = 4
const c = 5
// Function to check validity
function check(i, j, n, m, mat){
if (i >= 0 && i < n && j >= 0 && j < m){
if (mat[i][j] == 0)
return true
}
return false
}
// Function to find out minimum steps
function findMinSteps(mat, n, m){
let indx = -1, indy = -1;
// Find index of only 2 in matrix
for(let i=0;i<n;i++){
for(let j=0;j<m;j++){
if (mat[i][j] == 2){
indx = i
indy = j
break
}
}
if (indx != -1){
break
}
}
// Push elements in the queue
let q = []
// Push the position 2 with moves as 0
q.push([0, indx, indy])
// If already at boundary edge
if (check(indx, indy, n, m, mat))
return 0
// Marks the visit
let vis = new Array(r);
for(let i=0;i<r;i++){
vis[i] = new Array(r).fill(0);
}
// Iterate in the queue
while(q.length > 0){
// Get the front of the queue
let it = q.shift()
//Pop the first element from the queue
// Get the position
let x = it[1]
let y = it[2]
// Moves
let val = it[0]
// If a boundary edge
if (x == 0 || x == (n - 1) || y == 0 || y == (m - 1))
return val
// Marks the visited array
vis[x][y] = 1
// If a move is possible
if (check(x - 1, y, n, m, mat)){
// If not visited previously
if (vis[x - 1][y] == 0)
q.push([val + 1, x - 1, y])
}
// If a move is possible
if (check(x + 1, y, n, m, mat)){
// If not visited previously
if (vis[x + 1][y] == 0)
q.push([val + 1, x + 1, y])
}
// If a move is possible
if (check(x, y + 1, n, m, mat)){
// If not visited previously
if (vis[x][y + 1] == 0)
q.push([val + 1, x, y + 1])
}
// If a move is possible
if (check(x, y - 1, n, m, mat)){
// If not visited previously
if (vis[x][y - 1] == 0)
q.push([val + 1, x, y - 1])
}
}
return -1
}
// Driver Code
let mat = [[1, 1, 1, 0, 1 ],
[1, 0, 2, 0, 1 ],
[0, 0, 1, 0, 1 ],
[1, 0, 1, 1, 0 ]];
document.write(findMinSteps(mat, r, c))
// This code is contributed by shinjanpatra
</script>
Producción:
2
Complejidad de tiempo: O(N^2) Espacio auxiliar: O(N^2)