题解 | #矩阵中的路径#

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        bool ans=false;
        // 遍历一遍二维数组 如果说遇到了和word一样字，就进入后面的判断
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                if(matrix[i][j]==word[0])
                {
                    ans=findways(matrix,word,i,j);
                    if(ans==true)
                        return ans;
                }
            }
        }
        return ans;
    }
    
    // 递归判断结果是否是正确的
    // 思考为什么不能用引用传递参数
//     bool findways(vector<vector<char>> & matrix, string word,int i,int j){
    // 因为是回溯，所以matrix这里传递的参数不是引用，这样每次进来的东西修改了，如果结果不对，也不会变
    // 后面把matrix[i][j]设置为空了，如果说是引用的话，则即使结果不对，matrix是引用，回溯的时候也被修改了，之后再回来的时候就出错了。
    bool findways(vector<vector<char>> matrix, string word,int i,int j){
        // 首先先把第一个匹配到的字符删除，字符串也删除
        // 思考：在哪些情况要删除？递归回溯的时候还要不要？
        matrix[i][j]=NULL;
        word.erase(word.begin());
        // 递归结束的条件，字符串全部删完了，则结果正确
        if(word.size()==0)
            return true;
        // 记录答案
        bool retans=false;
        
        // 下面是上下左右四个方向找结果，如果能匹配，就递归调用
        // 注意这里用的&& 是要先判断是不是在范围里面，再访问值的，如果反了，就会有数组越界错误
        if((i-1)>=0 && matrix[i-1][j]==word[0])
        {
            // 访问上一个结点 matrix是修改过的，因为传递的参数不是引用，所以如果答案不正确，也不会使得matrix被修改
            retans=findways(matrix, word, i-1, j);
            if(retans==true)
                return retans;
        }
        // 下面三个一样，最后返回结果
        if( (i+1)<matrix.size() && matrix[i+1][j]==word[0])
        {
            retans=findways(matrix, word, i+1, j);
            if(retans==true)
                return retans;
        }
        if( (j-1)>=0 && matrix[i][j-1]==word[0])
        {
            retans=findways(matrix, word, i, j-1);
            if(retans==true)
                return retans;
        }
        if( (j+1)<matrix[0].size() && matrix[i][j+1]==word[0])
        {
            retans=findways(matrix, word, i, j+1);
            if(retans==true)
                return retans;
        }
        return retans;
        
    }
};