题解 | #矩阵中的路径#

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix char字符型vector<vector<>> * @param word string字符串 * @return bool布尔型 / bool hasPath(vector<vector >& matrix, string word) { // write code here if(matrix.empty()) { if(word.length()==0) return true; else return false; } int row=matrix.size(); int rll=matrix[0].size(); int len=word.length(); if(len>rowrll) return false; //vector WORD[len+1]; /* for(int i=0;i<len;i++) WORD[i]=word[i]; //将string转为char[] WORD[len]='\0'; */ for(int i=0;i<row;i++) for(int j=0;j<rll;j++) { if(dfs(matrix,word,i,j,0,len)) return true;

        }
    return false;
    
    
}

bool dfs(vector<vector<char>>& matrix,string word,int i,int j,int index,int len)
{
    if(index==len)
        return true;
    if(i<0||i>=matrix.size()||j<0||j>=matrix[0].size())
        return false;
    if(matrix[i][j]==word[index])
    {
        char temp=matrix[i][j];
        matrix[i][j]='.';  //因为是随机回溯查找。可能会使matrix[i][j]被遍历两次，因此暂时更改
        bool res=dfs(matrix,word,i,j+1,index+1,len)||dfs(matrix,word,i+1,j,index+1,len)||dfs(matrix,word,i,j-1,index+1,len)||dfs(matrix,word,i-1,j,index+1,len);
        matrix[i][j]=temp;
        return res;
    }
    else
        return false;
}

};