（LeetCode C++）单词搜索

给定一个 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 仅由大小写英文字母组成

Method：

找到二维字符网格中与目标字符串首字符相同的位置开始遍历，不断的往上下左右尝试寻找下一个字符。

Code：

class Solution{
public:
    // 分别对应着:
    // 左移
    // 右移
    // 上移
    // 下移
    int move_x[4]={-1,1,0,0};
    int move_y[4]={0,0,-1,1};

    // 深度优先遍历搜索单词
    bool dfs(vector> &board,string word,int index,int i,int j){
        // 如果当前字符与目标字符串首字符不相同
        if(board[i][j]!=word[index]){
            // 则遍历失败
            return false;
        }
        // 如果当前遍历深度与目标字符串的长度相同
        if(index==word.size()-1){
            // 遍历成功
            return true;
        }

        // 暂存当前字符
        char temp=board[i][j];
        // 标记已经使用的字符
        board[i][j]='@';

        // 向上下左右四个方向遍历
        for(int k=0;k<4;k++){
            // 遍历后的位置索引
            int search_x=i+move_x[k];
            int search_y=j+move_y[k];

            // 如果索引越界或者当前字符已被使用
            if(search_x<0||search_x>=board.size()||search_y<0||search_y>=board[0].size()||board[search_x][search_y]=='@'){
                // 则换个方向索引
                continue;
            }

            // 深度优先遍历
            if(dfs(board,word,index+1,search_x,search_y)){
                return true;
            }
        }

        // 恢复当前字符
        board[i][j]=temp;
        
        // 如果此时未搜索到该单词,则认定该单词检索失败
        return false;

    }

    // 单词搜索
    bool exist(vector> &board,string word){
        // 遍历二维字符网格的行
        for(int i=0;i