<p>Given an <code>m x n</code> grid of characters <code>board</code> and a string <code>word</code>, return <code>true</code> <em>if</em> <code>word</code> <em>exists in the grid</em>.</p>

<p>The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word2.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;ABCCED&quot;
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;SEE&quot;
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/15/word3.jpg" style="width: 322px; height: 242px;" />
<pre>
<strong>Input:</strong> board = [[&quot;A&quot;,&quot;B&quot;,&quot;C&quot;,&quot;E&quot;],[&quot;S&quot;,&quot;F&quot;,&quot;C&quot;,&quot;S&quot;],[&quot;A&quot;,&quot;D&quot;,&quot;E&quot;,&quot;E&quot;]], word = &quot;ABCB&quot;
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n = board[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 6</code></li>
	<li><code>1 &lt;= word.length &lt;= 15</code></li>
	<li><code>board</code> and <code>word</code> consists of only lowercase and uppercase English letters.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Could you use search pruning to make your solution faster with a larger <code>board</code>?</p>

class Solution {
public:
    void printB(vector<vector<char>>& curr) {
        for (vector<char> v : curr) {
            for (char c : v) {
                cout << c;
            }
            cout << endl;
        }
    }
    bool solve(vector<vector<char>>& curr, int row, int col, int m, int n, int idx, string word) {
        //printB(curr);
        if (idx >= word.length()) {
            return true;
        }
        bool win = false;
        if (row + 1 < m && curr[row + 1][col] == word[idx]) {
            vector<vector<char>> copy = vector<vector<char>>(curr);
            copy[row + 1][col] = '-';
            win = solve(copy, row + 1, col, m, n, idx + 1, word);
        }
        if (!win && col + 1 < n && curr[row][col + 1] == word[idx]) {
            vector<vector<char>> copy = vector<vector<char>>(curr);
            copy[row][col + 1] = '-';
            win = solve(copy, row, col + 1, m, n, idx + 1, word);
        }
        if (!win && row - 1 >= 0 && curr[row - 1][col] == word[idx]) {
            vector<vector<char>> copy = vector<vector<char>>(curr);
            copy[row - 1][col] = '-';
            win = solve(copy, row - 1, col, m, n, idx + 1, word);
        }
        if (!win && col - 1 >= 0 && curr[row][col - 1] == word[idx]) {
            vector<vector<char>> copy = vector<vector<char>>(curr);
            copy[row][col - 1] = '-';
            win = solve(copy, row, col - 1, m, n, idx + 1, word);
        }
        return win;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        reverse(word.begin(), word.end());
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (board[row][col] == word[0]) {
                    vector<vector<char>> copy = vector<vector<char>>(board);
                    copy[row][col] = '-';
                    if (solve(copy, row, col, m, n, 1, word)) {
                        return true;
                    }
                    else if (word[0] != word[word.length() - 1]) {
                        reverse(word.begin(), word.end());
                    }
                }
            }
        }
        return false;
    }
};
127756