https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6?tpId=265&tqId=39216&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13&difficulty=undefined&judgeStatus=undefined&tags=&title=

/*
step 1：优先处理矩阵为空的特殊情况。
step 2：设置flag数组记录某一次路径中矩阵中的位置是否被经过，因此一条路径不能回头。
step 3：遍历矩阵，对每个位置进行递归。
step 4：递归查找的时候，到了矩阵的边界或者是下一个字符与这个位置的字符不匹配，或者节点已经访问过了，或者字符串匹配完成都结束递归。
step 5：访问节点，修改flag数组，向其他四个方向延伸，回溯的时候修改flag数组。*/

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型

     
     */
     bool dfs(vector<vector<char>> &matrix, int n, int m, int i, int j, string word, int k, vector<vector<bool>> &flag)
     {
        if(i<0 || j<0 || i>=n || j>=m || (matrix[i][j] != word[k] || flag[i][j] == true))
        {
            return false;
        }
        if(k==word.size()-1)
        {
            return true;
        }
        flag[i][j]=true;

        if(dfs(matrix, n, m, i-1, j, word, k+1, flag) 
        || dfs(matrix, n, m, i, j-1, word, k+1, flag) 
        || dfs(matrix, n, m, i+1, j, word, k+1, flag)
        || dfs(matrix, n, m, i, j+1, word, k+1, flag))
        {
            return true;
        }

        flag[i][j] = false;
        return false;
     }

    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        if(matrix.empty())
        {
            return false;
        }
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<bool>> flag(n, vector<bool>(m, false));
        for(int i=0; i<n; ++i)
        {
            for(int j=0; j<m; ++j)
            {
                if(dfs(matrix, n, m, i, j, word, 0, flag))
                {
                    return true;
                }
            }
        }

        return false;
    }
};