1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
private:
char* matrix;
int rows;
int cols;
char* str;
bool* visited;
public:
bool hasPath(char* matrix, int rows, int cols, char* str){
if(matrix==NULL || rows<=0 || cols<=0 || str==NULL) return false;
this->matrix=matrix;
this->rows=rows;
this->cols=cols;
this->str=str;
visited=new bool[rows*cols];
memset(visited,false,rows*cols);
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(hasPath(i,j,0)) return true;
}
}
return false;
}
bool hasPath(int row,int col,int pos){
if(str[pos]=='\0') return true;
if(row>=rows || row<0 || col>=cols || col<0) return false;
if(visited[row*cols+col] || matrix[row*cols+col]!=str[pos]) return false;
visited[row*cols+col]=true;
pos++;
bool left=hasPath(row,col-1,pos);
bool right=hasPath(row,col+1,pos);
bool up=hasPath(row-1,col,pos);
bool down=hasPath(row+1,col,pos);
if(left||right||up||down) return true;
visited[row*cols+col]=false;
return false;
}
};
|