#include "bits/stdc++.h"
#define maxn 105
using namespace std;
typedef pair < int , int > ii;
int mov[ 4 ] [ 4 ] = { { 1 , 0 } , { 0 , 1 } , { - 1 , 0 } , { 0 , - 1 } } ;
int l = 1 << 10 ;
int dist[ maxn ] [ maxn ] ;
char a[ maxn ] [ maxn ] ;
queue < ii > Q;
int bfs( int n, int m )
{
memset ( dist, - 1 , sizeof dist ) ;
dist[ 0 ] [ 0 ] = 1 ;
int t = a[ 0 ] [ 0 ] - 'a' ;
if ( islower ( a[ 0 ] [ 0 ] ) && ( ( m >> t ) & 1 ) ! = 0 )
return - 1 ;
if ( isupper ( a[ 0 ] [ 0 ] ) && ( ( m >> t ) & 1 ) == 0 )
return - 1 ;
ii u = ii( 0 , 0 ) , v;
Q.push ( u ) ;
while ( ! Q.empty ( ) )
{
u = Q.front ( ) ; Q.pop ( ) ;
int x = u.first , y = u.second ;
for ( int i = 0 ; i < 4 ; i++ )
{
int nx = x + mov[ i ] [ 0 ] ;
int ny = y + mov[ i ] [ 1 ] ;
if ( nx < 0 || ny < 0 || nx > n || ny > n )
continue ;
if ( dist[ nx ] [ ny ] ! = - 1 )
continue ;
int r = tolower ( a[ nx ] [ ny ] ) - 'a' ;
if ( islower ( a[ nx ] [ ny ] ) && ( ( m >> r ) & 1 ) ! = 0 )
continue ;
if ( isupper ( a[ nx ] [ ny ] ) && ( ( m >> r ) & 1 ) == 0 )
continue ;
v.first = nx, v.second = ny;
Q.push ( v ) ;
dist[ nx ] [ ny ] = 1 + dist[ x ] [ y ] ;
}
}
return dist[ n ] [ n ] ;
}
main( )
{
int n;
while ( scanf ( "%d\n " , & n ) == 1 )
{
for ( int i = 0 ; i < n; i++ )
gets ( a[ i ] ) ;
int ans = - 1 ;
for ( int mask = 0 ; mask < l; mask++ )
{
int t = bfs( n- 1 , mask ) ;
if ( t == - 1 )
continue ;
if ( ans > 0 )
ans = max( ans, t ) ;
else
ans = t;
}
cout << ans << endl;
}
}
I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCgojZGVmaW5lIG1heG4gMTA1CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHBhaXIgPCBpbnQsIGludCA+IGlpOwoKaW50IG1vdlsgNCBdWyA0IF0gPSB7IHsgMSwgMCB9LCB7IDAsIDEgfSwgeyAtMSwgMCB9LCB7IDAsIC0xIH0gfTsKCmludCBsID0gMSA8PCAxMDsKaW50IGRpc3RbIG1heG4gXVsgbWF4biBdOwpjaGFyIGFbIG1heG4gXVsgbWF4biBdOwpxdWV1ZSA8IGlpID4gUTsKCmludCBiZnMoIGludCBuLCBpbnQgbSApCnsKICBtZW1zZXQoIGRpc3QsIC0xLCBzaXplb2YgZGlzdCApOwogIGRpc3RbIDAgXVsgMCBdID0gMTsKICAKICBpbnQgdCA9IGFbIDAgXVsgMCBdIC0gJ2EnOwogIGlmKCBpc2xvd2VyKCBhWyAwIF1bIDAgXSApICYmICggKCBtID4+IHQgKSAmIDEgKSAhPSAwICkKICAgIHJldHVybiAtMTsKICBpZiggaXN1cHBlciggYVsgMCBdWyAwIF0gKSAmJiAoICggbSA+PiB0ICkgJiAxICkgPT0gMCApCiAgICByZXR1cm4gLTE7CiAgCiAgaWkgdSA9IGlpKCAwLCAwICksIHY7CiAgUS5wdXNoKCB1ICk7CiAgCiAgd2hpbGUoICEgUS5lbXB0eSgpICkKICB7CiAgICB1ID0gUS5mcm9udCgpOyBRLnBvcCgpOwogICAgaW50IHggPSB1LmZpcnN0LCB5ID0gdS5zZWNvbmQ7CiAgICAKICAgIGZvciggaW50IGkgPSAwOyBpIDwgNDsgaSsrICkKICAgIHsKICAgICAgaW50IG54ID0geCArIG1vdlsgaSBdWyAwIF07CiAgICAgIGludCBueSA9IHkgKyBtb3ZbIGkgXVsgMSBdOwogICAgICAKICAgICAgaWYoIG54IDwgMCB8fCBueSA8IDAgfHwgbnggPiBuIHx8IG55ID4gbiApCiAgICAgICAgY29udGludWU7CiAgICAgIGlmKCBkaXN0WyBueCBdWyBueSBdICE9IC0xICkKICAgICAgICBjb250aW51ZTsKICAgICAgCiAgICAgIGludCByID0gdG9sb3dlciggYVsgbnggXVsgbnkgXSApIC0gJ2EnOwogICAgICBpZiggaXNsb3dlciggYVsgbnggXVsgbnkgXSApICYmICggKCBtID4+IHIgKSAmIDEgKSAhPSAwICkKICAgICAgICBjb250aW51ZTsKICAgICAgaWYoIGlzdXBwZXIoIGFbIG54IF1bIG55IF0gKSAmJiAoICggbSA+PiByICkgJiAxICkgPT0gMCApCiAgICAgICAgY29udGludWU7CiAgICAgIAogICAgICB2LmZpcnN0ID0gbngsIHYuc2Vjb25kID0gbnk7CiAgICAgIFEucHVzaCggdiApOwogICAgICBkaXN0WyBueCBdWyBueSBdID0gMSArIGRpc3RbIHggXVsgeSBdOwogICAgfQogIH0KICAKICByZXR1cm4gZGlzdFsgbiBdWyBuIF07Cn0KCm1haW4oKQp7CiAgaW50IG47CiAgd2hpbGUoIHNjYW5mKCAiJWRcbiIsICZuICkgPT0gMSApCiAgewogICAgZm9yKCBpbnQgaSA9IDA7IGkgPCBuOyBpKysgKQogICAgICBnZXRzKCBhWyBpIF0gKTsKICAgIGludCBhbnMgPSAtMTsKICAgIGZvciggaW50IG1hc2sgPSAwOyBtYXNrIDwgbDsgbWFzaysrICkKICAgIHsKICAgICAgCiAgICAgIGludCB0ID0gYmZzKCBuLTEsIG1hc2sgKTsKICAgICAgaWYoIHQgPT0gLTEgKQogICAgICAgIGNvbnRpbnVlOwogICAgICAKICAgICAgaWYoIGFucyA+IDAgKQogICAgICAgIGFucyA9IG1heCggYW5zLCB0ICk7CiAgICAgIGVsc2UKICAgICAgICBhbnMgPSB0OwogICAgfQogICAgY291dCA8PCBhbnMgPDwgZW5kbDsKICB9CiAgCn0K
stdin
NgpEZGFBYUEKQ0JBY2NhCmVFYWVlRQpiQmJhYkIKRGJEZERjCmZGYUFhQwo3CmFBYWFhYWEKYUFhYWFBYQphQWFhYUFBCmFhQWFBYWEKQWFBYWFBYQphYUFBYUFhCmFhYWFhQWEKMgphYQphYQoyCkFBCkFhCjEKYQoyCkFBCmFhCjUKYUJjY2QKQUFBQWQKYUJjY2QKYUFBQUEKYUJjY2QKMgpCQQphYgoyCmFhCkFBCjUKYUFBYWEKYkJiQ2QKQ0JDRGUKZERkRWUKZWVlRWUKMwphYmMKYkNCCmNBYQ==
6
DdaAaA
CBAcca
eEaeeE
bBbabB
DbDdDc
fFaAaC
7
aAaaaaa
aAaaaAa
aAaaaAA
aaAaAaa
AaAaaAa
aaAAaAa
aaaaaAa
2
aa
aa
2
AA
Aa
1
a
2
AA
aa
5
aBccd
AAAAd
aBccd
aAAAA
aBccd
2
BA
ab
2
aa
AA
5
aAAaa
bBbCd
CBCDe
dDdEe
eeeEe
3
abc
bCB
cAa