矩阵中的路径

链接：https://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc?answerType=1&f=discussion
来源：牛客网

简单的深度优先搜索，这种题目思路一般都比较明确，就看代码能力如何了。c++代码如下

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(!matrix) return false;
        //把二维数组转换为vector，这个只是个人习惯，不转也无所谓
        for(int i = 0; i < rows; ++i){
            vector<char> tmp;
            vector<bool> tmp_flag;
            for(int j = 0; j < cols; ++j){
                tmp.push_back(matrix[i * cols + j]);
                tmp_flag.push_back(false);
            }
            mat.push_back(tmp);
            travers.push_back(tmp_flag);
        }
        //把字符串转换为string，这个也是我的个人习惯
        for(int i = 0; str[i] != '\0'; ++i){
            path.push_back(str[i]);
        }
        int length = path.size();
        if(length == 0) return true;//如果字符串为空直接返回true
        for(int i = 0; i<rows; ++i){
            for(int j = 0; j<cols; ++j){
                //以每个字母为起点，判断是否可以找到路径，找到则返回true，否则进入下一个字母
                if(is_true(i, j, 0)){
                    return true;
                }
            }
        }
        return false;
    }
    //判断以row，col为起点能否找到路径，index为路径中当前匹配的字母下标
    bool is_true(int row, int col, int index){
        if(index == path.size()) return true;//如果当前下标已经超过路径长度，说明路径匹配完毕，直接返回true
        if(row<0 || row>=mat.size() || col<0 ||col>mat[0].size()) return false;//如果矩阵中当前坐标越界，返回false
        if(path[index] != mat[row][col]) return false;//当前字母不匹配，返回false
        if(travers[row][col] == true) return false;//当前坐标已被访问，返回false
        travers[row][col] = true;//访问当前坐标
        //上下左右四个方向，任有一个方向能找到路径，则返回true，否则返回false，并将该坐标的访问矩阵值置为false
        if(is_true(row-1, col, index+1) || is_true(row+1,col,index+1) || is_true(row,col-1,index+1) || is_true(row,col+1,index+1)){
            return true;
        }
        else{
            travers[row][col] = false;
            return false;
        }
    }
private:
    vector<vector<char>> mat;
    vector<char> path;
    vector<vector<bool>> travers;//坐标访问矩阵
};