# Search a word in a given 2 dimensional matrix of letters

Backtracking : Program to search a word in a given 2 dimensional matrix of letters

``````#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>

using namespace std;

class WordSearch {

public:
string sofar;
vector<string> board;
string word;

// The size of the board would always be less than or equal to 8
bool visited[8][8] = {{ false }};

bool Search (int x, int y, int pos) {

if (pos == word.size()) {
return true;
} else {
// Co-ordinates difference of the adjacent cells in order Up, Right, Down and Left
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int rows = board.size();
int cols = board[0].size();

// Visit adjacent cells in order Up, Right, Down & Left
for (int i=0; i<4; i++) {

int newx = x + dx[i];
int newy = y + dy[i];

if (newx < 0 or newx >= rows or
newy < 0 or newy >= cols or visited[newx][newy] == true)
continue;

if (board[newx][newy] == word[pos]) {
pos++;
visited[newx][newy] = true;
if (Search (newx, newy, pos) == true) // Word has been found so return true.
return true;
visited[newx][newy] = false; // Backtrack and try other adjacent letter first.
pos--;
}
}
}
return false;
}

// Below function returns true if the word [word] exist on the board
bool Exist (vector<string> arg_board, string arg_word) {

int pos; // Tracks the position of the matching letters of the word
board = arg_board;
word = arg_word;

int rows = board.size();
int cols = board[0].size();

memset(visited, false, sizeof(bool) * 8 * 8);

for (int r=0; r<rows; r++) {
for (int c=0; c<cols; c++) {
pos = 0;
if (board[r][c] == word[pos]) {
pos++;
visited[r][c] = true;
if (Search(r, c, pos))
return true;
visited[r][c] = false;
}
}
}
return false;
}
};

int main() {

WordSearch W;
//====================================
vector<string> vec_1 = {{"ABCE"},
{"SFCS"},

if (W.Exist(vec_1, "ABCCED") == 1)
cout << "Yes" << endl;
else
cout << "No" << endl;

//====================================
vector<string> vec_2 = {{"AAAAA"},
{"AAAAA"},
{"AAAAA"},
{"AAAAA"}};

if (W.Exist(vec_2, "AAB") == 1)
cout << "Yes" << endl;
else
cout << "No" << endl;

//====================================
vector<string> vec_3 = {{"FGABG"},
{"EFAEC"},
{"GGFBD"},
{"GGDCD"}};

if (W.Exist(vec_3, "FEGGGDCDDCGBAG") == 1)
cout << "Yes" << endl;
else
cout << "No" << endl;

//====================================
vector<string> vec_4 = {{"FCDFFD"},
{"BGCBFC"}};

if (W.Exist(vec_4, "FBGCDCBFFF") == 1)
cout << "Yes" << endl;
else
cout << "No" << endl;

return 0;
}
``````

Output

``````Yes
No
Yes
Yes
``````