class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param matrix string字符串
* @param rows int整型
* @param cols int整型
* @param str string字符串
* @return bool布尔型
*/
int m,n,visit[1000][1000],ll;
char mmap[1000][1000];
string tempstr;
string sstr;
int flag = 0;
void dfs(int x,int y,int l){
if(x=m||y=n||l>=ll){
return;
}
if(!visit[x][y]){
visit[x][y] = 1;
tempstr += mmap[x][y];
if(tempstr[l] == sstr[l]){//依次比较每一位,不同就停止
if(tempstr == sstr){
flag = 1;
return ;
}
l++;
dfs(x,y+1,l);
dfs(x+1,y,l);
dfs(x,y-1,l);
dfs(x-1,y,l);
}
tempstr.pop_back();;
visit[x][y] = 0;
}
return ;
}
bool hasPath(string matrix, int rows, int cols, string str) {
// write code here
int k = 0;
ll = str.length();
int len = matrix.length();
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
mmap[i][j] = matrix[k++];//把字符地图做好
}
}
memset(visit,0,sizeof(visit));
m = rows;
n = cols;
tempstr = "";
sstr = str;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
dfs(i,j,0);//地图上的每个点作为起点,去找路径。
if(flag==1)
return true;
tempstr = "";
memset(visit,0,sizeof(visit));
}
}
return false;
}
};