Se considera o lista avānd un numar cunoscut de cuvinte. Din acesta lista s-au ales doua cuvinte oarecare. Se doreste transformarea primului cuvānt īn cel de-al doilea, trecānd prin cuvinte intermediare, existente īn lista data. Trecerea dintr-un cuvānt īn altul se poate face folosind urmatoarele operatii: schimbarea, adaugarea sau stergerea unui singur caracter.
Cerinta
Dāndu-se o lista de cuvinte si doua cuvinte din aceasta, gasiti cea mai scurta secventa de operatii care transforma primul cuvānt īn cel de-al doilea folosind operatiile permise.
Date de intrareFisierul de intrare: CUVINTE.IN
Linia 1:
N P Q
·
trei numere naturale nenule,
reprezentānd numarul cuvintelor din lista (N), pozitia primului cuvānt
īn lista (P), respectiv pozitia celui de-al doilea cuvānt īn lista (Q);
Liniile 2..N+1: cuvant
·
aceste N linii
contin fiecare cāte un cuvānt, apartinānd listei.
Fisier de iesire: CUVINTE.OUT
Linia 1:
M
·
numar natural, reprezentānd
numarul minim de pasi necesari pentru a ajunge de la primul cuvānt la
al doilea;
Liniile 2..M+2: cuvānti
·
pe aceste linii apar īn
ordine cuvintele dintr-o secventa ce respecta cerinta problemei (cāte un cuvānt
pe linie), inclusiv primul cuvānt al secventei.
Exemplul 1
CUVINTE.IN |
CUVINTE.OUT |
Exemplul 2
CUVINTE.IN |
CUVINTE.OUT |
Timp maxim de executare/test: 2 secunde