https://ideone.com/fMSQW5
Code: Select all
#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;
}
}