题解 | #矩阵中的路径#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
    bool f=false;
    bool& found=f;
        //from the first algebra,peek four directions,and decrease the problem into smaller problem.
        //递归
        //recursively solve the smaller problem.
        //every peek,turn the val into negative to note that this element has been visit.

        //return true as soon as a line is found,false if the flag isnt true even if the ptr reaches the end.
        if(matrix.size()==0){
            return false;
        }

        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++){
                if(matrix[i][j]==word[0]){
                    //into backtrace
                    backtrace(matrix,word,found,0,i,j);
                }
            }
        }

        return found;
    }
    //find the corresponding c
    void backtrace(vector<vector<char>> & matrix,string & word,bool & found,int cur,int i,int j){

        //reads current latter ,explore near element.
        //edge condition reaches when i or j reaches the edge of the matrix
        if(i>=matrix.size()||i<0||j<0||j>=matrix[0].size()){//first fault,i equals to the size.
            return ;
        }

        //visit

        //the value is equal ,which means we are going to check the last member of the word,instead of finishing the findings.
        //the second fault is that you miss the last check
        if(found||(cur==word.size()-1 && word[cur]==matrix[i][j])){
            //edge reaches
            found=true;
            return ;
        }
        //if the algebra is right ,visit and set the flag
        if(word[cur]!=matrix[i][j])
            return;
        char tmp=matrix[i][j];
        matrix[i][j]='.';

        backtrace(matrix,word,found,cur+1,i-1,j);
         backtrace(matrix,word,found,cur+1,i+1,j);
          backtrace(matrix,word,found,cur+1,i,1+j);
           backtrace(matrix,word,found,cur+1,i,j-1);

        matrix[i][j]=tmp;

        return ;
        

        

    }
};

思路

1.可以拆解为规模更小的问题，如 word的子串。

2.规模更小的问题难以直接保存结果，无法运用dp，所以使用回溯法。

3.对于每一个开头字母，符合的进行回溯探测

3.1 先定义好回溯函数的功能，比如这里的功能为 “判断边界，判断是否寻找完毕，排除这些情况之后，进行访问，并且继续子问题，子问题结束后，恢复标记并返回。”

3.2 访问需要设置标记，设置过得标记应该及时清理。在这里，假设每一个bck都进行了清理，那么这四句bck运行结束之后并不会修改matrix本身，所以直接在65将matrix修改回来

3.3 需要剪枝，某一个分支寻找完毕之后，对于其他回溯可以直接退出。