就是普通的dfs,区别就是选一个方向的时候可以直接走到走不动为止。
时间复杂度: O(n^2), n代表行数
空间复杂度: O(n^2), 用来存储visited二维数组,当然也可以通过改input实现
class Solution {
public:
bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
int m = maze.size();
int n = maze[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
return dfs(maze, start[0], start[1], destination[0], destination[1], visited);
}
private:
bool dfs(vector<vector<int>>& maze, int i, int j, int di, int dj, vector<vector<bool>>& visited) {
if (i == di && j == dj) {
return true;
}
if (visited[i][j]) {
return false;
}
visited[i][j] = true;
vector<vector<int>> directions = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
for (const auto& dir : directions) {
int ni = i + dir[0];
int nj = j + dir[1];
while (ni >= 0 && ni < maze.size() && nj >= 0 && nj < maze[0].size() && maze[ni][nj] == 0) {
ni += dir[0];
nj += dir[1];
}
ni -= dir[0];
nj -= dir[1];
if (dfs(maze, ni, nj, di, dj, visited)) {
return true;
}
}
return false;
}
};
No comments:
Post a Comment