普通dfs 注意u的意义
注意时间复杂度计算
class Solution {
public:
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m;
// u:已经匹配了位置为几的字符
bool dfs(int u,int prex,int prey,int x,int y,const vector<vector<char>>& matrix,const string &str)
{
// std::cout<<u<<" "<<prex<<" "<<prey<<" "<<x<<" "<<y<<endl;
if(u==str.size()-1) return true;
for(int i=0;i!=4;++i)
{
int a = dx[i]+x;
int b = dy[i]+y;
if(a<0||a>=n||b<0||b>=m) continue;
if(a==prex && b==prey) continue;
if(str[u+1]!=matrix[a][b]) continue;
if(dfs(u+1,x,y,a,b,matrix,str)) return true;
}
return false;
}
bool hasPath(vector<vector<char>>& matrix, string &str) {
if(matrix.empty()) return false;
n = matrix.size();
m = matrix[0].size();
for(int i=0;i!=n;++i)
{
for(int j=0;j!=m;++j)
{
if(matrix[i][j]==str[0])
{
// std::cout<<i<<" "<<j<<endl;
if(dfs(0,-1,-1,i,j,matrix,str))
return true;
}
}
}
return false;
}
};