题解 | #矩阵中的路径#

1. 标准回溯解法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        for(int i = 0; i< matrix.size(); i++){//入口
             for(int j = 0; j< matrix[0].size();j++){

                 if(dfs(matrix,word,i,j,0)){
                     return true;
                 }

             }

        }


        return false;


    }


    bool dfs(vector<vector<char> >& matrix, string word, int i, int j, int index){

        //base case - 1 欲判断-取决于题目(如果出了边界，且当前单词得不等于现在矩阵对应的单词，reture false，否则继续回溯)
        if(i<0||i>=matrix.size() || j<0||j>=matrix[0].size() || matrix[i][j] != word[index]){
            return false;
        }


        //base case - 2 最终判断，取决于预判断
        if(index == word.size()-1){
            return true;
        }


        //开始回溯
        char tmp = matrix[i][j];//先把你给存起来
        matrix[i][j] = '.'; //以选择，以访问

        bool res = dfs(matrix,word,i,j+1,index+1)
                    || dfs(matrix,word,i,j-1,index+1)
                    || dfs(matrix,word,i+1,j,index+1)
                    || dfs(matrix,word,i-1,j,index+1);


        //复原
        matrix[i][j] = tmp;


        return res; //统一判断


    }


};