12797 - Letters

All about problems in Volume 127. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
satirmo
New poster
Posts: 3
Joined: Sat Oct 11, 2014 6:23 am

Re: 12797 - Letters

Post by satirmo » Fri Jan 02, 2015 7:41 am

Hello. I've been having trouble solving this problem. It seems to require simply trying all possible combinations and using a BFS to find the shortest distance. Perhaps I am getting stuck on a corner case.

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;
  }
  
}

bradd123
New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

Re: 12797 - Letters

Post by bradd123 » Fri Jan 02, 2015 8:08 am

@satirmo, your code fails on this test case

Code: Select all

2
aa
AA
Your code gives 3 but the answer is -1 . I think floodfill algorithm is more suitable for this type of implicit graphs. Although bfs will work fine.

satirmo
New poster
Posts: 3
Joined: Sat Oct 11, 2014 6:23 am

Re: 12797 - Letters

Post by satirmo » Sat Jan 03, 2015 1:04 am

Thank you for your response, bradd123. :]

I have fixed my code to handle the test case you mentioned, but after submitting my code, I was given another WA.

I have tested my code on ideone on a few other test cases: https://ideone.com/xf0xyO

Code:

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;
  
  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;
  }
  
}
Test Cases:

Code: Select all

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12797 - Letters

Post by brianfry713 » Thu Jan 08, 2015 2:16 am

Try the random input at:
http://www.udebug.com/UVa/12797
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 127 (12700-12799)”