<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>


struct Point{
    int x;
    int y;
    Point(int x, int y) : x{x}, y{y} {}
    
};

bool operator==(const Point& lhs, const Point& rhs) {
    return (lhs.x == rhs.x) && (lhs.y == rhs.y);
}
class Solution {
public:
    

    bool chain(vector<vector<char>>& board, vector<Point> points, string word) {
        Point p = points.back();
        int x = p.x;
        int y = p.y;
        const vector<Point> directions = vector<Point>{
            Point {1, 0}, Point{-1, 0},
            Point{0, 1}, Point{0, -1}
        };
        for (Point dir : directions) {
            int i = dir.x;
            int j = dir.y; 
            if (x + i >= 0 && y + j >= 0 
                    && x + i < board.size() && y + j < board[x + i].size()) {
                Point new_point = Point {x + i, y + j};
                if (word[0] == board[x + i][y + j]
                    && find(points.begin(), points.end(), new_point) == points.end()) {
                    if (word.length() == 1) {
                        return true;
                    } else {
                        points.push_back(new_point);
                        bool found = chain(board, points, word.substr(1));
                        if (found) return true;
                        points.pop_back();
                    }
                }
            }
        }
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        for (const auto& c : word) {
            bool skip = false;
            for (const auto& row : board) {
                for (const auto& board_c : row) {
                    if (c == board_c) {
                        skip = true;
                        break;
                    }
                }
                if (skip) break;
            }
            if (skip) continue;
            return false;
        } 
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (board[i][j] == word[0]){
                    if (word.length() == 1) {
                        return true;
                    } else {
                        vector<Point> points {Point {i, j}};
                        bool found = chain(board, points, word.substr(1));
                        if (found) return true;
                    }
                }
            }
        }
        return false;
    }
};

303981