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;

}

### Like this:

Like Loading...

*Related*