Dada una array arr[][] de dimensiones N * M , que tiene los elementos 0 , 1 y 2 . Solo hay una celda con valor 1 presente en la array. La tarea es verificar si es posible que 1 llegue a la esquina inferior derecha antes que cualquier celda con valor 2 o no usando las siguientes operaciones:
- 2 puede replicarse 1 unidad en las cuatro direcciones en 1 unidad de tiempo.
- 1 solo puede moverse en una dirección entre las cuatro direcciones si el elemento en esa posición es 0 .
Imprima » Sí» si una celda con valor 1 llegará a la esquina inferior derecha en menos o igual cantidad de tiempo que cualquier celda con valor 2 . De lo contrario, escriba “ 1″ .
Ejemplos:
Entrada: N = 3, M = 3, arr[][] = {{0, 2, 0}, {0, 1, 0}, {0, 0, 0}}
Salida : Sí
Explicación:
1 puede moverse a la esquina inferior derecha en 2 movimientos y 2 pueden moverse a la esquina inferior derecha en 3 movimientos.
Dado que la celda con valor 1 llega primero que la celda con valor 2. Por lo tanto, imprima Sí.Entrada: N = 3, M = 3, arr[][] = {{0, 2, 0}, {0, 1, 0}, {0, 2, 0}}
Salida: No
Explicación:
1 puede moverse a la esquina inferior derecha en 2 movimientos y 2 en la última fila de la celda pueden moverse a la esquina inferior derecha en 1 movimiento.
Dado que la celda con valor 2 llega primero que la celda con valor 1. Por lo tanto, imprima No.
Enfoque: La idea es utilizar un BFS de múltiples fuentes . Para realizar un cruce BFS multifuente, agregue todas las posiciones de 1 y 2 s presentes en la array, en un Deque en el orden especificado. Realice el BFS en esa cola extrayendo las posiciones agregadas y agregando las posiciones adyacentes que aún no se han visitado. Siga los pasos a continuación para resolver el problema:
- Cree una eliminación de cola para BFS de múltiples fuentes.
- En primer lugar, agregue la posición que tiene 1 al frente y luego agregue las posiciones que tienen 2 en la parte posterior. Esto se debe a que si 1 y 2 llegan a la parte inferior derecha al mismo tiempo, entonces 1 se considera superior a 2 .
- Extraiga los elementos del frente de la eliminación de la cola hasta que la eliminación de la cola esté vacía y haga lo siguiente:
- Si la posición emergente ya se visitó, continúe con la siguiente posición.
- Si no se visita la posición, compruebe si es una posición inferior derecha o no, así como si el elemento que contiene es 1 o no. Si se encuentra que es cierto, escriba Sí .
- De lo contrario, para las cuatro direcciones, inserte las posiciones actuales en el dequeue .
- Una vez agotadas las operaciones anteriores, si no se encuentra que la celda con el valor 1 haya alcanzado la posición inferior derecha, imprima No .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if cell with
// value 1 doesn't reaches the bottom
// right cell or not
bool reachesBottom(vector<vector<int> >& a)
{
// Number of rows and columns
int n = a.size();
int m = a[0].size();
// Initialise the deque
deque<vector<int> > q;
// Traverse the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Push 1 to front of queue
if (a[i][j] == 1) {
q.push_front({ i, j, 1 });
}
// Push 2 to back of queue
else if (a[i][j] == 2) {
q.push_back({ i, j, 2 });
}
a[i][j] = 0;
}
}
// Store all the possible direction
// of the current cell
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
// Run multi-source BFS
while (!q.empty()) {
// Get the front element
auto front = q.front();
// Pop the front element
q.pop_front();
int i = front[0], j = front[1];
int t = front[2];
if (a[i][j])
continue;
a[i][j] = 1;
// If 1 reached corner first
if (t == 1 and (i == n - 1
&& j == m - 1)) {
return true;
}
for (int d = 0; d < 4; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
// Insert new point in queue
if (ni >= 0 and ni < n
and nj >= 0 and nj < m) {
q.push_back({ ni, nj, t });
}
}
}
// If 1 can't reach the bottom
// right then return false
return false;
}
// Driver Code
int main()
{
// Given matrix
vector<vector<int> > matrix{ { 0, 2, 0 },
{ 0, 1, 0 },
{ 0, 2, 0 } };
// Function Call
if (reachesBottom(matrix)) {
cout << "YES";
}
else {
cout << "NO";
}
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG{
// Function to check if cell with
// value 1 doesn't reaches the bottom
// right cell or not
static boolean reachesBottom(int[][] a)
{
// Number of rows and columns
int n = a.length;
int m = a[0].length;
// Initialise the deque
Deque<int[]> q = new LinkedList<>();
// Traverse the matrix
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
// Push 1 to front of queue
if (a[i][j] == 1)
{
q.addFirst(new int[]{ i, j, 1 });
}
// Push 2 to back of queue
else if (a[i][j] == 2)
{
q.addLast(new int[]{ i, j, 2 });
}
a[i][j] = 0;
}
}
// Store all the possible direction
// of the current cell
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
// Run multi-source BFS
while (!q.isEmpty())
{
// Get the front element
int[] front = q.peekFirst();
// Pop the front element
q.removeFirst();
int i = front[0], j = front[1];
int t = front[2];
if (a[i][j] == 1)
continue;
a[i][j] = 1;
// If 1 reached corner first
if (t == 1 && (i == n - 1 &&
j == m - 1))
{
return true;
}
for(int d = 0; d < 4; d++)
{
int ni = i + dx[d];
int nj = j + dy[d];
// Insert new point in queue
if (ni >= 0 && ni < n &&
nj >= 0 && nj < m)
{
q.addLast(new int[]{ ni, nj, t });
}
}
}
// If 1 can't reach the bottom
// right then return false
return false;
}
// Driver Code
public static void main (String[] args)
{
// Given matrix
int[][] matrix = { { 0, 2, 0 },
{ 0, 1, 0 },
{ 0, 2, 0 } };
// Function call
if (reachesBottom(matrix))
{
System.out.print("YES");
}
else
{
System.out.print("NO");
}
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
from collections import deque
# Function to check if cell with
# value 1 doesn't reaches the bottom
# right cell or not
def reachesBottom(a):
# Number of rows and columns
n = len(a)
m = len(a[0])
# Initialise the deque
q = deque()
# Traverse the matrix
for i in range(n):
for j in range(m):
# Push 1 to front of queue
if (a[i][j] == 1):
q.appendleft([i, j, 1])
# Push 2 to back of queue
elif (a[i][j] == 2):
q.append([i, j, 2])
a[i][j] = 0
# Store all the possible direction
# of the current cell
dx = [ -1, 0, 1, 0 ]
dy = [ 0, 1, 0, -1 ]
# Run multi-source BFS
while (len(q) > 0):
# Get the front element
front = q.popleft()
i = front[0]
j = front[1]
t = front[2]
if (a[i][j]):
continue
a[i][j] = 1
# If 1 reached corner first
if (t == 1 and (i == n - 1 and
j == m - 1)):
return True
for d in range(4):
ni = i + dx[d]
nj = j + dy[d]
# Insert new point queue
if (ni >= 0 and ni < n and
nj >= 0 and nj < m):
q.append([ni, nj, t])
# If 1 can't reach the bottom
# right then return false
return False
# Driver Code
if __name__ == '__main__':
# Given matrix
matrix = [ [ 0, 2, 0 ],
[ 0, 1, 0 ],
[ 0, 2, 0 ] ]
# Function call
if (reachesBottom(matrix)):
print("YES")
else:
print("NO")
# This code is contributed by mohit kumar 29
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if cell with
// value 1 doesn't reaches the bottom
// right cell or not
static bool reachesBottom(int [,]a,
int n, int m)
{
// Initialise the deque
Queue<int[]> q = new Queue<int[]>();
// Traverse the matrix
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
// Push 1 to front of queue
if (a[i, j] == 1)
{
q.Enqueue(new int[]{i, j, 1});
}
// Push 2 to back of queue
else if (a[i, j] == 2)
{
q.Enqueue(new int[]{i, j, 2});
}
a[i, j] = 0;
}
}
// Store all the possible direction
// of the current cell
int []dx = {-1, 0, 1, 0};
int []dy = {0, 1, 0, -1};
// Run multi-source BFS
while (q.Count != 0)
{
// Get the front element
int[] front = q.Peek();
// Pop the front element
q.Dequeue();
int i = front[0], j = front[1];
int t = front[2];
if (a[i, j] == 1)
continue;
a[i, j] = 1;
// If 1 reached corner first
if (t == 1 && (i == n - 1 &&
j == m - 1))
{
return true;
}
for(int d = 0; d < 4; d++)
{
int ni = i + dx[d];
int nj = j + dy[d];
// Insert new point in queue
if (ni >= 0 && ni < n &&
nj >= 0 && nj < m)
{
q.Enqueue(new int[]{ni, nj, t});
}
}
}
// If 1 can't reach the bottom
// right then return false
return false;
}
// Driver Code
public static void Main(String[] args)
{
// Given matrix
int[,] matrix = {{0, 2, 0},
{0, 1, 0},
{0, 2, 0}};
// Function call
if (reachesBottom(matrix, 3, 3))
{
Console.Write("YES");
}
else
{
Console.Write("NO");
}
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to check if cell with
// value 1 doesn't reaches the bottom
// right cell or not
function reachesBottom(a)
{
// Number of rows and columns
var n = a.length;
var m = a[0].length;
// Initialise the deque
var q = [];
// Traverse the matrix
for (var i = 0; i < n; i++) {
for (var j = 0; j < m; j++) {
// Push 1 to front of queue
if (a[i][j] == 1) {
q.slice(0,0,[i, j, 1]);
}
// Push 2 to back of queue
else if (a[i][j] == 2) {
q.push([i, j, 2 ]);
}
a[i][j] = 0;
}
}
// Store all the possible direction
// of the current cell
var dx = [-1, 0, 1, 0 ];
var dy = [ 0, 1, 0, -1 ];
// Run multi-source BFS
while (!q.length) {
// Get the front element
var front = q[0];
// Pop the front element
q.shift();
var i = front[0], j = front[1];
var t = front[2];
if (a[i][j])
continue;
a[i][j] = 1;
// If 1 reached corner first
if (t == 1 && (i == n - 1
&& j == m - 1)) {
return true;
}
for (var d = 0; d < 4; d++) {
var ni = i + dx[d];
var nj = j + dy[d];
// Insert new point in queue
if (ni >= 0 && ni < n
&& nj >= 0 && nj < m) {
q.push([ ni, nj, t ]);
}
}
}
// If 1 can't reach the bottom
// right then return false
return false;
}
// Driver Code
// Given matrix
var matrix = [[ 0, 2, 0 ],
[ 0, 1, 0 ],
[0, 2, 0 ]];
// Function Call
if (reachesBottom(matrix)) {
document.write( "YES");
}
else {
document.write( "NO");
}
</script>
Producción:
NO
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA