find_the_word_in_the_crossword_puzzle_v1.c

/*

    find_the_word_in_the_crossword_puzzle_v1.c

    Task:
    https://www.facebook.com/photo/?fbid=1487687438086412&set=gm.788787108602994
    Picture of task:
    http://www.mediafire.com/view/atbcm8jbg06i7uk/Task+substrings+in+table.jpg/file


    I think we need to work with a character matrix M[n][n] .
    char M[n][n];

    8 possible directions for the required word should be introduced:
    Up, Down, Left, Right, UpLeft, UpRight, DownLeft, DownRight.

    Then you should go in order on the matrix
    until you find the first letter from the required word.
    In all 8 directions, examine whether there is a required word,
    ie whether in the given direction the next letter is equal to the
    next letter of the required word and so on until the end of the required word.
    If the search word in that direction exists, increase the counter.
    Be careful not to exceed the matrix limits during the test.
    Repeat this until the end of the matrix M[n*n].


    You can find all my C programs at Dragan Milicev's pastebin:

    https://pastebin.com/u/dmilicev

*/

#include <stdio.h>

#define MAX_SIZE 1000   // max size of requested word in matrix M[MAX_SIZE][MAX_SIZE]
#define UP          0   // define 8 possible directions
#define DOWN        1
#define LEFT        2
#define RIGHT       3
#define UP_LEFT     4
#define UP_RIGHT    5
#define DOWN_LEFT   6
#define DOWN_RIGHT  7


// Displays characters of the matrix M[r][c] that has r rows and c columns
void print_matrix( char *text, char M[][MAX_SIZE], int r, int c )
{
    int i, j;

    printf("%s", text );

    for(i=0;i<r;i++) {
        for(j=0;j<c;j++)
            printf(" %c ", M[i][j] );

        printf("\n\n");
    }
}


