Question

Question Prompt (1 of 1)

You are running a classroom and suspect that some of your students are cheating by sharing answers as single words hidden in 2D grids of letters.

A particular grid contains at most one word. The word may start anywhere in the grid, and consecutive letters can be either below or to the right of the previous letter.

The input will consist of a word and a grid. Print the location of the word in the grid as a list of “row column” coordinates, each on its own line. If the word does not appear in the grid, just print “None”.

Example input:

  catnip

  c r c a r s
  a b i t n b
  t f n n t i
  x s i i p t

Example output

  0 2
  0 3
  1 3
  2 3
  3 3
  3 4

Clarifications:

• The word will always appear in the grid exactly 0 or 1 times.

Starter code is provided for the following languages: Java, C, C++, JavaScript,

If you wish to use a different language, please write a solution
that reads from STDIN and writes to STDOUT. To obtain starter code,
change the language to one of the previously mentioned languages.

Public test 1

Input:

car

c r c r a c a b i t n b t f n n t i

Expected Output:

None

Public test 2

Input:

car

c r c c a r a b i t n b t f n n t i

Expected Output:

0 3 0 4 0 5

Public test 3

Input:

carsick c r c a r s a b i t n b t f n n t i x s c a t n x s d d e a s q w x s p

Expected Output:

None

Public test 4

Input:

catnap c r c a r s a b i t n b t f n n t i x s c a t n x s d d e a s q w x s p

Expected Output:

3 2 3 3 3 4 3 5 4 5 5 5

Public test 5

Input:

catnip c r c a r s a b i t n b t f n n t i x s i i p t

Expected Output:

0 2 0 3 1 3 2 3 3 3 3 4

Answer 1

#include <bits/stdc++.h> 
using namespace std; 

#define R 4
#define C 7
// For searching in 2 direction 
int x[] = { 0,1 }; 
int y[] = {1,0}; 

// This function searches in 
// all 2-direction from point 
// (row, col) in grid[][] 
bool search2D(char grid[R][C], int row, 
                        int col, string word) 
{ 
        // If first character of word doesn't 
        // match with given starting point in grid. 
        if (grid[row][col] != word[0]) 
                return false; 

        int len = word.length(); 

        // Search word in all 2 directions 
        // starting from (row, col) 
        for (int dir = 0; dir < 2; dir++) { 
                // Initialize starting point 
                // for current direction 
                int k, rd = row + x[dir], cd = col + y[dir]; 

                // First character is already checked, 
                // match remaining characters 
                for (k = 1; k < len; k++) { 
                        // If out of bound break 
                        if (rd >= R || rd < 0 || cd >= C || cd < 0) 
                                break; 

                        // If not matched, break 
                        if (grid[rd][cd] != word[k]) 
                                break; 

                        // Moving in particular direction 
                        rd += x[dir], cd += y[dir]; 
                } 

                // If all character matched, then value of must 
                // be equal to length of word 
                if (k == len) 
                        return true; 
        } 
        return false; 
} 

void patternSearch(char grid[R][C], 
                                string word) 
{ 
        // Consider every point as starting 
        // point and search given word 
        for (int row = 0; row < R; row++) 
                for (int col = 0; col < C; col++) 
                        if (search2D(grid, row, col, word)) 
                                cout << "pattern found at "
                                        << row << ", "
                                        << col << endl; 
} 

// Driver program 
int main() 
{ 
        char grid[R][C] = { "crcars","abitnb","tfnnti","xsiipt"}; 

        patternSearch(grid, "catnip"); 
        cout << endl; 
        return 0; 
} 

Please ask if there is any doubt, please upvote