Problem 2130: 2Drumuri

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.

Cerință

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 \leq i < |a|$ , 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 \leq N \leq 300$
Pentru teste în valoare de $20$ de puncte, $1 \leq N \leq 7$ .
Pentru teste în valoare de $50$ de puncte, $1 \leq N \leq 50$ .
Pentru teste în valoare de $80$ de puncte, $1 \leq N \leq 150$ .

Exemplul 1

2drumuri.in

3
abe
cef
zfq

2drumuri.out

Explicație

Drumurile sunt:

abefq: $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)$
acefq: $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$

Exemplul 2