单词搜索（回溯+剪枝）

***题目描述：***给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

示例 2：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
输出：true

示例 3：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB”
输出：false

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

方法：回溯+剪枝

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int n=board.size(),m=board[0].size();
        vector<vector<bool>> v(n,vector<bool>(m,0));
        pair<int,int> dir[4]={{0,1},{1,0},{-1,0},{0,-1}};
        bool t=0;
        auto dfs=[&](auto&& w,int&& k,int x,int y){
            if(k==word.size())
            {
            	t=1;
            	return;
            }
            if(x>=0&&x<n&&y>=0&&y<m&&!v[x][y]&&board[x][y]==word[k]){
                v[x][y]=1;
                for(int i=0;i!=4;++i){                   
                    w(w,k+1,x+dir[i].first,y+dir[i].second);
                    if(t)return ;
                }
                v[x][y]=0;
            }
        };
        int h = 0;
        for (const vector<char>& row : board)
            for (const char& c : row) {
            if (c == word[0])
            h += 1;
            else if (c == word.back())
            h -= 1;
        }
        //剪枝，用少的那个。估计是可以剪掉那个刚好很多重复头元素的
        if (h > 0) reverse(word.begin(), word.end());
        for(int i=0;i!=n;++i){
            for(int j=0;j!=m;++j){
                if(board[i][j]==word[0]){
                    dfs(dfs,0,i,j);
                    if(t)return t;
                }
            }
        }
        return 0;
    }
};