#include<iostream>
using namespace std;
void getStartAndEndOfAWord(char sentence[], char words[400][200], int &num_of_words)
{
        int position_sentence = 0, position_word_column = 0;
        num_of_words = 0;
        while (sentence[position_sentence] != 0)
        {
                if ((sentence[position_sentence] >= 'a' && sentence[position_sentence] <= 'z')
                        || sentence[position_sentence] >= 'A' && sentence[position_sentence] <= 'Z')
                {
                        words[num_of_words][position_word_column] = sentence[position_sentence];
                        position_word_column++;
                }
                if (sentence[position_sentence + 1] == 0 || sentence[position_sentence] == ' ')
                {
                        words[num_of_words][position_word_column] = 0;
                        num_of_words++;
                        position_word_column = 0;
                }
                position_sentence++;
        }
}
bool compareStrings(char* word_sentence, char* word_grid)
{
        int position = 0;
        while (word_sentence[position] != 0 && word_grid[position] != 0)
        {
                if (word_sentence[position] != word_grid[position])
                {
                        return 0;
                }
                position++;
        }
        return word_sentence[position] == word_grid[position];
}
int searchForRoutes(char words[][200], char grid[][30][101], int num_of_words, int start_counting,
        int current_position_row, int current_position_column, int gridRows, int gridColumns)
{
        int num_steps = 0;
        if (start_counting == num_of_words)
        {
                return 1;
        }
        for (int position_row = -1; position_row < 2; position_row++)
        {
                for (int position_column = -1; position_column < 2; position_column++)
                {
                        if (current_position_row + position_row >= 0
                                && current_position_row + position_row < gridRows
                                &&  current_position_column + position_column >= 0
                                && current_position_column < gridColumns
                                && compareStrings(words[start_counting], grid[current_position_row + position_row]
                                        [current_position_column + position_column]))
                        {
                                num_steps += searchForRoutes(words, grid, num_of_words, start_counting + 1,
                                        current_position_row + position_row, current_position_column + position_column,
                                        gridRows, gridColumns);
                        }
                }
        }
        return num_steps;
}
int countReads(char grid[30][30][101], int gridRows, int gridColumns, char sentence[90901])
{
        char words[400][200];
        int num_of_words, start_counting = 1, num_of_paths = 0;
        getStartAndEndOfAWord(sentence, words, num_of_words);
        for (int current_position_row = 0; current_position_row < gridRows; current_position_row++)
        {
                for (int current_position_column = 0; current_position_column < gridColumns; current_position_column++)
                {
                        if (compareStrings(words[0], grid[current_position_row][current_position_column]))
                        {
                                num_of_paths += searchForRoutes(words, grid, num_of_words, start_counting,
                                        current_position_row, current_position_column, gridRows, gridColumns);
                        }
                }
        }
        return num_of_paths;
}