算法思想：尝试迷宫的每个位置作为起点，进行深度优先搜索，给每次搜索计数为u，如果matrix[x][y]=str[u],则u+1，匹配失败returnfalse，如果u=str。size（）-1表示匹配完成，return true。如果所有位置都尝试未成功，则return false。
class Solution { public: bool hasPath(vector<vector<char>>& matrix, string &str) { for(int i=0;i < matrix.size();i++) for(int j=0;j < matrix[i].size();j++) if(dfs(matrix,str,0,i,j))//把每一个点作为起点尝试匹配字符串 return true; return false; } bool dfs(vector<vector<char>>& matrix, string &str,int u,int x,int y){ if(matrix[x][y]!=str[u])return false;//第u个字符能欧服匹配上 if(u==str.size()-1)return true;//表示字符串所有字符都能匹配成功 int dx[4]={-1,0,0,1}; int dy[4]={0,1,-1,0}; char t=matrix[x][y]; matrix[x][y]='*';//访问过标记成* for(int i=0;i<4;i++){ int a=x+dx[i]; int b=y+dy[i]; if(a>=0&&a<matrix.size()&&b>=0;b<matrix[a].size()){ if(dfs(matrix,str,u+1,a,b))return true; } } matrix[x][y]=t;//回溯 return false; } };
