class Solution {
public:
bool chk(vector<vector>& board, int j, int k, int i, string word,
vector<vector>& mpp, string& temp) {
if (i == word.size()) {
if (temp == word)
return true;
else return false;
}
for (int row = j; row < board.size(); row++) {
for (int col = k; col < board[0].size(); col++) {
if (!mpp[row][col] && board[row][col] == word[i]) {
temp += board[row][col];
cout<<temp<<"-> "<<i<<" ";
mpp[row][col] = 1;
if (i<word.size()-1&&row < board.size() - 1 &&
board[row + 1][col] == word[i + 1])
chk(board, row + 1, col, i + 1, word, mpp, temp);
else if (i<word.size()-1&&row > 0 && board[row - 1][col] == word[i + 1])
chk(board, row - 1, col, i + 1, word, mpp, temp);
else if (i<word.size()-1&&col > 0 && board[row][col - 1] == word[i + 1])
chk(board, row, col - 1, i + 1, word, mpp, temp);
else if (i<word.size()-1&&col < board[0].size() - 1 && board[row][col + 1] == word[i + 1])
chk(board, row, col + 1, i + 1, word, mpp, temp);
else {
mpp[row][col] = 0;
temp.pop_back();
}
}
}
}
return false;
}
bool exist(vector<vector<char>>& board, string word) {
int i = 0;
string temp;
vector<vector<int>> mpp(board.size(), vector<int>(board[0].size(), 0));
bool flag = chk(board, 0, 0, i, word, mpp, temp);
// cout << temp;
return flag;
}
};