算法：矩阵中的路径

题目：

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

 

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

 

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

示例：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

输出：true

思路：

回溯思想

申明以下递归函数，含义：m*n的board，从位置[i][j]开始，能否找到单词word，变量visted标记找到的字母。

bool check(vector<vector<char>>& board, int m, int n, int i, int j, vector<vector<bool>>& visited, string word)

主函数中，尝试每次从举证不同的位置作为起始位置，调用上面申明的check函数，判断从该位置出发，能否找到单词。

代码：

class Solution {
public:
    vector<int> dir = {-1,0, 1};

    bool valid(int m, int n, int i, int j)
    {
        if(i>=0 && i<m && j>=0 && j<n)
            return true;
        else
            return false;
    }

    bool check(vector<vector<char>>& board, int m, int n, int i, int j,  vector<vector<bool>>& visited, string word)
    { 
        if(board[i][j] != word[0])
            return false;
        
        visited[i][j]=true;
        string s=word.substr(1, word.size()-1);

        if(s.size() == 0 )
            return true;

        for(auto& p: dir)
        {
            for(auto& q: dir)
            {
                if(abs(p)==1 && abs(q)==1)
                    continue;
                
                if(valid(m,n,i+p,j+q) && !visited[i+p][j+q])
                {
                    bool ret = check(board,m,n,i+p,j+q, visited, s);
                    if(ret)
                        return true;
                }
            }
        }

        visited[i][j]=false;
        return false;
    }
    
    bool exist(vector<vector<char>>& board, string word) {
        if(word.size() == 0)
            return false;
        
        int m=board.size();
        int n=board[0].size();

        vector<vector<bool>> visited;
        visited.resize(m);
        for(int i=0; i<m; i++)
            visited[i].resize(n);

        
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                bool ret = check(board,m,n,i,j,visited,word);
                if(ret)
                    return true;
            }
        }

        return false;
    }
};