Moldovan Robert (use KN) (moldovan_robert_lol) Cerința
Se dă o matrice de mărime N pe N care conține litere ale alfabetului englez. Definim un drum dreapta-jos ca fiind un șir de celule ale matricei care începe cu celula (1, 1), se termină cu celula (N, N), iar pentru fiecare celulă (x, y) din drum (exceptând ultima), succesoarea sa este fie (x+1, y), fie (x, y+1). Spunem că șirul de caractere generat de un drum în matrice este șirul obținut prin concatenarea valorilor celulelor drumului în ordine.
Să se găsească 2 drumuri dreapta-jos care nu se intersectează (decât în celulele (1, 1) și (N, N)) pentru care coeficientul de similaritate este maxim. Coeficientul de similaritate a 2 drumuri reprezintă numărul de poziții i pentru care a[i] = b[i], 0 ≤ i < lungime(a), lungime(b), unde a și b sunt șirurile generate de cele 2 drumuri.
Date de intrare
Prima linie conține valoarea lui N. Următoarele N linii conțin câte N litere mici ale alfabetului englez, reprezentând matricea.
Date de ieșire
Prima linie va conține coeficientul maxim de similaritate între 2 drumuri dreapta jos care nu se interesectează decât în capete.
Restricții și precizări
1 ≤ N ≤ 300
Punctare
- Pentru teste în valoare de
20de puncte,1 ≤ N ≤ 7. - Pentru teste în valoare de
50de puncte,1 ≤ N ≤ 50. - Pentru teste în valoare de
80de puncte,1 ≤ N ≤ 150.
Exemplu 1:
douadrumuri.in
3 abe cef zfq
douadrumuri.out
4
Exemplu 2:
douadrumuri.in
4 abcd bcde aaaa zdef
douadrumuri.out
5
Explicații
În primul exemplu, drumurile sunt:
(1, 1) → (1, 2) → (1, 3) → (2, 3) → (3, 3)(1, 1) → (2, 1) → (2, 2) → (3, 2) → (3, 3)
Șirurile generate de acestea sunt:
abefqacefq