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.   ii u = ii( 0, 0 ), v;
  21.   Q.push( u );
  22.  
  23.   while( ! Q.empty() )
  24.   {
  25.     u = Q.front(); Q.pop();
  26.     int x = u.first, y = u.second;
  27.  
  28.     for( int i = 0; i < 4; i++ )
  29.     {
  30.       int nx = x + mov[ i ][ 0 ];
  31.       int ny = y + mov[ i ][ 1 ];
  32.  
  33.       //Determine if coordinates are valid
  34.       if( nx < 0 || ny < 0 || nx > n || ny > n )
  35.         continue;
  36.       //Determine if coordinate has been visited before
  37.       if( dist[ nx ][ ny ] != -1 )
  38.         continue;
  39.  
  40.       //Determine if letter is allowed given the current bitmask
  41.       int r = tolower( a[ nx ][ ny ] ) - 'a';
  42.       if( islower( a[ nx ][ ny ] ) && m & ( 1 << r ) )
  43.         continue;
  44.       if( isupper( a[ nx ][ ny ] ) && ! ( m & ( 1 << r ) ) )
  45.         continue;
  46.  
  47.       v.first = nx, v.second = ny;
  48.       Q.push( v );
  49.       dist[ nx ][ ny ] = 1 + dist[ x ][ y ];
  50.     }
  51.   }
  52.  
  53.   return dist[ n ][ n ];
  54. }
  55.  
  56. main()
  57. {
  58.   int n;
  59.   while( scanf( "%d\n", &n ) == 1 )
  60.   {
  61.     for( int i = 0; i < n; i++ )
  62.       gets( a[ i ] );
  63.     int ans = -1;
  64.     for( int mask = 0; mask < l; mask++ )
  65.     {
  66.       int t = bfs( n-1, mask );
  67.       if( t == -1 )
  68.         continue;
  69.  
  70.       if( ans > 0 )
  71.         ans = max( ans, t );
  72.       else
  73.         ans = t;
  74.     }
  75.     cout << ans << endl;
  76.   }
  77.  
  78. }
  79.  
Success #stdin #stdout 0.01s 3488KB
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
stdout
copy 
13
-1
3
-1
1
https://ideone.com/fMSQW5
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!