Dada una array de dimensiones N*M que consta de los caracteres ‘M’ , ‘#’ , ‘.’ y solo una única instancia de ‘A’ . La tarea es imprimir cualquier ruta desde la celda que tiene el valor A hasta cualquier celda del borde de la array de acuerdo con las siguientes reglas:
- Cada segundo, la ruta desde la celda ‘A’ puede moverse en las cuatro celdas adyacentes que tienen ‘.’ solo personajes. Los caracteres L , R , U y D representan las direcciones de la celda (X – 1, Y) , (X + 1, Y) , (X, Y – 1) y (X, Y + 1) moviéndose respectivamente de la celda (X, Y) .
- Las celdas que tienen los caracteres ‘#’ y ‘M’ son las celdas de bloque.
- Cada segundo, la celda que tiene los caracteres ‘M’ se propaga en las cuatro direcciones del tiempo simultáneamente con el carácter ‘A’ .
Nota: Si no existe tal ruta desde A a ninguna celda del borde de la array, imprima «-1» .
Ejemplos:
Entrada: mat[][] = {{‘#’, ‘M’, ‘.’}, {‘#’, ‘A’, ‘M’}, {‘#’, ‘.’, ‘#’} }
Salida: D
Explicación:
La array cambia de la siguiente manera:
Por lo tanto, yendo 1 celda hacia abajo, se pueden alcanzar las celdas del borde.
Entrada: mat[][] = {{‘#’, ‘#’, ‘#’, ‘#’, ‘#’, ‘#’, ‘#’, ‘#’}, {‘#’, ‘M ‘, ‘.’, ‘.’, ‘SOY’, ‘# ‘, ‘.’, ‘#’}, {‘#’, ‘.’, ‘#’, ‘.’, ‘.’, ‘#’, ‘.’, ‘.’}, {‘5’, ‘#’, ‘.’, ‘#’, ‘#’, ‘#’, ‘#’, ‘#’, ‘#’}}
Salida: RRDDR
Enfoque: el problema dado se puede resolver simulando primero el BFS multifuente en la cuadrícula para todas las celdas de bloque ‘M’ y luego realizar BFS desde la celda ‘A’ para verificar si se puede alcanzar o no alguna celda de borde. Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos G[][] que almacena el mínimo para llegar a la celda que tiene valores ‘.’ de todas las celdas que tienen el valor ‘M’ .
- Realice el BFS multifuente de todas las celdas que tengan valores ‘M’ para encontrar el tiempo mínimo para llegar a cada celda desde su celda más cercana que tenga ‘M’ y guárdela en la array G[][] .
- Inicialice una array, digamos parent[][] para almacenar el padre de cada celda, digamos (X, Y) cuando se realice cualquier movimiento a la celda (X, Y) .
- Realice el BFS Traversal en la cuadrícula desde la posición donde aparece ‘A’ , digamos (SX, SY) siguiendo los siguientes pasos:
- Empuje la celda actual (SX, SY) con la distancia como 0 en la cola .
- Iterar hasta que la cola no esté vacía y realizar los siguientes pasos:
- Haga estallar la celda frontal almacenada en la cola .
- Iterar a través de todas las celdas adyacentes válidas del Node emergente actual y empujar la celda adyacente con el tiempo de descubrimiento incrementado desde la celda emergente en la cola.
- Actualice el padre de la celda movida desde la celda actual en los pasos anteriores.
- Si la celda adyacente es la celda del borde, almacene esta celda, digamos (EX, EY) , y salga del bucle .
- Si no se alcanza el borde de la array, imprima «-1» . De lo contrario, imprima la ruta siguiendo los pasos a continuación:
- Iterar hasta que la celda final (EX, EY) no sea la misma que la celda inicial (SX, SY) :
- Encuentre el padre de la celda final y actualice la celda (EX, EY) a su celda principal.
- Imprima las direcciones L , R , U y D de acuerdo con la diferencia entre la celda final actual y su celda principal.
- Iterar hasta que la celda final (EX, EY) no sea la misma que la celda inicial (SX, SY) :
A continuación se muestra una implementación del enfoque anterior:
C++
// C++ program for tha above approach
#include <bits/stdc++.h>
using namespace std;
#define largest 10000000
// store the grid (2-d grid)
vector<vector<int> > g;
// store the coordinates of the 'M' cells
vector<pair<int, int> > M;
// record the parent of a index
vector<vector<pair<pair<int, int>, int> > > parent;
// start indices of A
int sx, sy;
// For traversing to adjacent cells
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, -1, 0, 1 };
// rows, columns, end-x, end-y
int n, m, ex = -1, ey = -1;
// function to check if the index
// to be processed is valid or not
bool isvalid(int x, int y)
{
// should not exceed any of the boundary walls
if (x < 1 || x > n || y < 0 || y > m)
return false;
// if current cell has '#'
if (g[x][y] == largest + 1)
return false;
return true;
}
// function to check if the current
// index is at border ornot
bool isborder(int x, int y)
{
if (x == 1 || y == 1 || x == n || y == m)
return true;
return false;
}
// function to get the direction when
// movement is made from (x --> ex) and (y --> ey)
char cal(int x, int y, int ex, int ey)
{
if (x + 1 == ex && y == ey)
return 'D';
if (x - 1 == ex && y == ey)
return 'U';
if (x == ex && y + 1 == ey)
return 'R';
return 'L';
}
// Function for the multisource
// bfs on M's to store the timers
void fillMatrix()
{
// queue to store index
// for bfs and shortest time
// for each (i, j)
queue<pair<pair<int, int>, int> > q;
for (auto m : M) {
// time at this moment is passed as zero
q.push({ m, 0 });
// insert time 0 for this (x, y)
g[m.first][m.second] = 0;
}
// process till the queue becomes empty
while (!q.empty()) {
// get the index and time of
// the element at front of queue
int x = q.front().first.first;
int y = q.front().first.second;
int time = q.front().second;
// remove it
q.pop();
// iterate to all the positions
// from the given position i.e.
// (x+1, y), (x-1, y), (x, y+1), (x, y-1)
for (auto i : { 0, 1, 2, 3 }) {
int newx = x + dx[i];
int newy = y + dy[i];
// check for validity of current index
if (!isvalid(newx, newy))
continue;
// not visited before
if (g[newx][newy] == -1) {
// update time
g[newx][newy] = (time + 1);
// push it into the queue
q.push({ { newx, newy }, time + 1 });
}
}
}
// in the end if there are some places on grid
// that were blocked and BFS couldn't reach there
// then just manually iterate over them and
// change them to largest +1 i.e. treat them as '#'
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == -1) {
g[i][j] = largest;
}
}
}
}
// A's BFS. It will return the time
// when A reaches boundary
// if it is not possible, it will return -1
int bfs()
{
queue<pair<pair<int, int>, int> > q;
// push the starting (x, y)
// and it's time as 0
q.push({ { sx, sy }, 0 });
while (!q.empty()) {
int x = q.front().first.first;
int y = q.front().first.second;
int time = q.front().second;
q.pop();
for (auto i : { 0, 1, 2, 3 }) {
int newx = x + dx[i];
int newy = y + dy[i];
if (!isvalid(newx, newy))
continue;
// Moving to this index is not possible
if ((time + 1) >= (g[newx][newy]))
continue;
// index to move on already has
// a parent i.e. already visited
if (parent[newx][newy].first.first != -1)
continue;
// Move to this index and mark the parents
parent[newx][newy].first.first = x;
parent[newx][newy].first.second = y;
parent[newx][newy].second = time + 1;
q.push({ { newx, newy }, time + 1 });
// if this index is a border
if (isborder(newx, newy)) {
// update ex and ey
ex = newx;
ey = newy;
return time + 1;
}
}
}
// if not possible
return -1;
}
// Function to solve the above problem
void isItPossible(vector<vector<char> > Mat)
{
// Resize the global vectors
g.resize(n + 1, vector<int>(m + 1));
parent.resize(
n + 1, vector<pair<pair<int, int>, int> >(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// initialize that no one is currently the
// parent of (i, j)
parent[i][j].first.first = -1;
parent[i][j].first.second = -1;
parent[i][j].second = -1;
char x = Mat[i - 1][j - 1];
if (x == 'M') {
// if the input character is 'M',
// push the coordinates in M and
// in the grid take 0 as input
M.push_back({ i, j });
g[i][j] = 0;
}
else if (x == 'A') {
// this is the start x and start y
sx = i, sy = j;
g[i][j] = -1;
}
else if (x == '.')
g[i][j] = -1;
// denote '#' with largest+1
else
g[i][j] = largest + 1;
}
}
// if already at the border
if (isborder(sx, sy)) {
cout << "Already a boundary cell\n";
return;
}
// Multisource bfs
fillMatrix();
// bfs of A
int time = bfs();
// if (end x) index is -1 and
// boundary has not been
if (ex == -1) {
cout << ex;
}
else {
vector<char> ans; // record the path
while (!(ex == sx && ey == sy)) {
int x = parent[ex][ey].first.first;
int y = parent[ex][ey].first.second;
// get the direction of movement
char dir = cal(x, y, ex, ey);
ans.push_back(dir);
ex = x;
ey = y;
}
reverse(ans.begin(), ans.end());
for (auto x : ans) {
cout << x;
}
}
}
// Driver code
int main()
{
// Input
vector<vector<char> > Mat = { { '#', 'M', '.' },
{ '#', 'A', 'M' },
{ '#', '.', '#' } };
n = Mat.size();
m = Mat[0].size();
// Function call
isItPossible(Mat);
return 0;
}
Producción
D
Tiempo Complejidad: O(n*m)
Espacio Auxiliar: O(n*m)
Publicación traducida automáticamente
Artículo escrito por anirudhpanwar7777 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA