13616번 - Letras 다국어

Os parques na Cidade da Lógica são reticulados de N × N quadrados (2 ≤ N ≤ 100), onde cada quadrado contém uma das 10 primeiras letras ASCII, abcdefghijABCDEFGHIJ, em caixa minúscula ou maiúscula. As pessoas na Cidade da Lógica têm orgulho de seguir apenas caminhos consistentes quando cruzam os parques. Por exemplo, se eles passam por um c minúsculo, eles não vão se permitir, mais adiante, passar por um C maiúsculo. Para definir isso mais precisamente, um caminho consistente é uma sequência de quadrados satisfazendo: quadrados consecutivos na sequência são adjacentes ortogonalmente; nenhuma letra ocorre na sequência tanto minúscula quanto maiúscula. Quer dizer, ou a letra não está na sequência, ou ela ocorre apenas em caixa minúscula, ou somente em caixa maiúscula.

DdaAaA D.....
CBAcca C.....
eEaeeE e.....
bBbabB b.bab.
DbDdDc DbD.D.
fFaAaC ....aC

Você deve escrever um programa para ajudar as pessoas da Cidade da Lógica a computar o comprimento do menor caminho consistente entre o quadrado de coordenadas (1, 1), no canto superior esquerdo, e o quadrado de coordenadas (N, N ), no canto inferior direito. Por exemplo, para o parque acima, o menor caminho consistente tem comprimento 13.

A primeira linha da entrada contém um inteiro N (2 ≤ N ≤ 100), o tamanho do parque. As N linhas seguintes contêm, cada uma, uma sequência de N letras, definindo o parque.

Seu programa deve imprimir uma linha contendo um inteiro, o comprimento de um caminho consistente mínimo. Se não houver um caminho consistente, imprima -1.