Dada una string inicial X de 3 caracteres, una string final Y de 3 caracteres y una array de strings prohibidas. La tarea es encontrar el número mínimo de clics para llegar a Y desde X.
Normas:
- Cada uno de los 3 caracteres cambia de forma circular, es decir, con cada clic puede pasar de la a a la b o de la a a la z y nunca se muestra ninguna de las palabras prohibidas.
- Si no es posible llegar a Y , imprima -1 . En cada clic, solo se puede cambiar una letra.
- Cada string prohibida tiene la forma: { “S1” “S2” “S3”} donde cada string S i contiene letras prohibidas para ese carácter.
- String prohibida = {“ac” “bx” “lw”} implica que las palabras “abl”, “cxw”, “cbl”, “abw”, “cbw”, “axl”, “axw” y “cxl” están prohibidas y nunca se mostrará.
Nota: si la string inicial X también es una posible combinación de caracteres prohibidos, el resultado también debería ser -1.
Entrada: X = “znw”, Y = “lof”, N = 4 (no de strings prohibidas)
prohibido =
{ ” qlb “, ” jcm “, ” mhoq ” },
{ ” azn “, ” piy “, ” vj ” },
{ ” by “, ” oy “, ” ubo ” },
{ ” jqm “, ” f “, ” ej ” }
Salida: el número mínimo de clics requeridos es 22
Explicación: dado que no hay combinación de las strings prohibidas dadas forma la string final Y, por lo que la string Y se vuelve válida.Por lo tanto, el número mínimo de clics necesarios se calcula como:
z – l en dirección hacia adelante por 12 clics
z – l en dirección hacia atrás por 14 clics
n – o en dirección hacia adelante por 1 clic
n – o en dirección hacia atrás por 25 clics
w – f en dirección hacia adelante por 9 clics
w – f en dirección hacia atrás por 17 clicsClics mínimos totales = 12 + 1 + 9 = 22.
Entrada: X = “bdb”, Y = “xxx”, N = 1 (nº de strings prohibidas)
prohibido = { ” ax “, ” acx “, ” bxy ” }
Salida: El número mínimo de clics requeridos es -1
Explicación: Como “xxx” es una posible combinación de caracteres prohibidos, no es posible llegar a Y desde X.
Acercarse:
Use BFS (búsqueda primero en amplitud) con ciertas modificaciones para obtener el número mínimo de clics, sin pasar por las strings prohibidas.
- Dado que cada una de las 3 posiciones puede contener alfabetos, cree una array visitada en 3D de dimensiones 26 * 26 * 26 para atravesar los estados de palabra.
- Para visualizar cada una de las palabras restringidas, cree otra array 3D de dimensiones 26 * 26 * 26 para realizar un seguimiento de las palabras que nunca deben visitarse en el recorrido.
- Dado que cada uno de los 3 caracteres cambia de forma circular, es decir, las letras cambiarán de forma circular con cada clic, es necesario tener cuidado con el módulo 26 cada vez que se alcance la siguiente letra.
- Sea el estado actual de la palabra [XYZ] . Luego, con un solo clic, es posible pasar a los siguientes 6 estados:
[ X+1 YZ ], [ X-1 YZ ], [ X Y+1 Z ], [ X Y-1 Z ], [ XY Z+1 ], [ XY Z-1 ].
- Por lo tanto, cree 3 arrays de utilidades dx, dy, dz para mantener el recorrido como un proceso optimizado. Almacene cada estado de palabra en una estructura que tenga 4 campos, a saber, a, b, c (cada uno de los 3 caracteres) y la distancia desde las palabras iniciales.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for above program.
#include <bits/stdc++.h>
using namespace std;
#define int long long int
// each node represents a word state
struct node {
int a, b, c;
// dist from starting word X
int dist;
};
// 3D visited array
bool visited[26][26][26];
// 3D restricted array
bool restricted[26][26][26];
// utility arrays for single step
// traversal in left and right
int dx[6] = { 1, -1, 0, 0, 0, 0 };
int dy[6] = { 0, 0, 1, -1, 0, 0 };
int dz[6] = { 0, 0, 0, 0, 1, -1 };
// function to find the
// minimum clicks.
void solve(string start,
string end, int qx,
const vector<vector<string> >& forbidden)
{
memset(visited, 0,
sizeof(visited));
memset(restricted, 0,
sizeof(restricted));
for (auto vec : forbidden) {
string a = vec[0];
string b = vec[1];
string c = vec[2];
for (auto x : a)
for (auto y : b)
for (auto z : c) {
// each invalid word is
// decoded and marked as
// restricted = true.
restricted[x - 'a']
[y - 'a']
[z - 'a']
= true;
}
}
// starting and ending letter a
int sa = start[0] - 'a';
int ea = end[0] - 'a';
// starting and ending letter b
int sb = start[1] - 'a';
int eb = end[1] - 'a';
// starting and ending letter c
int sc = start[2] - 'a';
int ec = end[2] - 'a';
if (restricted[sa][sb][sc]
or restricted[ea][eb][ec]) {
// check if starting word
// or finishing word is
// restricted or not
cout << -1 << endl;
return;
}
// queue of nodes for BFS
queue<node> q;
// initial starting word pushed in
// queue. dist = 0 for starting word
q.push({ sa, sb, sc, 0 });
// mark as visited
visited[sa][sb][sc] = true;
while (!q.empty()) {
node x = q.front();
q.pop();
// final destination reached condition
if (x.a == (end[0] - 'a')
and x.b == (end[1] - 'a')
and x.c == (end[2] - 'a')) {
cout << x.dist
<< endl;
return;
}
int DIST = x.dist;
for (int i = 0; i < 6; i++) {
// mod 26 for circular letter sequence
// next letter for a
int A = (x.a + dx[i] + 26) % 26;
// next letter for b
int B = (x.b + dy[i] + 26) % 26;
// next letter for c
int C = (x.c + dz[i] + 26) % 26;
if (!restricted[A][B][C]
and !visited[A][B][C]) {
// if a valid word state,
// push into queue
q.push({ A, B, C, DIST + 1 });
visited[A][B][C] = true;
}
}
}
// reach here if not possible
// to reach final word Y
cout << -1 << endl;
}
// Driver Code
signed main()
{
// starting string
string X = "znw";
// final string
string Y = "lof";
// no of restricting word vectors
int N = 4;
vector<vector<string> > forbidden
= { { "qlb", "jcm", "mhoq" },
{ "azn", "piy", "vj" },
{ "by", "oy", "ubo" },
{ "jqm", "f", "ej" } };
solve(X, Y, N, forbidden);
return 0;
}
22
Complejidad de tiempo: O (26 * 26 * 26), ya que como máximo, puede haber 26 * 26 * 26 estados de palabras.
Complejidad espacial: O (26 * 26 * 26)
Publicación traducida automáticamente
Artículo escrito por greenindia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA