Boggle puzzle

for an M*N matrix, each element is a char, you can link the char with another char which is above, below, left, right of it, no diagonal , find how many words it would returned which is in the dictionary.

 

//Boggle puzzle
// for A[i][j] , it could be linked to
// same row:  A[i][j-1] ( j > 0 ), A[i][j+1] ( j < N-1)
// same col:  A[i+1][j] ( i < M-1), A[i-1][j] ( i > 0 )
// above diag : A[i-1][j-1]( i > 0, j > 0 ), A[i-1][j+1] ( i > 0, j < N-1 ) // dont' need this, I make it too complicated
// below diag : A[i+1][j-1] ( i < M-1, j > 0 ), A[i+1][j+1]( i < M-1; j < N-1 ) // don't need this, for interview purpose, just row and col would be fine

// need to return how many dictionary words could be assembled
const int M = 10;
const int N = 10;
int CountWords(char A[M][N])
{
    int counter = 0;
    for( int i = 0; i < M; i++ )
        for( int j = 0; j < N; j++ )
        {
            bool B[M][N] = { false };
            vector v;
            counter += countHelper( A, i, j, B, v );
        }
}

int countHelper( char A[][], int row, int col, bool B[][], Vector v )
{
    // if the character has already been visited then directly return
    if( row > M || col > N || B[row][col] )
    {
        return 0;
    }
    int number = 0;
    // set the flag to be true, means the character has been visited already
    B[row][col] = true;
    char a = A[row][col];
    v.push_back( a );
    if( isWord( v ) )
    {
        number++;
    }
    number += countHelper( A, row, col-1, v );
    number += countHelper( A, row, col+1, v );
    number += countHelper( A, row-1, col, v );
    number += countHelper( A, row+1, col, v );
    // very important, need to reset it after a recursive call
    // to other recursive call, this particular character should be
    // be reseted as unvisited
    B[row][col] = false;
    v.pop_back();

    return number;
}

Advertisements
This entry was posted in interview and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s