## 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

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

### Re: 12797 - Letters

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

}
``````

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

### Re: 12797 - Letters

@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

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

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