beats 99.27%(25ms) DFS without extra two-dimesion "visited" array and "helper" function

• I'm surprised that many solutions based on DFS create extra two-dimesion array to store "visited". Actually, we don't need it.

``````class Solution {
public:
bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
if (start == destination) return true;
int r = start[0], c = start[1];
maze[r][c] = -1;
int i = r, m = maze.size(), n = maze.front().size();

for (; i > 0 && maze[i - 1][c] != 1; --i); //up
vector<int> next { i, c };
if (i != r && maze[i][c] != -1 && hasPath(maze, next, destination)) return true;

for (i = r; i < m - 1 && maze[i + 1][c] != 1; ++i); //down
next[0] = i;
if (i != r && maze[i][c] != -1 && hasPath(maze, next, destination)) return true;

for (i = c; i > 0 && maze[r][i - 1] != 1; --i); //left
next[0] = r; next[1] = i;
if (i != c && maze[r][i] != -1 && hasPath(maze, next, destination)) return true;

for (i = c; i < n - 1 && maze[r][i + 1] != 1; ++i); //right
next[1] = i;
if (i != c && maze[r][i] != -1 && hasPath(maze, next, destination)) return true;

return false;
}
};
``````

Or (beats 92.48%(26ms)):

``````class Solution {
public:
bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
if (start == destination) return true;
int r = start[0], c = start[1];
maze[r][c] = -1;
int m = maze.size(), n = maze.front().size();

vector<int> next(2);
for (auto &dr: dirs) {
int i = r, j = c, nx = dr[0], ny = dr[1];
while (i + nx >= 0 && i + nx < m && j + ny >= 0 && j + ny < n && maze[i + nx][j + ny] != 1) {
i += nx; j += ny;
}
next[0] = i; next[1] = j;
if ((i != r || j != c) && maze[i][j] != -1 && hasPath(maze, next, destination)) return true;
}
return false;
}
private:
vector<vector<int>> dirs { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.