Search a Word in a 2D Grid of characters - GeeksforGeeks
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.
http://www.geeksforgeeks.org/find-all-occurrences-of-the-word-in-a-matrix/
Read full article from Search a Word in a 2D Grid of characters - GeeksforGeeks
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.
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.
// Rows and columns in given grid#define R 3#define C 14// For searching in all 8 directionint 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[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[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 directionsvoid 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;}http://www.geeksforgeeks.org/find-all-occurrences-of-the-word-in-a-matrix/
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 Diagonals.
Input:
mat[ROW][COL]= { {'B', 'N', 'E', 'Y', 'S'},
{'H', 'E', 'D', 'E', 'S'},
{'S', 'G', 'N', 'D', 'E'}
};
Word = “DES”
Output:
D(1, 2) E(1, 1) S(2, 0)
D(1, 2) E(1, 3) S(0, 4)
D(1, 2) E(1, 3) S(1, 4)
D(2, 3) E(1, 3) S(0, 4)
D(2, 3) E(1, 3) S(1, 4)
D(2, 3) E(2, 4) S(1, 4)
The problem can be easily solved by applying DFS() on each occurrence of first character of the word in the matrix. A cell in 2D matrix can be connected to 8 neighbours. So, unlike standard DFS(), where we recursively call for all adjacent vertices, here we can recursive call for 8 neighbours only.
bool isvalid(int row, int col){ // return true if row number and column number // is in range return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL);}// These arrays are used to get row and column// numbers of 8 neighboursof a given cellint rowNum[] = {-1, -1, -1, 0, 0, 1, 1, 1};int colNum[] = {-1, 0, 1, -1, 1, -1, 0, 1};// A utility function to do DFS for a 2D boolean// matrix. It only considers the 8 neighbours as// adjacent verticesvoid DFS(char mat[][COL], int row, int col, char* word, string path, int index, int n){ // return if current character doesn't match with // the next character in the word if (index > n || mat[row][col] != word[index]) return; //append current character position to path path += string(1, word[index]) + "(" + to_string(row) + ", " + to_string(col) + ") "; // current character matches with the last character // in the word if (index == n) { cout << path << endl; return; } // Recur for all connected neighbours for (int k = 0; k < 8; ++k) if (isvalid(row + rowNum[k], col + colNum[k])) DFS(mat, row + rowNum[k], col + colNum[k], word, path, index+1, n);}// The main function to find all occurrences of the// word in a matrixvoid findWords(char mat[][COL], char* word, int n){ // traverse through the all cells of given matrix for (int i = 0; i < ROW; ++i) for (int j = 0; j < COL; ++j) // occurrence of first character in matrix if (mat[i][j] == word[0]) // check and print if path exists DFS(mat, i, j, word, "", 0, n);}