// Returns the number of occurrences of the requested word in the matrix M
int number_off_occurrences( char word[], char M[][MAX_SIZE], int rows, int columns )
{
    int i, row, column, r, c, counter=0, direction, end_of_table, end_of_word, match;
    // i is index of word characters
    // row and column are coordinates of matrix character that we examine in all directions
    // r and c are current row and column (auxiliary coordinates)
    // rows and columns are the sizes of the whole matrix M

    // Let's go in order by the elements of the matrix.
    // When we come across an element of the matrix that is equal to the first
    // character of the requested word, we process that element in all directions,
    // looking for the following characters of the requested word.
    for( row=0; row<rows; row++ )
    {
        for( column=0; column<columns; column++ )
        {
            i = 0;

            if( M[row][column] == word[i] )             // character of M equal to first character of word
            {
                direction = 0;

                while( direction < 8 )
                {
                    i = 0;                              // index of first character of word
                    match = 1;                          // first character of word and character of matrix M match
                    end_of_table = 0;                   // it is not yet end of table
                    end_of_word = 0;                    // it is not yet end of word
                    r = row;                            // from current row
                    c = column;                         // from current column

                    switch( direction++ )
                    {
                    case UP :
                        while( match && !end_of_word && !end_of_table ) // while three conditions
                        {
                            if( r >= 0 )                        // if can go UP in matrix M
                                r--;                            // go UP in matrix M
                            else
                                end_of_table = 1;               // if can't go UP in matrix M, end

                            if( word[++i] == '\0' )             // if we reach the end of word,
                                end_of_word = 1;                // it is the end of word

                            if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
                                match = 0;                      // they don't match
                        } // while( match && !end_of_word && !end_of_table )

                        if( match )                             // if all characters of word are match
                        {
                            counter++;                          // count that word
                            printf("\n M[%d][%d] = %c \t found UP \n", row+1, column+1, M[row][column] );
                        }
                        break;

                    case DOWN :
                        while( match && !end_of_word && !end_of_table ) // while three conditions
                        {
                            if( r < rows )                      // if can go DOWN in matrix M
                                r++;                            // go DOWN in matrix M
                            else
                                end_of_table = 1;               // if can't go DOWN in matrix M, end

                            if( word[++i] == '\0' )             // if we reach the end of word,
                                end_of_word = 1;                // it is the end of word

                            if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
                                match = 0;                      // they don't match
                        } // while( match && !end_of_word && !end_of_table )

                        if( match )                             // if all characters of word are match
                        {
                            counter++;                          // count that word
                            printf("\n M[%d][%d] = %c \t found DOWN \n", row+1, column+1, M[row][column] );
                        }
                        break;

                    case LEFT :
                        while( match && !end_of_word && !end_of_table ) // while three conditions
                        {
                            if( c >= 0 )                        // if can go LEFT in matrix M
                                c--;                            // go LEFT in matrix M
                            else
                                end_of_table = 1;               // if can't go LEFT in matrix M, end

                            if( word[++i] == '\0' )             // if we reach the end of word,
                                end_of_word = 1;                // it is the end of word

                            if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
                                match = 0;                      // they don't match
                        } // while( match && !end_of_word && !end_of_table )

                        if( match )                             // if all characters of word are match
                        {
                            counter++;                          // count that word
                            printf("\n M[%d][%d] = %c \t found LEFT \n", row+1, column+1, M[row][column] );
                        }
                        break;

                    case RIGHT :
                        while( match && !end_of_word && !end_of_table ) // while three conditions
                        {
                            if( c < rows )                      // if can go RIGHT in matrix M
                                c++;                            // go RIGHT in matrix M
                            else
                                end_of_table = 1;               // if can't go RIGHT in matrix M, end

                            if( word[++i] == '\0' )             // if we reach the end of word,
                                end_of_word = 1;                // it is the end of word

                            if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
                                match = 0;                      // they don't match
                        } // while( match && !end_of_word && !end_of_table )

                        if( match )                             // if all characters of word are match
                        {
                            counter++;                          // count that word
                            printf("\n M[%d][%d] = %c \t found RIGHT \n", row+1, column+1, M[row][column] );
                        }
                        break;

                    case UP_LEFT :
                        while( match && !end_of_word && !end_of_table ) // while three conditions
                        {
                            if( r >= 0 && c >=0)                // if can go UP_LEFT in matrix M
                            {
                                r--;                            // go UP in matrix M
                                c--;                            // go LEFT in matrix M
                            }
                            else
                                end_of_table = 1;               // if can't go UP_LEFT in matrix M, end

                            if( word[++i] == '\0' )             // if we reach the end of word,
                                end_of_word = 1;                // it is the end of word

                            if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
                                match = 0;                      // they don't match
                        } // while( match && !end_of_word && !end_of_table )

                        if( match )                             // if all characters of word are match
                        {
                            counter++;                          // count that word
                            printf("\n M[%d][%d] = %c \t found UP_LEFT \n", row+1, column+1, M[row][column] );
                        }
                        break;

                    case UP_RIGHT :
                        while( match && !end_of_word && !end_of_table ) // while three conditions
                        {
                            if( r >= 0 && c < columns )         // if can go UP_RIGHT in matrix M
                            {
                                r--;                            // go UP in matrix M
                                c++;                            // go RIGHT in matrix M
                            }
                            else
                                end_of_table = 1;               // if can't go UP_RIGHT in matrix M, end

                            if( word[++i] == '\0' )             // if we reach the end of word,
                                end_of_word = 1;                // it is the end of word

                            if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
                                match = 0;                      // they don't match
                        } // while( match && !end_of_word && !end_of_table )

                        if( match )                             // if all characters of word are match
                        {
                            counter++;                          // count that word
                            printf("\n M[%d][%d] = %c \t found UP_RIGHT \n", row+1, column+1, M[row][column] );
                        }
                        break;

                    case DOWN_LEFT :
                        while( match && !end_of_word && !end_of_table ) // while three conditions
                        {
                            if( r < rows && c >= 0 )            // if can go DOWN_LEFT in matrix M
                            {
                                r++;                            // go DOWN in matrix M
                                c--;                            // go LEFT in matrix M
                            }
                            else
                                end_of_table = 1;               // if can't go DOWN_LEFT in matrix M, end

                            if( word[++i] == '\0' )             // if we reach the end of word,
                                end_of_word = 1;                // it is the end of word

                            if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
                                match = 0;                      // they don't match
                        } // while( match && !end_of_word && !end_of_table )

                        if( match )                             // if all characters of word are match
                        {
                            counter++;                          // count that word
                            printf("\n M[%d][%d] = %c \t found DOWN_LEFT \n", row+1, column+1, M[row][column] );
                        }
                        break;

                    case DOWN_RIGHT :
                        while( match && !end_of_word && !end_of_table ) // while three conditions
                        {
                            if( r < rows && c < columns )       // if can go DOWN_RIGHT in matrix M
                            {
                                r++;                            // go DOWN in matrix M
                                c++;                            // go RIGHT in matrix M
                            }
                            else
                                end_of_table = 1;               // if can't go DOWN_RIGHT in matrix M, end

                            if( word[++i] == '\0' )             // if we reach the end of word,
                                end_of_word = 1;                // it is the end of word

                            if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
                                match = 0;                      // they don't match
                        } // while( match && !end_of_word && !end_of_table )

                        if( match )                             // if all characters of word are match
                        {
                            counter++;                          // count that word
                            printf("\n M[%d][%d] = %c \t found DOWN_RIGHT \n", row+1, column+1, M[row][column] );
                        }
                        break;

                    default :
                        break;

                    } // switch( direction )

                } // while( direction < 8 )

            } // if( M[row][column] == word[i] )

        } // for(column=0; column<columns; column++)

    } // for(row=0; row<rows; row++)

    return counter;
} // number_off_occurrences( char word[], char M[][MAX_SIZE], int rows, int columns )


