1
class Solution {
2
 public:
3
  bool solve(int i, int j, int &m, int &n, vector<vector<char>> &board, string &str, int s) {
4
    if (s >= str.length()) {
5
      return true;
6
    }
7
    if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] == '#') {
8
      return false;
9
    }
10
    char c = board[i][j];
11
    board[i][j] = '#';
12
    bool a = false;
13
    if (c == str[s])
14
      a = solve(i + 1, j, m, n, board, str, s + 1) || solve(i - 1, j, m, n, board, str, s + 1) ||
15
          solve(i, j - 1, m, n, board, str, s + 1) || solve(i, j + 1, m, n, board, str, s + 1);
16
    board[i][j] = c;
17
    return a;
18
  }
19
  bool exist(vector<vector<char>> &board, string word) {
20
    int i, j, m = board.size(), n = board[0].size();
21
    for (i = 0; i < m; i++) {
22
      for (j = 0; j < n; j++) {
23
        if (board[i][j] == word[0] && solve(i, j, m, n, board, word, 0)) {
24
          return true;
25
        }
26
      }
27
    }
28
    return false;
29
  }
30
};