题解 | #矩阵中的路径#

class Solution { public: bool hasPath(vector<vector>& matrix, string word) { int row = matrix.size(); //行 int col = matrix[0].size(); //列 if(matrix.empty() || row<1 || col<1){
        return false;
    }   //如果矩阵为空或者行列为0，直接返回false

    vector<vector<bool> > visited(row, vector<bool>(col, 0));  //定义一个二维向量，尺寸等于matrix，储存内容为是否访问过这个点
    int pathLength = 0;  //pathLength 走到第几个字符了
    for(int r=0; r<row; ++r){
        for(int c=0;c<col;++c){
            if(hashPathCore(matrix,row,col,r,c,word,pathLength,visited)){
                return true;
            }  //遍历全部元素，hashPathCore返回true，则说明存在路径，返回true
        }
    }
    return false; //否则返回false
}


bool hashPathCore(vector<vector<char> >& matrix, int row,int col, int r, int c, string& word, int pathLength, vector<vector<bool> > visited) //核心函数，判断路径是否存在 { if(word[pathLength] == '\0'){ return true; }//string最后一个字符为'\0'，可以用来判断是否走到了最后一个字符
  bool hashPath = false;  //hashPath为路径是否存在的标识符，初始化hashPath为0

    if(r>=0 && c>=0 && r<row && c<col && matrix[r][c] == word[pathLength] && !visited[r][c])
{ //如果matrix[r][c] == word[pathLength]，pathlength+1，指向word的下一个元素，并且visited[r][c]置1，表示走过这里了；  
++pathLength; 
visited[r][c] = true;  
//然后依次遍历上下左右四个格子 
hashPath = hashPathCore(matrix,row,col,r,c-1,word,pathLength,visited)|| 
hashPathCore(matrix,row,col,r,c+1,word,pathLength,visited)|| 
hashPathCore(matrix,row,col,r-1,c,word,pathLength,visited)|| 
hashPathCore(matrix,row,col,r+1,c,word,pathLength,visited);
 if(!hashPath){
            --pathLength;
            visited[r][c] = false;
        }//如果走该路径不行，就--pathLength，并且再把visited[r][c]置0，回溯
    }

    return hashPath;
}

	};