Dado un objetivo de string numérica de longitud N y un conjunto de strings numéricas bloqueadas , cada una de longitud N , la tarea es encontrar el número mínimo de rotaciones circulares requeridas para convertir una string inicial que consta de solo 0 en el objetivo evitando cualquiera de las cuerdas presentes en bloqueado en cualquier paso. Si no es posible, imprima -1.
Nota: una sola rotación implica aumentar o disminuir un valor en un índice particular en 1 unidad. Como las rotaciones son circulares, 0 se puede convertir en 9 o 9 se puede convertir en 0.
Ejemplos:
Entrada: objetivo = “7531”, bloqueado = {“1543”, “7434”, “7300”, “7321”, “2427” }
Salida: 12
Explicación: “0000” -> “9000” -> “8000” – > “7000” -> “7100” -> “7200” -> “7210” -> “7310” -> “7410” -> “7510” -> “7520” -> “7530” -> “7531”
Entrada : destino = «4231», bloqueado = { «1243», «4444», «1256», «5321», «2222» }
Salida: 10
Enfoque: para resolver este problema, estamos utilizando el siguiente enfoque BFS :
- Cree un comienzo de string de longitud N que consista solo en 0. Empújelo a la cola. La cola se crea para almacenar la siguiente combinación válida posible aumentando o disminuyendo un carácter en una unidad.
- Cree un conjunto desordenado para evitar y agregue todas las strings bloqueadas en él.
- Si el inicio o el destino está presente en evitar , no se puede alcanzar el destino requerido.
- Pop start from queue y recorra todos los caracteres de start . Aumente y disminuya cada carácter en una unidad manteniendo el resto constante y verifique si la string está presente en Avoid . Si no es así y la nueva combinación no es igual al objetivo, empújela a la cola e insértela en evitar para evitar que se repita la misma combinación en el futuro.
- Una vez que se recorre toda la longitud de inicio , repita los pasos anteriores para el siguiente nivel, que son las strings válidas obtenidas desde inicio y que están actualmente presentes en la cola.
- Siga repitiendo los pasos anteriores hasta que alcance el objetivo o no queden más combinaciones y la cola se haya quedado vacía.
- En cualquier instante, si la string formada es igual al objetivo, devuelve el valor de recuento que mantiene un recuento del número de niveles de recorridos BFS. El valor de count es el número mínimo de rotaciones circulares requeridas.
- Si no se puede obtener más estado y la cola está vacía, imprima «No posible» .
A continuación se muestra la implementación de la lógica anterior:
C++
// C++ Program to count the minimum
// number of circular rotations required
// to obtain a given numeric strings
// avoiding a set of blocked strings
#include <bits/stdc++.h>
using namespace std;
int minCircularRotations(
string target,
vector<string>& blocked,
int N)
{
string start = "";
for (int i = 0; i < N; i++) {
start += '0';
}
unordered_set<string> avoid;
for (int i = 0; i < blocked.size(); i++)
avoid.insert(blocked[i]);
// If the starting string needs
// to be avoided
if (avoid.find(start) != avoid.end())
return -1;
// If the final string needs
// to be avoided
if (avoid.find(target) != avoid.end())
return -1;
queue<string> qu;
qu.push(start);
// Variable to store count of rotations
int count = 0;
// BFS Approach
while (!qu.empty()) {
count++;
// Store the current size
// of the queue
int size = qu.size();
for (int j = 0; j < size; j++) {
string st = qu.front();
qu.pop();
// Traverse the string
for (int i = 0; i < N; i++) {
char ch = st[i];
// Increase the
// current character
st[i]++;
// Circular rotation
if (st[i] > '9')
st[i] = '0';
// If target is reached
if (st == target)
return count;
// If the string formed
// is not one to be avoided
if (avoid.find(st)
== avoid.end())
qu.push(st);
// Add it to the list of
// strings to be avoided
// to prevent visiting
// already visited states
avoid.insert(st);
// Decrease the current
// value by 1 and repeat
// the similar checkings
st[i] = ch - 1;
if (st[i] < '0')
st[i] = '9';
if (st == target)
return count;
if (avoid.find(st)
== avoid.end())
qu.push(st);
avoid.insert(st);
// Restore the original
// character
st[i] = ch;
}
}
}
return -1;
}
// Driver code
int main()
{
int N = 4;
string target = "7531";
vector<string> blocked
= { "1543",
"7434",
"7300",
"7321",
"2427" };
cout << minCircularRotations(
target,
blocked, N)
<< endl;
return 0;
}
12
¡ Consulte el artículo completo sobre Rotaciones circulares mínimas para obtener una string numérica dada evitando un conjunto de strings dadas para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA