<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 {
private:
    class stack_entry {
    public:
        pair<int, int>  loc;
        bool            status;
        bool            found_visited;

        stack_entry() = default;

        stack_entry(int i, int j) {
            loc = {i, j};
            status = false;
            found_visited = false;
        }
    };

    struct search_state {
        vector<vector<char>>            *board;
        string                          *word;
        vector<vector<bool>>            visited;
        vector<vector<vector<bool>>>    tbl;
        stack<stack_entry>              stk;
    };

    void testLoc(int y, int x, int idx, struct search_state *st) {
        if (st->tbl[y][x][idx])
            return;
        if (st->visited[y][x]) {
            st->stk.top().found_visited = true;
            return;
        }
        if (st->board->at(y)[x] == st->word->at(idx))
            st->stk.push(stack_entry(y, x));
    }

public:
    bool exist(vector<vector<char>>& board, string word) {
        int i, j;
        int idx;
        int len;
        int m, n;
        int x, y;
        struct search_state st;

        m = board.size();
        n = board[0].size();

        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                if (board[i][j] == word[0])
                    st.stk.push(stack_entry(i, j));
            }
        }

        len = word.length();

        st.board = &board;
        st.word = &word;

        st.visited = vector<vector<bool>>(m, vector<bool>(n));
        st.tbl = vector<vector<vector<bool>>>(m, vector<vector<bool>>(n, vector<bool>(len)));

        idx = 0;
        for (;;) {
            stack_entry *e;

            if (st.stk.empty())
                return false;
            e = &st.stk.top();

            i = e->loc.first;
            j = e->loc.second;

            if (e->status == true) {
                bool found_visited;

                found_visited = st.stk.top().found_visited;
                st.visited[i][j] = false;
                st.stk.pop();
                --idx;
                if (!st.stk.empty())
                    st.stk.top().found_visited = found_visited;
                if (idx > 0 && idx < len - 1 && !found_visited)
                    st.tbl[i][j][idx] = true;
                continue;
            }
            st.visited[i][j] = true;
            e->status = true;
            ++idx;

            if (idx == len)
                break;

            if (i > 0)
                testLoc(i - 1, j, idx, &st);
            if (i < m - 1)
                testLoc(i + 1, j, idx, &st);
            if (j > 0)
                testLoc(i, j - 1, idx, &st);
            if (j < n - 1)
                testLoc(i, j + 1, idx, &st);
        }

        return true;
    }
};
137031