Dada una cuadrícula mat[][] de tamaño M * N , que consta de solo 0 s, 1 s y 2 s, donde 0 representa un lugar vacío, 1 representa una persona y 2 representa el fuego, la tarea es contar el mínimo número de movimientos necesarios para que la persona salga de la red de forma segura. En cada paso, el fuego quemará sus celdas laterales adyacentes y la persona se moverá de la celda actual a una de sus celdas laterales adyacentes. Si no es posible salir de la cuadrícula, imprima -1 .
Nota: Una persona saldrá de la cuadrícula si llega a uno de los lados del borde de la cuadrícula.
Ejemplos:
Entrada: mat[][] = { { 0, 0, 0, 0 }, { 2, 0, 0, 0 }, { 2, 1, 0, 0 }, { 2, 2, 0, 0 } }
Salida : 2
Explicación:
Los movimientos posibles de la persona son (2, 1) → (2, 2) → (2, 3).
La persona llega a uno de los lados del borde de la cuadrícula (última fila) en 2 movimientos y también es la cuenta mínima posible.
Por lo tanto, la salida requerida es 2.Entrada: mat[][] = { { 0, 2, 0, 0 }, { 2, 1, 0, 2 }, { 2, 0, 0, 0 }, { 2, 0, 2, 0 }}
Salida : -1
Enfoque: El problema se puede resolver usando conceptos para resolver el problema de las naranjas podridas . La idea es realizar BFS en la propagación del fuego, así como en los movimientos de la persona. Siga los pasos a continuación para resolver el problema:
- Inicialice dos colas vacías fQ y pQ para almacenar las celdas en las que se puede propagar el fuego y a las que se puede mover la persona, respectivamente.
- Inicialice una array 2D , por ejemplo, visited[][] , para verificar si la persona ya visitó la celda (i, j) o no.
- Ponga en cola todas las celdas adyacentes laterales de la persona y marque todas las celdas adyacentes como celdas visitadas.
- Ponga en cola todas las celdas adyacentes a los lados de las celdas de fuego en fQ y marque todas las celdas adyacentes a los lados como celdas en llamas.
- Inicialice una variable, digamos depth , para realizar un seguimiento de la distancia más corta entre dos celdas.
- Realice los siguientes pasos mientras pQ no está vacío:
- Incrementa la profundidad en 1.
- Saque de la cola todas las celdas de pQ y ponga en cola todas las celdas adyacentes laterales válidas de la celda extraída.
- Si alguna celda adyacente en cola está presente en el borde de la cuadrícula, imprima el valor de profundidad.
- De lo contrario, elimine todas las celdas de fQ . Para cada celda extraída, ponga en cola todas las celdas adyacentes válidas.
- De los pasos anteriores, si no es posible salir de la cuadrícula, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores size of the grid
int m, n;
// Function to check valid
// cells of the grid
bool valid(int x, int y)
{
return (x >= 0 && x < m && y >= 0 && y < n);
}
// Checks for the border sides
bool border(int x, int y)
{
return (x == 0 || x == m - 1 || y == 0 || y == n - 1);
}
// Function to find shortest distance
// between two cells of the grid
int minStep(vector<vector<int>> mat)
{
// Rows of the grid
m = mat.size();
// Column of the grid
n = mat[0].size();
// Stores possible move
// of the person
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
// Store possible cells visited
// by the person
queue<pair<int,int> > pQ;
// Store possible cells which
// are burning
queue<pair<int,int> > fQ;
// Traverse the grid
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++) {
// If current cell is
// burning
if (mat[i][j] == 2)
fQ.push({i, j});
// If person is in
// the current cell
else if (mat[i][j] == 1) {
if (border(i, j))
return 0;
pQ.push({i, j});
}
}
}
// Stores shortest distance
// between two cells
int depth = 0;
// Check if a cell is visited
// by the person or not
vector<vector<int>> visited(n,vector<int>(m,0));
// While pQ is not empty
while (pQ.size()>0) {
// Update depth
depth++;
// Popped all the cells from
// pQ and mark all adjacent cells
// of as visited
for (int i = pQ.size(); i > 0;i--) {
// Front element of
// the queue pQ
pair<int,int> pos = pQ.front();
// Remove front element of
// the queue pQ
pQ.pop();
// If current cell is burning
if (mat[pos.first][pos.second] == 2)
continue;
// Find all adjacent cells
for (int j = 0; j < 4; j++) {
// Stores row number of
// adjacent cell
int x = pos.first + dx[j];
// Stores column number
// of adjacent cell
int y = pos.second + dy[j];
// Checks if current cell
// is valid
if (valid(x, y) && mat[x][y] != 2 && !visited[x][y]) {
// Mark the cell as visited
visited[x][y] = 1;
// Enqueue the cell
pQ.push(pair<int,int> (x, y));
// Checks the escape condition
if (border(x, y))
return depth;
}
}
}
// Burn all the adjacent cells
// of burning cells
for (int i = fQ.size(); i > 0; i--) {
// Front element of
// the queue fQ
pair<int,int> pos = fQ.front();
// Delete front element of
// the queue fQ
fQ.pop();
// Find adjacent cells of
// burning cell
for (int j = 0; j < 4; j++) {
// Stores row number of
// adjacent cell
int x = pos.first + dx[j];
// Stores column number
// of adjacent cell
int y = pos.second + dy[j];
// Checks if current
// cell is valid
if (valid(x, y) && mat[x][y] != 2) {
mat[x][y] = 2;
// Burn all the adjacent
// cells of current cell
fQ.push(pair<int,int> (x, y));
}
}
}
}
return -1;
}
// Driver Code
int main()
{
// Given grid
vector<vector<int>> grid = { { 0, 0, 0, 0 },
{ 2, 0, 0, 0 },
{ 2, 1, 0, 0 },
{ 2, 2, 0, 0 } };
cout<<minStep(grid);
}
Java
// Java program to implement
// the above approach
import java.util.*;
import java.lang.*;
class GFG
{
// Structure of cell
// of the grid
static class pair
{
int x, y;
pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
// Stores size of the grid
static int m, n;
// Function to find shortest distance
// between two cells of the grid
static int minStep(int[][] mat)
{
// Rows of the grid
m = mat.length;
// Column of the grid
n = mat[0].length;
// Stores possible move
// of the person
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
// Store possible cells visited
// by the person
Queue<pair> pQ = new LinkedList<>();
// Store possible cells which
// are burning
Queue<pair> fQ = new LinkedList<>();
// Traverse the grid
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
// If current cell is
// burning
if (mat[i][j] == 2)
fQ.add(new pair(i, j));
// If person is in
// the current cell
else if (mat[i][j] == 1)
{
if (border(i, j))
return 0;
pQ.add(new pair(i, j));
}
}
// Stores shortest distance
// between two cells
int depth = 0;
// Check if a cell is visited
// by the person or not
boolean[][] visited
= new boolean[n][m];
// While pQ is not empty
while (!pQ.isEmpty())
{
// Update depth
depth++;
// Popped all the cells from
// pQ and mark all adjacent cells
// of as visited
for (int i = pQ.size(); i > 0; i--)
{
// Front element of
// the queue pQ
pair pos = pQ.peek();
// Remove front element of
// the queue pQ
pQ.remove();
// If current cell is burning
if (mat[pos.x][pos.y] == 2)
continue;
// Find all adjacent cells
for (int j = 0; j < 4; j++)
{
// Stores row number of
// adjacent cell
int x = pos.x + dx[j];
// Stores column number
// of adjacent cell
int y = pos.y + dy[j];
// Checks if current cell
// is valid
if (valid(x, y) && mat[x][y] != 2
&& !visited[x][y])
{
// Mark the cell as visited
visited[x][y] = true;
// Enqueue the cell
pQ.add(new pair(x, y));
// Checks the escape condition
if (border(x, y))
return depth;
}
}
}
// Burn all the adjacent cells
// of burning cells
for (int i = fQ.size(); i > 0; i--)
{
// Front element of
// the queue fQ
pair pos = fQ.peek();
// Delete front element of
// the queue fQ
fQ.remove();
// Find adjacent cells of
// burning cell
for (int j = 0; j < 4; j++)
{
// Stores row number of
// adjacent cell
int x = pos.x + dx[j];
// Stores column number
// of adjacent cell
int y = pos.y + dy[j];
// Checks if current
// cell is valid
if (valid(x, y) && mat[x][y] != 2)
{
mat[x][y] = 2;
// Burn all the adjacent
// cells of current cell
fQ.add(new pair(x, y));
}
}
}
}
return -1;
}
// Function to check valid
// cells of the grid
static boolean valid(int x, int y)
{
return (x >= 0 && x < m
&& y >= 0 && y < n);
}
// Checks for the border sides
static boolean border(int x, int y)
{
return (x == 0 || x == m - 1
|| y == 0 || y == n - 1);
}
// Driver Code
public static void main(String[] args)
{
// Given grid
int[][] grid = { { 0, 0, 0, 0 },
{ 2, 0, 0, 0 },
{ 2, 1, 0, 0 },
{ 2, 2, 0, 0 } };
System.out.println(minStep(grid));
}
}
// This code is contributed by mohit kumar 29.
Python3
# Python3 program to implement # the above approach # Stores size of the grid m = 0 n = 0 # Function to check valid # cells of the grid def valid(x, y): global n global m return (x >= 0 and x < m and y >= 0 and y < n) # Checks for the border sides def border(x, y): global n global m return (x == 0 or x == m - 1 or y == 0 or y == n - 1) # Function to find shortest distance # between two cells of the grid def minStep(mat): global n global m # Rows of the grid m = len(mat) # Column of the grid n = len(mat[0]) # Stores possible move # of the person dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] # Store possible cells visited # by the person pQ = [] # Store possible cells which # are burning fQ = [] # Traverse the grid for i in range(m): for j in range(n): # If current cell is # burning if (mat[i][j] == 2): fQ.append([i, j]) # If person is in # the current cell elif(mat[i][j] == 1): if (border(i, j)): return 0 pQ.append([i, j]) # Stores shortest distance # between two cells depth = 0 # Check if a cell is visited # by the person or not visited = [[0 for i in range(m)] for j in range(n)] # While pQ is not empty while (len(pQ) > 0): # Update depth depth += 1 # Popped all the cells from # pQ and mark all adjacent cells # of as visited i = len(pQ) while(i > 0): # Front element of # the queue pQ pos = pQ[0] # Remove front element of # the queue pQ pQ.remove(pQ[0]) # If current cell is burning if (mat[pos[0]][pos[1]] == 2): continue # Find all adjacent cells for j in range(4): # Stores row number of # adjacent cell x = pos[0] + dx[j] # Stores column number # of adjacent cell y = pos[1] + dy[j] # Checks if current cell # is valid if (valid(x, y) and mat[x][y] != 2 and visited[x][y] == 0): # Mark the cell as visited visited[x][y] = 1 # Enqueue the cell pQ.append([x, y]) # Checks the escape condition if (border(x, y)): return depth i -= 1 # Burn all the adjacent cells # of burning cells i = len(fQ) while(i > 0): # Front element of # the queue fQ pos = fQ[0] # Delete front element of # the queue fQ fQ.remove(fQ[0]) # Find adjacent cells of # burning cell for j in range(4): # Stores row number of # adjacent cell x = pos[0] + dx[j] # Stores column number # of adjacent cell y = pos[1] + dy[j] # Checks if current # cell is valid if (valid(x, y) and mat[x][y] != 2): mat[x][y] = 2 # Burn all the adjacent # cells of current cell fQ.append([x, y]) i -= 1 return -1 # Driver Code if __name__ == '__main__': # Given grid grid = [ [ 0, 0, 0, 0 ], [ 2, 0, 0, 0 ], [ 2, 1, 0, 0 ], [ 2, 2, 0, 0 ] ] print(minStep(grid)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Structure of cell
// of the grid
class pair
{
public int x, y;
public pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
// Stores size of the grid
static int m, n;
// Function to find shortest distance
// between two cells of the grid
static int minStep(int[,] mat)
{
// Rows of the grid
m = mat.GetLength(0);
// Column of the grid
n = mat.GetLength(1);
// Stores possible move
// of the person
int []dx = { 1, -1, 0, 0 };
int []dy = { 0, 0, 1, -1 };
// Store possible cells visited
// by the person
Queue<pair> pQ = new Queue<pair>();
// Store possible cells which
// are burning
Queue<pair> fQ = new Queue<pair>();
// Traverse the grid
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
// If current cell is
// burning
if (mat[i, j] == 2)
fQ.Enqueue(new pair(i, j));
// If person is in
// the current cell
else if (mat[i, j] == 1)
{
if (border(i, j))
return 0;
pQ.Enqueue(new pair(i, j));
}
}
// Stores shortest distance
// between two cells
int depth = 0;
// Check if a cell is visited
// by the person or not
bool[,] visited
= new bool[n, m];
// While pQ is not empty
while (pQ.Count != 0)
{
// Update depth
depth++;
// Popped all the cells from
// pQ and mark all adjacent cells
// of as visited
for (int i = pQ.Count; i > 0; i--)
{
// Front element of
// the queue pQ
pair pos = pQ.Peek();
// Remove front element of
// the queue pQ
pQ.Dequeue();
// If current cell is burning
if (mat[pos.x, pos.y] == 2)
continue;
// Find all adjacent cells
for (int j = 0; j < 4; j++)
{
// Stores row number of
// adjacent cell
int x = pos.x + dx[j];
// Stores column number
// of adjacent cell
int y = pos.y + dy[j];
// Checks if current cell
// is valid
if (valid(x, y) && mat[x, y] != 2
&& !visited[x, y])
{
// Mark the cell as visited
visited[x, y] = true;
// Enqueue the cell
pQ.Enqueue(new pair(x, y));
// Checks the escape condition
if (border(x, y))
return depth;
}
}
}
// Burn all the adjacent cells
// of burning cells
for (int i = fQ.Count; i > 0; i--)
{
// Front element of
// the queue fQ
pair pos = fQ.Peek();
// Delete front element of
// the queue fQ
fQ.Dequeue();
// Find adjacent cells of
// burning cell
for (int j = 0; j < 4; j++)
{
// Stores row number of
// adjacent cell
int x = pos.x + dx[j];
// Stores column number
// of adjacent cell
int y = pos.y + dy[j];
// Checks if current
// cell is valid
if (valid(x, y) && mat[x, y] != 2)
{
mat[x, y] = 2;
// Burn all the adjacent
// cells of current cell
fQ.Enqueue(new pair(x, y));
}
}
}
}
return -1;
}
// Function to check valid
// cells of the grid
static bool valid(int x, int y)
{
return (x >= 0 && x < m
&& y >= 0 && y < n);
}
// Checks for the border sides
static bool border(int x, int y)
{
return (x == 0 || x == m - 1
|| y == 0 || y == n - 1);
}
// Driver Code
public static void Main(String[] args)
{
// Given grid
int[,] grid = { { 0, 0, 0, 0 },
{ 2, 0, 0, 0 },
{ 2, 1, 0, 0 },
{ 2, 2, 0, 0 } };
Console.WriteLine(minStep(grid));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
// Stores size of the grid
var m, n;
// Function to check valid
// cells of the grid
function valid(x, y)
{
return (x >= 0 && x < m && y >= 0 && y < n);
}
// Checks for the border sides
function border(x, y)
{
return (x == 0 || x == m - 1 || y == 0 || y == n - 1);
}
// Function to find shortest distance
// between two cells of the grid
function minStep(mat)
{
// Rows of the grid
m = mat.length;
// Column of the grid
n = mat[0].length;
// Stores possible move
// of the person
var dx = [1, -1, 0, 0];
var dy = [0, 0, 1, -1];
// Store possible cells visited
// by the person
var pQ = [];
// Store possible cells which
// are burning
var fQ = [];
// Traverse the grid
for (var i = 0; i < m; i++){
for (var j = 0; j < n; j++) {
// If current cell is
// burning
if (mat[i][j] == 2)
fQ.push([i, j]);
// If person is in
// the current cell
else if (mat[i][j] == 1) {
if (border(i, j))
return 0;
pQ.push([i, j]);
}
}
}
// Stores shortest distance
// between two cells
var depth = 0;
// Check if a cell is visited
// by the person or not
var visited = Array.from(Array(n), ()=> Array(m).fill(0));
// While pQ is not empty
while (pQ.length>0) {
// Update depth
depth++;
// Popped all the cells from
// pQ and mark all adjacent cells
// of as visited
for (var i = pQ.length; i > 0;i--) {
// Front element of
// the queue pQ
var pos = pQ[0];
// Remove front element of
// the queue pQ
pQ.shift();
// If current cell is burning
if (mat[pos[0]][pos[1]] == 2)
continue;
// Find all adjacent cells
for (var j = 0; j < 4; j++) {
// Stores row number of
// adjacent cell
var x = pos[0] + dx[j];
// Stores column number
// of adjacent cell
var y = pos[1] + dy[j];
// Checks if current cell
// is valid
if (valid(x, y) && mat[x][y] != 2 && !visited[x][y]) {
// Mark the cell as visited
visited[x][y] = 1;
// Enqueue the cell
pQ.push([x, y]);
// Checks the escape condition
if (border(x, y))
return depth;
}
}
}
// Burn all the adjacent cells
// of burning cells
for (var i = fQ.length; i > 0; i--) {
// Front element of
// the queue fQ
var pos = fQ[0];
// Delete front element of
// the queue fQ
fQ.shift();
// Find adjacent cells of
// burning cell
for (var j = 0; j < 4; j++) {
// Stores row number of
// adjacent cell
var x = pos[0] + dx[j];
// Stores column number
// of adjacent cell
var y = pos[1] + dy[j];
// Checks if current
// cell is valid
if (valid(x, y) && mat[x][y] != 2) {
mat[x][y] = 2;
// Burn all the adjacent
// cells of current cell
fQ.push([x, y]);
}
}
}
}
return -1;
}
// Driver Code
// Given grid
var grid = [ [ 0, 0, 0, 0 ],
[ 2, 0, 0, 0 ],
[ 2, 1, 0, 0 ],
[ 2, 2, 0, 0 ] ];
document.write( minStep(grid));
// This code is contributed by rutvik_56.
</script>
Producción:
2
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)