题目描述
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。
注意:
样例
matrix=
[
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]
str="BCCE" , return "true"
str="ASAE" , return "false"
算法1
时间复杂度
参考文献
C++ 代码
class Solution {
public:
vector<int> dx={-1,0,1,0};
vector<int>dy={0,1,0,-1};
bool dfs(vector<vector<char>>& mt, string &s,vector<vector<bool>>&st,int x,int y,int len){
int n=mt.size(),m=mt[0].size();
if(len==s.size()) return true;
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if(a>=0&&a<n&&b>=0&&b<m&&!st[a][b]){
if(mt[a][b]==s[len]){
st[a][b]=true;
if(dfs(mt,s,st,a,b,len+1)) return true;
else st[a][b]=false;
}
}
}
return false;
}
bool hasPath(vector<vector<char>>& mt, string &s) {
if(mt.size()==0) return false;
vector<vector<bool>>st(mt.size(),vector<bool>(mt[0].size(),false));
for(int i=0;i<mt.size();i++)
for(int j=0;j<mt[0].size();j++){
if(mt[i][j]==s[0]){
st[i][j]=true;
if(dfs(mt,s,st,i,j,1)) return true;
st[i][j]=false;
}
}
return false;
}
};