# Simple DFS solution, beat 97%

• Simple DFS solution
Logic:
the ball can roll four directions. If visited, marked as visited.

``````public class Solution {
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
// dfs
if (maze == null || start == null || destination == null) {
return false;
}
boolean[][] visited = new boolean[maze.length][maze[0].length];
return hasPath(maze, start, destination, visited);
}
private boolean hasPath(int[][] maze, int[] start, int[] dest, boolean[][] visited) {
int y = start[0];
int x = start[1];
if (visited[y][x]) return false;
visited[y][x] = true;
if (x == dest[1] && y == dest[0]) {
return true;
}
// left
if (x > 0 && maze[y][x-1] != 1) {
int i = x - 1;
while (i > 0 && maze[y][i-1] != 1) i--;
if (hasPath(maze, new int[]{y, i}, dest, visited)) return true;
}
//right
if (x < maze[0].length - 1 && maze[y][x+1] != 1) {
int i = x + 1;
while (i < maze[0].length-1 && maze[y][i+1] != 1)  i++;
if (hasPath(maze, new int[]{y, i}, dest, visited)) return true;
}
//up
if (y > 0 && maze[y-1][x] != 1) {
int i = y - 1;
while (i > 0 && maze[i-1][x] != 1) i--;
if (hasPath(maze, new int[]{i, x}, dest, visited)) return true;
}
//down
if (y < maze.length - 1 && maze[y+1][x] != 1) {
int i = y + 1;
while (i < maze.length-1 && maze[i+1][x] != 1) i++;
if (hasPath(maze, new int[]{i, x}, dest, visited)) return true;
}
return false;
}
}
``````

• ``````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;
}
};
``````

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