// serves to test the program
void input_test_matrix( char M[][MAX_SIZE], int *rows, int *columns, char word[] )
{
    *rows = 4;
    *columns = 4;

    M[0][0] = 'O';
    M[0][1] = 'O';
    M[0][2] = 'O';
    M[0][3] = 'O';

    M[1][0] = 'O';
    M[1][1] = 'O';
    M[1][2] = 'O';
    M[1][3] = 'O';

    M[2][0] = 'O';
    M[2][1] = 'O';
    M[2][2] = 'W';
    M[2][3] = 'O';

    M[3][0] = 'O';
    M[3][1] = 'O';
    M[3][2] = 'O';
    M[3][3] = 'O';

//  M[0][0] = 'A';
//  M[0][1] = 'B';
//  M[0][2] = 'C';
//  M[0][3] = 'D';
//
//  M[1][0] = 'E';
//  M[1][1] = 'F';
//  M[1][2] = 'G';
//  M[1][3] = 'H';
//
//  M[2][0] = 'I';
//  M[2][1] = 'J';
//  M[2][2] = 'K';
//  M[2][3] = 'L';
//
//  M[3][0] = 'M';
//  M[3][1] = 'N';
//  M[3][2] = 'O';
//  M[3][3] = 'P';

    print_matrix("\n Matrix: \n\n", M, *rows, *columns );

    printf("\n Enter requested word: ");
    scanf("%s", word);
}


// input from user, numbers of rows, columns and matrix elements
void input_matrix( char M[][MAX_SIZE], int *rows, int *columns, char word[] )
{
    int r, c;

    printf("\n Enter number of rows of    matrix M [rows] [columns] ,  rows    = ");
    scanf("%d", rows);

    printf("\n Enter number of columns of matrix M [%d] [columns] , \t columns = ", *rows );
    scanf("%d", columns);

    for(r=0; r < (*rows); r++)
        for(c=0; c < (*columns); c++)
        {
            printf("\n Enter M[%d][%d] = ", r, c );
            scanf(" %c", &M[r][c] );
        }

    print_matrix("\n Matrix: \n\n", M, *rows, *columns );

    printf("\n Enter requested word: ");
    scanf("%s", word);
}


int main(void)
{
    int rows, columns, counter = 0;                 // sizes of matrix M[rows][columns]
    char word[MAX_SIZE];                            // requested word
    char M[MAX_SIZE][MAX_SIZE];                     // matrix M (a big one)


    input_test_matrix( M, &rows, &columns, word );  // serves to test the program

    counter = number_off_occurrences( word, M, rows, columns );

    printf("\n There are %d words \"%s\" in the matrix M[%d][%d] \n", counter, word, rows, columns );


    input_matrix( M, &rows, &columns, word );       // input from user

    counter = number_off_occurrences( word, M, rows, columns );

    printf("\n There are %d words \"%s\" in the matrix M[%d][%d] \n", counter, word, rows, columns );


    return 0;

} // main()