如果思路不是很清晰,可以设置一个vis数组(dfs)
class Solution {
public:
vector<vector<bool>> vis;
int n, m;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
bool dfs(int x, int y, string &str, int t, vector<vector<char>>& matrix){
if(t == str.size()) return true;
vis[x][y] = true;
for(int i = 0; i < 4; i ++ ){
int xx = x + dx[i];
int yy = y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy] && str[t] == matrix[xx][yy]){
if(dfs(xx, yy, str, t + 1, matrix)) return true;
vis[xx][yy] = false;
}
}
return false;
}
bool hasPath(vector<vector<char>>& matrix, string &str) {
n = matrix.size();
if(n == 0) return false;
m = matrix[0].size();
vis = vector<vector<bool>>(n, vector<bool>(m, false));
for(int i = 0; i < n; i ++ ){
for(int j = 0; j < m; j ++ ){
vis = vector<vector<bool>>(n, vector<bool>(m, false));
if(str[0] == matrix[i][j] && dfs(i, j, str, 1, matrix)) return true;
}
}
return false;
}
};
直接在matrix数组上面做修改(回溯复原)dfs
class Solution {
public:
int n, m;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
bool dfs(int x, int y, int t, string &str, vector<vector<char>>& matrix){
if(t == str.size() - 1) return true;
if(matrix[x][y] != str[t]) return false;
int p = matrix[x][y];
matrix[x][y] = '*';
for(int i = 0; i < 4; i ++ ){
int xx = x + dx[i];
int yy = y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && matrix[xx][yy] != '*'){
if(dfs(xx, yy, t + 1, str, matrix)) return true;
}
}
matrix[x][y] = p;
return false;
}
bool hasPath(vector<vector<char>>& matrix, string &str) {
n = matrix.size();
if(n == 0) return false;
m = matrix[0].size();
for(int i = 0; i < n; i ++ ){
for(int j = 0; j < m; j ++ ){
if(dfs(i, j, 0, str, matrix)) return true;
}
}
return false;
}
};