总是会错几个用例,调试一下。然后就OK了。尴尬。
此题重在4点:
1.需要一个record来记录每次走过的状态。
2.需要遍历路径的起始位置,位置任意。
3.dfs深度遍历路径的时候,需要设置记录一下位置,等待所有四种可选位置遍历执行完成之后,需要重置记录状态。
4.处理好dfs边界。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix char字符型vector<vector<>> * @param word string字符串 * @return bool布尔型 */ bool hasPath(vector<vector<char> >& matrix, string word) { if(word.size() == 0 || matrix.size() == 0){ return false; } vector<vector<char> > record = vector<vector<char> >(matrix.size(),vector<char>(matrix[0].size(),0)); for(int i=0;i<matrix.size();i++){ for(int j=0;j<matrix[i].size();j++){ if(dfs(record,matrix,i,j,word)){ return true; } } } return false; } bool dfs(vector<vector<char> >& record,vector<vector<char> >& matrix, int row,int col,string word){ if(row<0 || col<0 || row>=matrix.size() || col >= matrix[0].size() || record[row][col] == 1){ return false; } // write code here record[row][col] = 1; if(matrix[row][col] == word[0]){ if(word.length() == 1){ return true; } string sb_word=word.substr(1); if(dfs(record,matrix,row-1,col,sb_word)){ return true; } if(dfs(record,matrix,row+1,col,sb_word)){ return true; } if(dfs(record,matrix,row,col-1,sb_word)){ return true; } if(dfs(record,matrix,row,col+1,sb_word)){ return true; } } record[row][col] = 0; return false; } };