Urgent

[gabrinka]

Hello,can anyone please help me with the following task and probably write a possible solution.Here is the task.
We have a rectangular matrix GRID consisting of words with no more than 100 characters composed of small Latin letters (no other symbols), and a sentence composed of words separated by a space. A sequence of cells in the matrix in which each next cell is directly from the top, left, right, or bottom of the previous one, we call the "path." It is allowed for a cell to participate more than once in the path.

We say that a sentence can be read in the matrix of words if we can find a path in the matrix consisting of the consecutive words of the sentence.

Write the function int countReads (char grid [30] [30] [101], int gridRows, int gridColumns, char sentence [90900]), which returns the number of different ways in which sentence sentences can be read in the grid .

Assume that the sentence consists of no more than 900 words, each with no more than 100 characters.You cn use a funtion that separetes the sentece into a char array of words and another one which finds all the possible paths from a certain cell using recursion.

I don't even know where to start and it is due tomorrow.

[jonnin]

start by setting up your storage as specified.
get the words into the grid.

then you can work on trying to figure out how to path it out.


do you know the maze solver recursive approach? try to walk left, if you can't try to walk right, if can't try to walk up, if can't try to walk down... and if you walk, it starts a new recursive copy at the new location, so say you were able to go right, then you move there and try to go left, then right, then up, then down again... and again.. if you get stuck, it pops back and tries the next direction from the previous location... does that make sense? You can do a brute force solution this way, by finding the first word, then treat it like that maze (remember to check for doubled up same word as where you currently ar though)

honestly I would find a way to get lists... get a list of all the coordinates of all the words in the input, and cross reference those using some sort of 'is this coordinate and that coordinate adjacent' function. If you can think of a way to iterate this idea recursively, it will be much faster.

this seems like a lot to give someone only one day to do.

[dutch]

By your 11th post you should be able to give your thread a decent name. "Urgent" is useless.

[dhayden]

I assume that gridRows and gridColumns are the number of rows and columns in grid, which means they are both 30 or less.

A recursive function to count the paths from a particular starting point might look like this:

// return the number of times the sentence starts from startRow/startColumn
int countReadsRecursive(char grid [30] [30] [101],
                         int gridRows, int gridColumns,
                         int startRow, int startColumn,
                         char *sentence)
{
    //  The following bounds checks are needed for the recursive calls
    // if startRow<0 || startRow > gridRows) return 0;  // startRow out of bounds
    // if startColumn<= 0 || startColumn > gridColumns) return 0;  // startColumn out of 
bounds
    // See if grid[startRow][startColumn] contains the first word of the sentence
    // if it doesn't then return 0.
    // If it does then
    // set char *newSentence to point to the next word in the sentence.
    // return countReadsRecursive(grid, gridRows, gridColumns, startRow-1, startColumn, newSentence) +
       countReadsRecursive(grid, gridRows, gridColumns, startRow, startColumn-1, newSentence) +
       countReadsRecursive(grid, gridRows, gridColumns, startRow, startColumn+1, newSentence) +
       countReadsRecursive(grid, gridRows, gridColumns, startRow+1, startColumn, newSentence);
}

Then you can could all the ways to read the sentence by checking the start of the sentence at each location:

int countReads (char grid [30] [30] [101], int gridRows, int gridColumns, char sentence [90900])
{
    int result = 0;  // result of the function
    for (int r=0; r<gridRows; ++r) {
        for (int c=0; c<gridColumns; ++c) {
            result += countReadsRecursive(grid, gridRows, gridColumns, r, c, sentence)
        }
    }
    return result;
}

I don't even know where to start and it is due tomorrow.

Program requires LOTS of time. Don't let yourself get into this position again.

[gabrinka]

Well I missed the deadline but then I sat down and wrote the code. I am just glad I know how to do it, been having problems with recursion for a while. Thank you though! Appreciate the help.