#include <iostream>
using namespace std;
#define ROW 8
#define COL 10
// check whether given cell (row, col) is a valid
// cell or not.
bool isvalid(int row, int col, int prevRow, int prevCol)
{
// return true if row number and column number
// is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL) &&
!(row== prevRow && col == prevCol);
}
// These arrays are used to get row and column
// numbers of 8 neighboursof a given cell
int 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 vertices
void DFS(char mat[][COL], int row, int col,
int prevRow, int prevCol, string 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 += "(" + 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],
prevRow, prevCol))
DFS(mat, row + rowNum[k], col + colNum[k],
row, col, word, path, index+1, n);
}
// The main function to find all occurrences of the
// word in a matrix
void findWords(char mat[][COL], string 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, -1, -1, word, "", 0, n);
}
int main() {
char mat[8][10] = {{'B','O','O','K','E','T','T','L','E','G'},
{'O','O','Y','L','D','E','T','O','N','O'},
{'Y','G','Y','O','B','D','E','O','E','W'},
{'S','W','A','G','B','C','Q','S','M','O'},
{'Q','A','M','P','Z','X','W','E','O','R'},
{'E','Y','V','U','Z','V','Q','H','T','E'},
{'A','W','M','U','P','V','H','E','E','V'},
{'Q','W','B','K','L','N','M','N','C','E'}};
string word = "HEN";
findWords(mat, word,word.length()-1);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIFJPVyA4CiNkZWZpbmUgQ09MIDEwCiAKLy8gY2hlY2sgd2hldGhlciBnaXZlbiBjZWxsIChyb3csIGNvbCkgaXMgYSB2YWxpZAovLyBjZWxsIG9yIG5vdC4KYm9vbCBpc3ZhbGlkKGludCByb3csIGludCBjb2wsIGludCBwcmV2Um93LCBpbnQgcHJldkNvbCkKewogICAgLy8gcmV0dXJuIHRydWUgaWYgcm93IG51bWJlciBhbmQgY29sdW1uIG51bWJlcgogICAgLy8gaXMgaW4gcmFuZ2UKICAgIHJldHVybiAocm93ID49IDApICYmIChyb3cgPCBST1cpICYmCiAgICAgICAgICAgKGNvbCA+PSAwKSAmJiAoY29sIDwgQ09MKSAmJgogICAgICAgICAgICEocm93PT0gcHJldlJvdyAmJiBjb2wgPT0gcHJldkNvbCk7Cn0KIAovLyBUaGVzZSBhcnJheXMgYXJlIHVzZWQgdG8gZ2V0IHJvdyBhbmQgY29sdW1uCi8vIG51bWJlcnMgb2YgOCBuZWlnaGJvdXJzb2YgYSBnaXZlbiBjZWxsCmludCByb3dOdW1bXSA9IHstMSwgLTEsIC0xLCAwLCAwLCAxLCAxLCAxfTsKaW50IGNvbE51bVtdID0gey0xLCAwLCAxLCAtMSwgMSwgLTEsIDAsIDF9OwogCi8vIEEgdXRpbGl0eSBmdW5jdGlvbiB0byBkbyBERlMgZm9yIGEgMkQgYm9vbGVhbgovLyBtYXRyaXguIEl0IG9ubHkgY29uc2lkZXJzIHRoZSA4IG5laWdoYm91cnMgYXMKLy8gYWRqYWNlbnQgdmVydGljZXMKdm9pZCBERlMoY2hhciBtYXRbXVtDT0xdLCBpbnQgcm93LCBpbnQgY29sLAogICAgICAgICBpbnQgcHJldlJvdywgaW50IHByZXZDb2wsIHN0cmluZyB3b3JkLAogICAgICAgICBzdHJpbmcgcGF0aCwgaW50IGluZGV4LCBpbnQgbikKewogICAgLy8gcmV0dXJuIGlmIGN1cnJlbnQgY2hhcmFjdGVyIGRvZXNuJ3QgbWF0Y2ggd2l0aAogICAgLy8gdGhlIG5leHQgY2hhcmFjdGVyIGluIHRoZSB3b3JkCiAgICBpZiAoaW5kZXggPiBuIHx8IG1hdFtyb3ddW2NvbF0gIT0gd29yZFtpbmRleF0pCiAgICAgICAgcmV0dXJuOwogCiAgICAvL2FwcGVuZCBjdXJyZW50IGNoYXJhY3RlciBwb3NpdGlvbiB0byBwYXRoCiAgICBwYXRoICs9ICAiKCIgKyB0b19zdHJpbmcocm93KQogICAgICAgICAgICArICIsICIgKyB0b19zdHJpbmcoY29sKSArICIpICI7CiAKICAgIC8vIGN1cnJlbnQgY2hhcmFjdGVyIG1hdGNoZXMgd2l0aCB0aGUgbGFzdCBjaGFyYWN0ZXIKICAgIC8vIGluIHRoZSB3b3JkCiAgICBpZiAoaW5kZXggPT0gbikKICAgIHsKICAgICAgICBjb3V0IDw8IHBhdGggPDwgZW5kbDsKICAgICAgICByZXR1cm47CiAgICB9CiAKICAgIC8vIFJlY3VyIGZvciBhbGwgY29ubmVjdGVkIG5laWdoYm91cnMKICAgIGZvciAoaW50IGsgPSAwOyBrIDwgODsgKytrKQogICAgICAgIGlmIChpc3ZhbGlkKHJvdyArIHJvd051bVtrXSwgY29sICsgY29sTnVtW2tdLAogICAgICAgICAgICAgICAgICAgIHByZXZSb3csIHByZXZDb2wpKQogCiAgICAgICAgICAgIERGUyhtYXQsIHJvdyArIHJvd051bVtrXSwgY29sICsgY29sTnVtW2tdLAogICAgICAgICAgICAgICAgcm93LCBjb2wsIHdvcmQsIHBhdGgsIGluZGV4KzEsIG4pOwp9CiAKLy8gVGhlIG1haW4gZnVuY3Rpb24gdG8gZmluZCBhbGwgb2NjdXJyZW5jZXMgb2YgdGhlCi8vIHdvcmQgaW4gYSBtYXRyaXgKdm9pZCBmaW5kV29yZHMoY2hhciBtYXRbXVtDT0xdLCBzdHJpbmcgd29yZCwgaW50IG4pCnsKICAgIC8vIHRyYXZlcnNlIHRocm91Z2ggdGhlIGFsbCBjZWxscyBvZiBnaXZlbiBtYXRyaXgKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgUk9XOyArK2kpCiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBDT0w7ICsraikKIAogICAgICAgICAgICAvLyBvY2N1cnJlbmNlIG9mIGZpcnN0IGNoYXJhY3RlciBpbiBtYXRyaXgKICAgICAgICAgICAgaWYgKG1hdFtpXVtqXSA9PSB3b3JkWzBdKQogCiAgICAgICAgICAgICAgICAvLyBjaGVjayBhbmQgcHJpbnQgaWYgcGF0aCBleGlzdHMKICAgICAgICAgICAgICAgIERGUyhtYXQsIGksIGosIC0xLCAtMSwgd29yZCwgIiIsIDAsIG4pOwp9CmludCBtYWluKCkgewpjaGFyIG1hdFs4XVsxMF0gPSB7eydCJywnTycsJ08nLCdLJywnRScsJ1QnLCdUJywnTCcsJ0UnLCdHJ30sCgogICAgICAgICAgICAgICAgICAgIHsnTycsJ08nLCdZJywnTCcsJ0QnLCdFJywnVCcsJ08nLCdOJywnTyd9LAoKICAgICAgICAgICAgICAgICAgICB7J1knLCdHJywnWScsJ08nLCdCJywnRCcsJ0UnLCdPJywnRScsJ1cnfSwKCiAgICAgICAgICAgICAgICAgICAgeydTJywnVycsJ0EnLCdHJywnQicsJ0MnLCdRJywnUycsJ00nLCdPJ30sCgogICAgICAgICAgICAgICAgICAgIHsnUScsJ0EnLCdNJywnUCcsJ1onLCdYJywnVycsJ0UnLCdPJywnUid9LAoKICAgICAgICAgICAgICAgICAgICB7J0UnLCdZJywnVicsJ1UnLCdaJywnVicsJ1EnLCdIJywnVCcsJ0UnfSwKCiAgICAgICAgICAgICAgICAgICAgeydBJywnVycsJ00nLCdVJywnUCcsJ1YnLCdIJywnRScsJ0UnLCdWJ30sCgogICAgICAgICAgICAgICAgICAgIHsnUScsJ1cnLCdCJywnSycsJ0wnLCdOJywnTScsJ04nLCdDJywnRSd9fTsKICAgICAgICAgICAgICAgICAgICBzdHJpbmcgd29yZCA9ICJIRU4iOwogICAgICAgICAgICAgICAgICAgIGZpbmRXb3JkcyhtYXQsIHdvcmQsd29yZC5sZW5ndGgoKS0xKTsKICAgIHJldHVybiAwOwp9