# Search a Word in a 2D Grid of characters

Given a 2D grid of characters and a word, find all occurrences of given word in grid. A word can be matched in all 8 directions at any point. Word is said be found in a direction if all characters match in this direction (not in zig-zag form).

The 8 directions are, Horizontally Left, Horizontally Right, Vertically Up and 4 Diagonal directions.

Example:

```Input:  grid[][] = {"GEEKSFORGEEKS",
"GEEKSQUIZGEEK",
"IDEQAPRACTICE"};
word = "GEEKS"

Output: pattern found at 0, 0
pattern found at 0, 8
pattern found at 1, 0

Input:  grid[][] = {"GEEKSFORGEEKS",
"GEEKSQUIZGEEK",
"IDEQAPRACTICE"};
word = "EEE"

Output: pattern found at 0, 2
pattern found at 0, 10
pattern found at 2, 2
pattern found at 2, 12
```

Below diagram shows a bigger grid and presence of different words in it. Source: Microsoft Interview Question

The idea used here is simple, we check every cell. If cell has first character, then we one by one try all 8 directions from that cell for a match. Implementation is interesting though. We use two arrays x[] and y[] to find next move in all 8 directions.

Below are implementation of the same.

div class="responsive-tabs">

## C++

 `// C++ programs to search a word in a 2D grid ` `#include ` `using` `namespace` `std; ` ` `  `// Rows and columns in given grid ` `#define R 3 ` `#define C 14 ` ` `  `// For searching in all 8 direction ` `int` `x[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; ` `int` `y[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; ` ` `  `// This function searches in all 8-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) ` `      ``return` `false``; ` ` `  `    ``int` `len = word.length(); ` ` `  `    ``// Search word in all 8 directions starting from (row,col) ` `    ``for` `(``int` `dir = 0; dir < 8; 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``; ` `} ` ` `  `//  Searches given word in a given matrix in all 8 directions ` `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] = {``"GEEKSFORGEEKS"``, ` `                       ``"GEEKSQUIZGEEK"``, ` `                       ``"IDEQAPRACTICE"` `                      ``}; ` ` `  `    ``patternSearch(grid, ``"GEEKS"``); ` `    ``cout << endl;  ` `    ``patternSearch(grid, ``"EEE"``); ` `    ``return` `0; ` `} `

## Java

 `// Java program to search a word in a 2D grid ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `GFG  ` `{ ` ` `  `    ``// Rows and columns in given grid ` `    ``static` `int` `R, C; ` ` `  `    ``// For searching in all 8 direction  ` `    ``static` `int``[] x = { -``1``, -``1``, -``1``, ``0``, ``0``, ``1``, ``1``, ``1` `};  ` `    ``static` `int``[] y = { -``1``, ``0``, ``1``, -``1``, ``1``, -``1``, ``0``, ``1` `};  ` ` `  `    ``// This function searches in all 8-direction from point  ` `    ``// (row, col) in grid[][]  ` `    ``static` `boolean` `search2D(``char``[][] grid, ``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.charAt(``0``)) ` `                ``return` `false``; ` ` `  `            ``int` `len = word.length(); ` `             `  `            ``// Search word in all 8 directions ` `            ``// starting from (row,col) ` `            ``for` `(``int` `dir = ``0``; dir < ``8``; 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.charAt(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``; ` `    ``} ` ` `  `    ``// Searches given word in a given ` `    ``// matrix in all 8 directions ` `    ``static` `void` `patternSearch(``char``[][] grid, 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)) ` `                        ``System.out.println(``"pattern found at "` `+ row +  ` `                                                            ``", "` `+ col); ` `                ``} ` `            ``} ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `            ``R = ``3``; ` `            ``C = ``13``; ` `            ``char``[][] grid = {{``'G'``,``'E'``,``'E'``,``'K'``,``'S'``,``'F'``,``'O'``,``'R'``,``'G'``,``'E'``,``'E'``,``'K'``,``'S'``}, ` `                                ``{``'G'``,``'E'``,``'E'``,``'K'``,``'S'``,``'Q'``,``'U'``,``'I'``,``'Z'``,``'G'``,``'E'``,``'E'``,``'K'``}, ` `                                ``{``'I'``,``'D'``,``'E'``,``'Q'``,``'A'``,``'P'``,``'R'``,``'A'``,``'C'``,``'T'``,``'I'``,``'C'``,``'E'``}}; ` `            ``patternSearch(grid, ``"GEEKS"``); ` `            ``System.out.println(); ` `            ``patternSearch(grid, ``"EEE"``); ` `    ``} ` `}  ` ` `  `// This code is contributed by rachana soma `

Output:

```pattern found at 0, 0
pattern found at 0, 8
pattern found at 1, 0

pattern found at 0, 2
pattern found at 0, 10
pattern found at 2, 2
pattern found at 2, 12```

Exercise: The above solution only print locations of word. Extend it to print the direction where word is present.

See this for solution of exercise.