#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;
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 ];
//Determine if coordinates are valid
if( nx < 0 || ny < 0 || nx > n || ny > n )
continue;
//Determine if coordinate has been visited before
if( dist[ nx ][ ny ] != -1 )
continue;
//Determine if letter is allowed given the current bitmask
int r = tolower( a[ nx ][ ny ] ) - 'a';
if( islower( a[ nx ][ ny ] ) && m & ( 1 << r ) )
continue;
if( isupper( a[ nx ][ ny ] ) && ! ( m & ( 1 << r ) ) )
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+IGlpOwoKaW50IG1vdlsgNCBdWyA0IF0gPSB7IHsgMSwgMCB9LCB7IDAsIDEgfSwgeyAtMSwgMCB9LCB7IDAsIC0xIH0gfTsKCmludCBsID0gMSA8PCAxMDsKaW50IGRpc3RbIG1heG4gXVsgbWF4biBdOwpjaGFyIGFbIG1heG4gXVsgbWF4biBdOwpxdWV1ZSA8IGlpID4gUTsKCmludCBiZnMoIGludCBuLCBpbnQgbSApCnsKICBtZW1zZXQoIGRpc3QsIC0xLCBzaXplb2YgZGlzdCApOwogIGRpc3RbIDAgXVsgMCBdID0gMTsKICAKICBpaSB1ID0gaWkoIDAsIDAgKSwgdjsKICBRLnB1c2goIHUgKTsKICAKICB3aGlsZSggISBRLmVtcHR5KCkgKQogIHsKICAgIHUgPSBRLmZyb250KCk7IFEucG9wKCk7CiAgICBpbnQgeCA9IHUuZmlyc3QsIHkgPSB1LnNlY29uZDsKICAgIAogICAgZm9yKCBpbnQgaSA9IDA7IGkgPCA0OyBpKysgKQogICAgewogICAgICBpbnQgbnggPSB4ICsgbW92WyBpIF1bIDAgXTsKICAgICAgaW50IG55ID0geSArIG1vdlsgaSBdWyAxIF07CiAgICAgIAogICAgICAvL0RldGVybWluZSBpZiBjb29yZGluYXRlcyBhcmUgdmFsaWQKICAgICAgaWYoIG54IDwgMCB8fCBueSA8IDAgfHwgbnggPiBuIHx8IG55ID4gbiApCiAgICAgICAgY29udGludWU7CiAgICAgIC8vRGV0ZXJtaW5lIGlmIGNvb3JkaW5hdGUgaGFzIGJlZW4gdmlzaXRlZCBiZWZvcmUKICAgICAgaWYoIGRpc3RbIG54IF1bIG55IF0gIT0gLTEgKQogICAgICAgIGNvbnRpbnVlOwogICAgICAKICAgICAgLy9EZXRlcm1pbmUgaWYgbGV0dGVyIGlzIGFsbG93ZWQgZ2l2ZW4gdGhlIGN1cnJlbnQgYml0bWFzawogICAgICBpbnQgciA9IHRvbG93ZXIoIGFbIG54IF1bIG55IF0gKSAtICdhJzsKICAgICAgaWYoIGlzbG93ZXIoIGFbIG54IF1bIG55IF0gKSAmJiBtICYgKCAxIDw8IHIgKSApCiAgICAgICAgY29udGludWU7CiAgICAgIGlmKCBpc3VwcGVyKCBhWyBueCBdWyBueSBdICkgJiYgISAoIG0gJiAoIDEgPDwgciApICkgKQogICAgICAgIGNvbnRpbnVlOwogICAgICAKICAgICAgdi5maXJzdCA9IG54LCB2LnNlY29uZCA9IG55OwogICAgICBRLnB1c2goIHYgKTsKICAgICAgZGlzdFsgbnggXVsgbnkgXSA9IDEgKyBkaXN0WyB4IF1bIHkgXTsKICAgIH0KICB9CiAgCiAgcmV0dXJuIGRpc3RbIG4gXVsgbiBdOwp9CgptYWluKCkKewogIGludCBuOwogIHdoaWxlKCBzY2FuZiggIiVkXG4iLCAmbiApID09IDEgKQogIHsKICAgIGZvciggaW50IGkgPSAwOyBpIDwgbjsgaSsrICkKICAgICAgZ2V0cyggYVsgaSBdICk7CiAgICBpbnQgYW5zID0gLTE7CiAgICBmb3IoIGludCBtYXNrID0gMDsgbWFzayA8IGw7IG1hc2srKyApCiAgICB7CiAgICAgIGludCB0ID0gYmZzKCBuLTEsIG1hc2sgKTsKICAgICAgaWYoIHQgPT0gLTEgKQogICAgICAgIGNvbnRpbnVlOwogICAgICAKICAgICAgaWYoIGFucyA+IDAgKQogICAgICAgIGFucyA9IG1heCggYW5zLCB0ICk7CiAgICAgIGVsc2UKICAgICAgICBhbnMgPSB0OwogICAgfQogICAgY291dCA8PCBhbnMgPDwgZW5kbDsKICB9CiAgCn0K
NgpEZGFBYUEKQ0JBY2NhCmVFYWVlRQpiQmJhYkIKRGJEZERjCmZGYUFhQwo3CmFBYWFhYWEKYUFhYWFBYQphQWFhYUFBCmFhQWFBYWEKQWFBYWFBYQphYUFBYUFhCmFhYWFhQWEKMgphYQphYQoyCkFBCkFhCjEKYQ==
6
DdaAaA
CBAcca
eEaeeE
bBbabB
DbDdDc
fFaAaC
7
aAaaaaa
aAaaaAa
aAaaaAA
aaAaAaa
AaAaaAa
aaAAaAa
aaaaaAa
2
aa
aa
2
AA
Aa
1
a