Dada una array de array 2-D [][] de tamaño FILA * COL y un número entero K, donde cada array de celda [i][j] es 0 (vacío) o 1 (obstáculo) . Un puntero se puede mover hacia arriba, hacia abajo, hacia la izquierda o hacia la derecha desde y hacia una celda vacía en un solo paso. La tarea es encontrar el número mínimo de pasos necesarios para ir desde el origen (0, 0) hasta el destino (ROW-1, COL-1) con menos o igual a K eliminaciones de obstáculos. La eliminación de un obstáculo se define como cambiar la array de valores de una celda [i][j] de 1 a 0. Si no hay camino posible, entonces regrese-1 .
Ejemplos:
Entrada: array[][] = { {0,0,1},
{1,0,1},
{0,1,0} },
FILA = 3, COL = 3, K = 2
Salida: 4
Explicación:
Cambie el valor de matrix[0][2] y matrix[1][2] a 0 y la ruta es 0,0 -> 0,1 -> 0,2 -> 1,2 -> 2,2.
Entrada: array[][] = { {0,1,0},
{1,1,0},
{0,0,0},
{0,0,0} },
FILA = 4, COL = 3, K = 1
Salida: 5
Enfoque: la ruta más corta se puede buscar utilizando BFS en una array. Inicialice un vector de contador [] [] , esta array realizará un seguimiento de la cantidad de obstáculos restantes que se pueden eliminar para cada celda visitada. Ejecute una búsqueda de amplitud en cada celda y, al mismo tiempo, realice un seguimiento de la cantidad de obstáculos que aún podemos eliminar. En cada celda, primero, verifique si es la celda de destino o no. Luego, se verifica si la celda actual es un obstáculo y luego el conteo de eliminaciones disponibles se decrementa en 1 . Si el valor de la celda en la array de contadores tiene un valor más bajo que la variable actual, entonces se actualiza. La array de longitud se actualiza en cada paso. Siga los pasos a continuación para resolver el problema:
- Defina 2 arrays dir_Row[4] y dir_Col[4] para almacenar las coordenadas de dirección posibles desde cada punto.
- Defina una estructura pointLoc como x, y y k.
- Inicialice una cola q[] del tipo de datos pointLoc .
- Inicialice un vector 2-D de distancia[ROW][COL] con valores 0 para almacenar la distancia de cada celda desde la celda de origen.
- Inicialice un vector 2-D obstackles[ROW][COL] con valores -1 para almacenar el recuento de eliminaciones de obstáculos disponibles.
- Ponga en cola el valor {0, 0, K} en la cola q[].
- Atraviese un bucle while hasta que el tamaño de la cola q[] sea mayor que 0 y realice las siguientes tareas:
- Inicialice una variable te como el frente de la cola q[].
- Inicialice las variables x, y y tk como te.x, te.y y te.k.
- Si la celda actual es igual a la celda de destino, devuelve el valor de distancia[x][y] como respuesta.
- Retire el elemento frontal de la cola q[].
- Si la celda actual es un obstáculo, si tk es mayor que 0 , disminuya su valor en 1 ; de lo contrario, continúe.
- Si los obstáculos [x] [y] son mayores que iguales a tk , entonces continúe; de lo contrario, establezca su valor como tk.
- Itere sobre el rango [0, 4) usando la variable i y realice las siguientes tareas:
- Vea todas las celdas vecinas (ax, ay) y verifique si son celdas válidas o no. Si no, entonces continúe. De lo contrario, ponga en cola {ax, ay, tk} en la cola q[] y establezca el valor de distancia[ax][ay] como distancia[x][y] + 1.
- Después de realizar los pasos anteriores, imprima el valor -1 si no se encuentra una respuesta.
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;
#define ROW 3
#define COL 3
// Direction Vectors
int dir_Row[4] = { -1, 0, 1, 0 };
int dir_Col[4] = { 0, 1, 0, -1 };
// Structure for storing coordinates
// count of remaining obstacle eliminations
struct pointLoc {
int x, y, k;
};
// Function to perform BFS
int BFS(int matrix[][COL], int k, pair<int, int> source,
pair<int, int> destination)
{
// Stores pointLoc of each cell
queue<struct pointLoc> q;
// Vector array to store distance of
// each cell from source cell
vector<vector<int> > distance(
ROW, vector<int>(COL, 0));
// Vector array to store count of
// available obstacle eliminations
vector<vector<int> > obstacles(
ROW, vector<int>(COL, -1));
// Push the source cell into queue
// and use as starting point
q.push({ source.first, source.second, k });
// Iterate while queue is not empty
while (!q.empty()) {
struct pointLoc te = q.front();
int x = te.x;
int y = te.y;
int tk = te.k;
// If current cell is same as
// destination then return distance
if (x == destination.first
&& y == destination.second)
return distance[x][y];
q.pop();
// If current cell is an obstacle
// then decrement current value
// if possible else skip the cell
if (matrix[x][y] == 1) {
if (tk > 0)
tk--;
else
continue;
}
// Cell is skipped only if current
// value is less than previous
// value of cell
if (obstacles[x][y] >= tk)
continue;
// Else update value
obstacles[x][y] = tk;
// Push all valid adjacent
// cells into queue
for (int i = 0; i < 4; i++) {
int ax = x + dir_Row[i];
int ay = y + dir_Col[i];
if (ax < 0 || ay < 0
|| ax >= ROW || ay >= COL)
continue;
q.push({ ax, ay, tk });
// Update distance of current
// cell from source cell
distance[ax][ay] = distance[x][y] + 1;
}
}
// If not possible to reach
// destination from source
return -1;
}
// Driver Code
int main()
{
// Given input
int matrix[ROW][COL]
= { { 0, 0, 1 },
{ 1, 0, 1 },
{ 0, 1, 0 } };
int k = 2;
pair<int, int> source = { 0, 0 };
pair<int, int> destination = { 2, 2 };
cout << BFS(matrix, k, source, destination);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
static final int ROW = 3;
static final int COL = 3;
// Direction Vectors
static int dir_Row[] = { -1, 0, 1, 0 };
static int dir_Col[] = { 0, 1, 0, -1 };
// Structure for storing coordinates
// count of remaining obstacle eliminations
static class pointLoc {
int x, y, k;
public pointLoc(int x, int y, int k) {
super();
this.x = x;
this.y = y;
this.k = k;
}
};
static class pair {
int first, second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
// Function to perform BFS
static int BFS(int matrix[][], int k, pair source, pair destination) {
// Stores pointLoc of each cell
Queue<pointLoc> q = new LinkedList<GFG.pointLoc>();
// Vector array to store distance of
// each cell from source cell
int[][] distance = new int[ROW][COL];
// Vector array to store count of
// available obstacle eliminations
int[][] obstacles = new int[ROW][COL];
// Push the source cell into queue
// and use as starting point
q.add(new pointLoc(source.first, source.second, k));
// Iterate while queue is not empty
while (!q.isEmpty()) {
pointLoc te = q.peek();
int x = te.x;
int y = te.y;
int tk = te.k;
// If current cell is same as
// destination then return distance
if (x == destination.first && y == destination.second)
return distance[x][y];
q.remove();
// If current cell is an obstacle
// then decrement current value
// if possible else skip the cell
if (matrix[x][y] == 1) {
if (tk > 0)
tk--;
else
continue;
}
// Cell is skipped only if current
// value is less than previous
// value of cell
if (obstacles[x][y] >= tk)
continue;
// Else update value
obstacles[x][y] = tk;
// Push all valid adjacent
// cells into queue
for (int i = 0; i < 4; i++) {
int ax = x + dir_Row[i];
int ay = y + dir_Col[i];
if (ax < 0 || ay < 0 || ax >= ROW || ay >= COL)
continue;
q.add(new pointLoc(ax, ay, tk));
// Update distance of current
// cell from source cell
distance[ax][ay] = distance[x][y] + 1;
}
}
// If not possible to reach
// destination from source
return -1;
}
// Driver Code
public static void main(String[] args) {
// Given input
int matrix[][] = { { 0, 0, 1 }, { 1, 0, 1 }, { 0, 1, 0 } };
int k = 2;
pair source = new pair(0, 0);
pair destination = new pair(2, 2);
System.out.print(BFS(matrix, k, source, destination));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python Program to implement # the above approach ROW = 3 COL = 3 # Direction Vectors dir_Row = [-1, 0, 1, 0] dir_Col = [0, 1, 0, -1] # Structure for storing coordinates # count of remaining obstacle eliminations class pointLoc: def __init__(self,x, y, k): self.x = x self.y = y self.k = k # Function to perform BFS def BFS(matrix, k, source,destination): # Stores pointLoc of each cell q = [] # Vector array to store distance of # each cell from source cell distance = [0 for i in range(ROW)] for i in range(len(distance)): distance[i] = [0 for i in range(COL)] # Vector array to store count of # available obstacle eliminations obstacles = [0 for i in range(ROW)] for i in range(len(obstacles)): obstacles[i] = [-1 for i in range(COL)] # Push the source cell into queue # and use as starting point q.append(pointLoc(source[0], source[1], k)) # Iterate while queue is not empty while (len(q) > 0): te = q[0] x = te.x y = te.y tk = te.k # If current cell is same as # destination then return distance if (x == destination[0] and y == destination[1]): return distance[x][y] q = q[1:] # If current cell is an obstacle # then decrement current value # if possible else skip the cell if (matrix[x][y] == 1): if (tk > 0): tk -= 1 else: continue # Cell is skipped only if current # value is less than previous # value of cell if (obstacles[x][y] >= tk): continue # Else update value obstacles[x][y] = tk # Push all valid adjacent # cells into queue for i in range(4): ax = x + dir_Row[i] ay = y + dir_Col[i] if (ax < 0 or ay < 0 or ax >= ROW or ay >= COL): continue q.append(pointLoc(ax, ay, tk)) # Update distance of current # cell from source cell distance[ax][ay] = distance[x][y] + 1 # If not possible to reach # destination from source return -1 # Driver Code # Given input matrix = [[0, 0, 1],[1, 0, 1],[0, 1, 0]] k = 2 source = [0, 0] destination = [2, 2] print(BFS(matrix, k, source, destination)) # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static readonly int ROW = 3;
static readonly int COL = 3;
// Direction Lists
static int []dir_Row = { -1, 0, 1, 0 };
static int []dir_Col = { 0, 1, 0, -1 };
// Structure for storing coordinates
// count of remaining obstacle eliminations
class pointLoc
{
public int x, y, k;
public pointLoc(int x, int y, int k)
{
this.x = x;
this.y = y;
this.k = k;
}
};
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to perform BFS
static int BFS(int [,]matrix, int k, pair source,
pair destination)
{
// Stores pointLoc of each cell
Queue<pointLoc> q = new Queue<GFG.pointLoc>();
// List array to store distance of
// each cell from source cell
int[,] distance = new int[ROW, COL];
// List array to store count of
// available obstacle eliminations
int[,] obstacles = new int[ROW, COL];
// Push the source cell into queue
// and use as starting point
q.Enqueue(new pointLoc(source.first,
source.second, k));
// Iterate while queue is not empty
while (q.Count != 0)
{
pointLoc te = q.Peek();
int x = te.x;
int y = te.y;
int tk = te.k;
// If current cell is same as
// destination then return distance
if (x == destination.first &&
y == destination.second)
return distance[x, y];
q.Dequeue();
// If current cell is an obstacle
// then decrement current value
// if possible else skip the cell
if (matrix[x, y] == 1)
{
if (tk > 0)
tk--;
else
continue;
}
// Cell is skipped only if current
// value is less than previous
// value of cell
if (obstacles[x, y] >= tk)
continue;
// Else update value
obstacles[x, y] = tk;
// Push all valid adjacent
// cells into queue
for(int i = 0; i < 4; i++)
{
int ax = x + dir_Row[i];
int ay = y + dir_Col[i];
if (ax < 0 || ay < 0 ||
ax >= ROW || ay >= COL)
continue;
q.Enqueue(new pointLoc(ax, ay, tk));
// Update distance of current
// cell from source cell
distance[ax, ay] = distance[x, y] + 1;
}
}
// If not possible to reach
// destination from source
return -1;
}
// Driver Code
public static void Main(String[] args)
{
// Given input
int [,]matrix = { { 0, 0, 1 },
{ 1, 0, 1 },
{ 0, 1, 0 } };
int k = 2;
pair source = new pair(0, 0);
pair destination = new pair(2, 2);
Console.Write(BFS(matrix, k, source, destination));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to implement
// the above approach
let ROW = 3
let COL = 3
// Direction Vectors
let dir_Row = [-1, 0, 1, 0];
let dir_Col = [0, 1, 0, -1];
// Structure for storing coordinates
// count of remaining obstacle eliminations
class pointLoc {
constructor(x, y, k) {
this.x = x;
this.y = y;
this.k = k;
}
};
// Function to perform BFS
function BFS(matrix, k, source,
destination) {
// Stores pointLoc of each cell
let q = [];
// Vector array to store distance of
// each cell from source cell
let distance = new Array(ROW);
for (let i = 0; i < distance.length; i++) {
distance[i] = new Array(COL).fill(0);
}
// Vector array to store count of
// available obstacle eliminations
let obstacles = new Array(ROW);
for (let i = 0; i < obstacles.length; i++) {
obstacles[i] = new Array(COL).fill(-1);
}
// Push the source cell into queue
// and use as starting point
q.push(new pointLoc(source[0], source[1], k));
// Iterate while queue is not empty
while (q.length > 0) {
let te = q[0];
let x = te.x;
let y = te.y;
let tk = te.k;
// If current cell is same as
// destination then return distance
if (x == destination[0]
&& y == destination[1])
return distance[x][y];
q.shift();
// If current cell is an obstacle
// then decrement current value
// if possible else skip the cell
if (matrix[x][y] == 1) {
if (tk > 0)
tk--;
else
continue;
}
// Cell is skipped only if current
// value is less than previous
// value of cell
if (obstacles[x][y] >= tk)
continue;
// Else update value
obstacles[x][y] = tk;
// Push all valid adjacent
// cells into queue
for (let i = 0; i < 4; i++) {
let ax = x + dir_Row[i];
let ay = y + dir_Col[i];
if (ax < 0 || ay < 0
|| ax >= ROW || ay >= COL)
continue;
q.push(new pointLoc(ax, ay, tk));
// Update distance of current
// cell from source cell
distance[ax][ay] = distance[x][y] + 1;
}
}
// If not possible to reach
// destination from source
return -1;
}
// Driver Code
// Given input
let matrix
= [[0, 0, 1],
[1, 0, 1],
[0, 1, 0]];
let k = 2;
let source = [0, 0];
let destination = [2, 2];
document.write(BFS(matrix, k, source, destination));
// This code is contributed by Potta Lokesh
</script>
Producción
4
Complejidad de tiempo: O( FILA*COL *K)
Espacio auxiliar: O( FILA*COL *K)
Publicación traducida automáticamente
Artículo escrito por mashedpotat0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA