Page 1 of 1

### Re: 12797 - Letters

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

}
``````

### Re: 12797 - Letters

Posted: 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.

### Re: 12797 - Letters

Posted: 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
aBccd
aAAAA
aBccd
2
BA
ab
2
aa
AA
5
aAAaa
bBbCd
CBCDe
dDdEe
eeeEe
3
abc
bCB
cAa``````

### Re: 12797 - Letters

Posted: Thu Jan 08, 2015 2:16 am
Try the random input at:
http://www.udebug.com/UVa/12797