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;
}
Java
// Java Program to count the minimum
// number of circular rotations required
// to obtain a given numeric Strings
// avoiding a set of blocked Strings
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
class GFG
{
static int minCircularRotations(String target,
ArrayList<String> blocked,
int N)
{
String start = "";
for (int i = 0; i < N; i++)
{
start += '0';
}
HashSet<String> avoid = new HashSet<>();
for (int i = 0; i < blocked.size(); i++)
avoid.add(blocked.get(i));
// If the starting String needs // to be avoided
if (avoid.contains(start))
return -1;
// If the final String needs // to be avoided
if (avoid.contains(target))
return -1;
Queue<String> qu = new LinkedList<>();
qu.add(start);
// Variable to store count of rotations
int count = 0;
// BFS Approach
while (!qu.isEmpty())
{
count++;
// Store the current size // of the queue
int size = qu.size();
for (int j = 0; j < size; j++)
{
StringBuilder st = new StringBuilder(qu.poll());
// Traverse the String
for (int i = 0; i < N; i++)
{
char ch = st.charAt(i);
// Increase the // current character
st.setCharAt(i, (char) (st.charAt(i) + 1));
// Circular rotation
if (st.charAt(i) > '9')
st.setCharAt(i, '0');
// If target is reached
if (st.toString().equals(target))
return count;
// If the String formed
// is not one to be avoided
if (!avoid.contains(st.toString()))
qu.add(st.toString());
// Add it to the list of
// Strings to be avoided
// to prevent visiting
// already visited states
avoid.add(st.toString());
// Decrease the current
// value by 1 and repeat
// the similar checkings
st.setCharAt(i, (char) (ch - 1));
if (st.charAt(i) < '0')
st.setCharAt(i, '9');
if (st.toString().equals(target))
return count;
if (!avoid.contains(st.toString()))
qu.add(st.toString());
avoid.add(st.toString());
// Restore the original
// character
st.setCharAt(i, ch);
}
}
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int N = 4;
String target = "7531";
ArrayList<String> blocked =
new ArrayList<>(Arrays.asList("1543",
"7434",
"7300",
"7321",
"2427"));
System.out.println(minCircularRotations(target, blocked, N));
}
}
// This code is contributed by sanjeev2552
Python3
# python Program to count the minimum # number of circular rotations required # to obtain a given numeric strings # avoiding a set of blocked strings def minCircularRotations(target, blocked, N): start = "" for i in range(N): start += '0' avoid = set() for i in range(len(blocked)): avoid.add(blocked[i]) # If the starting string needs # to be avoided if(start in avoid): return -1 # If the final string needs # to be avoided if(target in avoid): return -1 # Initializing a queue qu = [] qu.append(start) # Variable to store count of rotations count = 0 while(len(qu) != 0): count += 1 # Store the current size # of the queue size = len(qu) for j in range(size): st = qu[0] qu.pop(0) # Traverse the string for i in range(N): ch = st[i] # Increase the # current character list1 = list(st) list1[i] = chr(ord(ch) + 1) st = ''.join(list1) # Circular rotation if(st[i] > '9'): list1 = list(st) list1[i] = '0' st = ''.join(list1) # If target is reached if(st == target): return count # If the string formed # is not one to be avoided if(st not in avoid): qu.append(st) # Add it to the list of # strings to be avoided # to prevent visiting # already visited states avoid.add(st) # Decrease the current # value by 1 and repeat # the similar checkings list1 = list(st) list1[i] = chr(ord(ch) - 1) st = ''.join(list1) if(st[i] < '0'): list1 = list(st) list1[i] = '9' st = ''.join(list1) if(st == target): return count if(st not in avoid): qu.append(st) avoid.add(st) # Restore the original # character list1 = list(st) list1[i] = ch st = ''.join(list1) return -1 # Driver code N = 4 target = "7531" blocked = ["1543", "7434", "7300", "7321", "2427"] print(minCircularRotations(target, blocked, N)) # This code is contributed by Aarti_Rathi
C#
// C# Program to count the minimum
// number of circular rotations required
// to obtain a given numeric strings
// avoiding a set of blocked strings
using System;
using System.Collections.Generic;
using System.Text;
public class Test
{
// Function to reorder elements of arr[] according
// to index[]
static int minCircularRotations(string target, string[] blocked, int N)
{
string start = "";
for (int i = 0; i < N; i++) {
start += '0';
}
HashSet < string > avoid = new HashSet < string >();
for (int i=0; i<blocked.Length; i++)
{
avoid.Add(blocked[i]);
// If the starting string needs
// to be avoided
if (avoid.Contains(start))
return -1;
// If the final string needs
// to be avoided
if (avoid.Contains(target))
return -1;
}
Queue<string> qu = new Queue<string>();
qu.Enqueue(start);
// Variable to store count of rotations
int count = 0;
// BFS Approach
while (qu.Count != 0) {
count++;
// Store the current size
// of the queue
int size = qu.Count;
for (int j = 0; j < size; j++) {
string st = qu.Peek();
StringBuilder sb = new StringBuilder(st);
qu.Dequeue();
// Traverse the string
for (int i = 0; i < N; i++) {
char ch = st[i];
// Increase the
// current character
char c=ch;
sb[i] = ++c;
st = sb.ToString();
// Circular rotation
if (st[i] > '9')
{
sb[i] = '0';
st = sb.ToString();
}
// If target is reached
if (st == target)
return count;
// If the string formed
// is not one to be avoided
if (!avoid.Contains(st))
qu.Enqueue(st);
// Add it to the list of
// strings to be avoided
// to prevent visiting
// already visited states
avoid.Add(st);
// Decrease the current
// value by 1 and repeat
// the similar checkings
c=ch;
sb[i] = --c;
st = sb.ToString();
if (st[i] < '0')
{
sb[i] = '9';
st = sb.ToString();
}
if (st == target)
return count;
if (!avoid.Contains(st))
qu.Enqueue(st);
avoid.Add(st);
// Restore the original
// character
sb[i] = ch;
st = sb.ToString();
}
}
}
return -1;
}
// Driver Code
static void Main()
{
int n=4;
string target = "7531";
string[] blocked = new string[]{ "1543",
"7434",
"7300",
"7321",
"2427" };
Console.WriteLine(minCircularRotations(target,blocked, n));
}
}
// This code is contributed by Aditya_Kumar
Producción:
12
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)