fork download
copy 
  1. #include "bits/stdc++.h"
  2.  
  3. #define maxn 105
  4. using namespace std;
  5.  
  6. typedef pair < int, int > ii;
  7.  
  8. int mov[ 4 ][ 4 ] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
  9.  
  10. int l = 1 << 10;
  11. int dist[ maxn ][ maxn ];
  12. char a[ maxn ][ maxn ];
  13. queue < ii > Q;
  14.  
  15. int bfs( int n, int m )
  16. {
  17.   memset( dist, -1, sizeof dist );
  18.   dist[ 0 ][ 0 ] = 1;
  19.  
  20.   int t = a[ 0 ][ 0 ] - 'a';
  21.   if( islower( a[ 0 ][ 0 ] ) && ( ( m >> t ) & 1 ) != 0 )
  22.     return -1;
  23.   if( isupper( a[ 0 ][ 0 ] ) && ( ( m >> t ) & 1 ) == 0 )
  24.     return -1;
  25.  
  26.   ii u = ii( 0, 0 ), v;
  27.   Q.push( u );
  28.  
  29.   while( ! Q.empty() )
  30.   {
  31.     u = Q.front(); Q.pop();
  32.     int x = u.first, y = u.second;
  33.  
  34.     for( int i = 0; i < 4; i++ )
  35.     {
  36.       int nx = x + mov[ i ][ 0 ];
  37.       int ny = y + mov[ i ][ 1 ];
  38.  
  39.       if( nx < 0 || ny < 0 || nx > n || ny > n )
  40.         continue;
  41.       if( dist[ nx ][ ny ] != -1 )
  42.         continue;
  43.  
  44.       int r = tolower( a[ nx ][ ny ] ) - 'a';
  45.       if( islower( a[ nx ][ ny ] ) && ( ( m >> r ) & 1 ) != 0 )
  46.         continue;
  47.       if( isupper( a[ nx ][ ny ] ) && ( ( m >> r ) & 1 ) == 0 )
  48.         continue;
  49.  
  50.       v.first = nx, v.second = ny;
  51.       Q.push( v );
  52.       dist[ nx ][ ny ] = 1 + dist[ x ][ y ];
  53.     }
  54.   }
  55.  
  56.   return dist[ n ][ n ];
  57. }
  58.  
  59. main()
  60. {
  61.   int n;
  62.   while( scanf( "%d\n", &n ) == 1 )
  63.   {
  64.     for( int i = 0; i < n; i++ )
  65.       gets( a[ i ] );
  66.     int ans = -1;
  67.     for( int mask = 0; mask < l; mask++ )
  68.     {
  69.  
  70.       int t = bfs( n-1, mask );
  71.       if( t == -1 )
  72.         continue;
  73.  
  74.       if( ans > 0 )
  75.         ans = max( ans, t );
  76.       else
  77.         ans = t;
  78.     }
  79.     cout << ans << endl;
  80.   }
  81.  
  82. }
  83.  
Success #stdin #stdout 0.02s 3532KB
comments (?)
stdin
copy 
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
stdout
copy 
13
-1
3
-1
1
-1
17
-1
-1
15
-1
https://ideone.com/xf0xyO
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!