<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:
    bool exist(vector<vector<char>>& board, string word) {

        if(!solvable(board, word)) {
            return false;
        }

        // cout << "Solvable\n";

        if(shouldReverse(word)) {
            reverse(word.begin(), word.end());
            // cout << "Reversed!\t" << word;
        }

        for(int y = 0; y < board.size(); y++) {
            for(int x = 0; x < board[0].size(); x++) {
                set<pair<int, int>> t;
                if (attempt(y, x, 0, t, word, board)) {
                    return true;
                }
            }
        }

        return false;
    }

    bool solvable(vector<vector<char>>& board, string& word) {
        // unordered_map<char, int> b;
        set<char> w;
        set<char> b;

        for(vector<char> x: board) {
            for(char y: x) {
                b.insert(y);
            }
        }

        for(char x: word) {
            w.insert(x);
        }


        return includes(b.begin(), b.end(), w.begin(), w.end());
    }

    bool attempt(int y, int x, int pos, set<pair<int, int>> visit, string& word, vector<vector<char>>& board) {
        // cout << pos << '\t';
        // if(pos >= word.size()) {
        //     // cout << "Found" << '\n';
        //     return true;
        // }

        if(y >= board.size() || y < 0 || x >= board[0].size() || x < 0) {
            // cout << '\n';
            return false;
        }   

        pair<int, int> currLoc = {y, x};

        if(find(visit.begin(), visit.end(), currLoc) != visit.end()) {
            // cout << '\n';
            return false;
        }

        if(word[pos] == board[y][x]) {
            if(pos == word.size() - 1) {
                return true;
            }
            visit.insert(currLoc);
            // set<pair<int, int>> cp = visit;
            // launch in all directions
            bool down = attempt(y + 1, x, pos + 1, visit, word, board);
            if(down) {
                return true;
            }
            // visit = cp;

            bool up = attempt(y - 1, x, pos + 1, visit, word, board);
            if(up) {
                return true;
            }
            // visit = cp;

            bool right = attempt(y, x + 1, pos + 1, visit, word, board);
            if(right) {
                return true;
            }
            // visit = cp;
            
            bool left = attempt(y, x - 1, pos + 1, visit, word, board);

            return left;
        }

        return false;
    }

    bool shouldReverse(string& word) {
        int sf = 0;
        int ef = 0;

        auto it = word.begin();
        while(it != word.end() && *it == word[0]) {
            sf++;
            it++;
        }

        auto rit = word.rbegin();

        while(rit != word.rend() && *rit == word[word.size() - 1]) {
            ef++;
            rit++;
        }

        // cout << "First char->" << *word.begin() << '/' << sf;
        // cout << '\n';
        // cout << "Second char->" << *word.rbegin() << '/' << ef;
        // cout << '\n';

        return ef < sf;
    }
};






























                // // Move right if correct
                // if(!v && r) {
                //     check(s, y, x + 1, pos + 1, false, true, false, word, board, out);
                // }
                // // Move up if correct
                // if(v && u) {
                //     check(s, y - 1, x, pos + 1, true, false, true, word, board, out);
                // }
                // // Move down if correct
                // if(v && !u) {
                //     check(s, y + 1, x, pos + 1, true, false, false, word, board, out);
                // }
                // // Move left if correct
                // if(!v && !r) {
                //     check(s, y, x - 1, pos + 1, false, false, false, word, board, out);
                // }


                // // Move right if correct
                // if(!v && r) {
                //     check(s, y, x + 1, pos + 1, false, true, false, word, board, out);
                // }
                // // Move up if correct
                // if(v && u) {
                //     check(s, y - 1, x, pos + 1, true, false, true, word, board, out);
                // }
                // // Move down if correct
                // if(v && !u) {
                //     check(s, y + 1, x, pos + 1, true, false, false, word, board, out);
                // }
                // // Move left if correct
                // if(!v && !r) {
                //     check(s, y, x - 1, pos + 1, false, false, false, word, board, out);
                // }

48918