Dada una array mat[][] de tamaño N*M y el destino (x, y) al que se llega desde (0, 0), la tarea es encontrar si se puede llegar al destino siguiendo los criterios dados:
- Si el valor de la celda es 0, no puede moverse a esa celda.
- Si el valor de la celda es 1, puede moverse a la celda y no necesita tener ningún valor especial.
- En todos los demás casos, primero debe recopilar ese valor antes de pasar a esa celda.
Se permiten movimientos en las cuatro direcciones (arriba, abajo, izquierda y derecha) y las posiciones donde se sitúa un valor específico se proporcionan en las teclas de nombre de un mapa .
Entrada : mat = {{1, 0, 0, 0}, {1, 1, 1, 1}, {0, 2, 0, 0}, {1, 1, 1, 1}}
teclas: {(1 , 3): 2, (2, 1): 3}, x = 3, y = 1
Salida: verdadera
Explicación: en la cuadrícula anterior, comience desde (0, 0) y
busque el valor 2 desde (1, 3). Ahora muévase a (2, 1) y llegue al destino (3, 1).Entrada : mat = {{1, 0, 0, 0}, {1, 1, 1, 1}, {0, 2, 0, 0}, {1, 1, 2, 1}}
teclas: {(1 , 3)=> 2, (2, 1)=> 3}, x = 3, y = 3
Salida: Verdadero
Enfoque: La forma de resolver el problema se basa en el concepto de BFS :
Necesitamos recopilar los valores de las celdas especiales con valores superiores a 1, por lo tanto, el recorrido de ancho primero se puede utilizar para explorar primero los niveles más cercanos y moverse en todas las direcciones para recopilar los valores y encontrar el camino para llegar al destino.
Siga los pasos mencionados a continuación para implementar la idea:
- Realice la cuadrícula transversal en anchura a partir de (0, 0) . Pueden darse tres casos:
- Caso 1 (Cuando una celda tiene un valor de 1): En este caso, simplemente empujamos esta coordenada en la cola para explorar.
- Caso 2 (cuando una celda necesita un valor especial que ya está recopilado): las celdas que requieren el valor ahora se pueden colocar en la cola para su procesamiento.
- Caso 3 (Cuando una celda necesita un valor especial que aún no se recoge). En este caso, inserte esta celda en un mapa que represente las celdas que no se pueden atravesar en ausencia de un valor. Cuando se encuentre el valor al atravesar la cuadrícula, visite todas las habitaciones que están almacenadas en el mapa que requieren este valor.
- Si se alcanza la habitación objetivo (x, y), devuelve verdadero , de lo contrario , falso .
A continuación se muestra la implementación completa de la idea anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find if
// the destination can be reached or not
string Solveable(vector<vector<int> >& mat,
map<pair<int, int>, int> Given_keys,
int xDestination, int yDestination)
{
// Contains the keys which were found while
// traversing the grid.
set<int> ListOfAvailableKeys;
ListOfAvailableKeys.insert(1);
queue<vector<int> > q;
q.push({ 0, 0 });
vector<vector<int> > dirr{
{ 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }
};
// Contains value -> ListOfCells which
// require this value.
unordered_map<int, vector<pair<int, int> > >
Unopened_Rooms;
while (!q.empty()) {
vector<int> curr = q.front();
q.pop();
// Checking if at the destination
if (curr[0] == xDestination
&& curr[1] == yDestination) {
return "True";
}
// Case 2: If the current co-ordinate
// contains any value.
if (Given_keys.find({ curr[0], curr[1] })
!= Given_keys.end()) {
int curr_key = Given_keys[{ curr[0], curr[1] }];
// Insert the found value in
// list of available values
ListOfAvailableKeys.insert(curr_key);
// Fetch the list of cells which require
// the current value and then
// push them in queue for exploration
for (int i = 0;
i < Unopened_Rooms[curr_key].size(); i++) {
q.push(
{ Unopened_Rooms[curr_key][i].first,
Unopened_Rooms[curr_key][i].second });
}
}
for (int i = 0; i < dirr.size(); i++) {
int x = curr[0] + dirr[i][0];
int y = curr[1] + dirr[i][1];
if (x < 0 || y < 0 || x >= mat.size()
|| y >= mat[0].size() || mat[x][y] == 0) {
continue;
}
// Case 3: if the cell requires a value
// that currently we don't have.
if (ListOfAvailableKeys.find(mat[x][y])
== ListOfAvailableKeys.end()) {
Unopened_Rooms[mat[x][y]].push_back(
{ x, y });
// Mark the cell as visited.
mat[x][y] = 0;
}
else {
q.push({ x, y });
// Mark that cell as visited.
mat[x][y] = 0;
}
}
}
return "False";
}
// Driver Code
int main()
{
vector<vector<int> > mat{ { 1, 0, 0, 0 },
{ 1, 1, 1, 1 },
{ 0, 2, 0, 0 },
{ 1, 1, 2, 1 } };
map<pair<int, int>, int> keys;
keys[{ 1, 1 }] = 3;
keys[{ 1, 3 }] = 2;
int x = 3, y = 3;
// Function Call
cout << Solveable(mat, keys, x, y);
return 0;
}
True
Complejidad Temporal: O(N * M)
Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por garvjuneja98 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA