• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
bool hasPath(vector<vector<int>>& maze, vector<int>& start,
vector<int>& destination) {
const int m = maze.size();
const int n = maze[0].size();
const vector<int> dirs{0, 1, 0, -1, 0};
queue<pair<int, int>> q{{{start[0], start[1]}}};
vector<vector<bool>> seen(m, vector<bool>(n));
seen[start[0]][start[1]] = true;

while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int x = i;
int y = j;
while (isValid(maze, x + dirs[k], y + dirs[k + 1])) {
x += dirs[k];
y += dirs[k + 1];
}
if (x == destination[0] && y == destination[1])
return true;
if (seen[x][y])
continue;
q.emplace(x, y);
seen[x][y] = true;
}
}

return false;
}

private:
bool isValid(const vector<vector<int>>& maze, int x, int y) {
return 0 <= x && x < maze.size() && 0 <= y && y < maze[0].size() &&
maze[x][y] == 0;
}
};
``````

## JAVA

``````class Solution {
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
final int m = maze.length;
final int n = maze[0].length;
final int[] dirs = {0, 1, 0, -1, 0};
Queue<int[]> q = new ArrayDeque<>(Arrays.asList(new int[] {start[0], start[1]}));
boolean[][] seen = new boolean[m][n];
seen[start[0]][start[1]] = true;

while (!q.isEmpty()) {
final int i = q.peek()[0];
final int j = q.poll()[1];
for (int k = 0; k < 4; ++k) {
int x = i;
int y = j;
while (isValid(maze, x + dirs[k], y + dirs[k + 1])) {
x += dirs[k];
y += dirs[k + 1];
}
if (x == destination[0] && y == destination[1])
return true;
if (seen[x][y])
continue;
q.offer(new int[] {x, y});
seen[x][y] = true;
}
}

return false;
}

private boolean isValid(int[][] maze, int x, int y) {
return 0 <= x && x < maze.length && 0 <= y && y < maze[0].length && maze[x][y] == 0;
}
}
``````

## Python

``````class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m = len(maze)
n = len(maze[0])
dirs = [0, 1, 0, -1, 0]
q = deque([(start[0], start[1])])
seen = {(start[0], start[1])}

def isValid(x: int, y: int) -> bool:
return 0 <= x < m and 0 <= y < n and maze[x][y] == 0

while q:
i, j = q.popleft()
for k in range(4):
x = i
y = j
while isValid(x + dirs[k], y + dirs[k + 1]):
x += dirs[k]
y += dirs[k + 1]
if [x, y] == destination:
return True
if (x, y) in seen:
continue
q.append((x, y))

return False
``````

• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
bool hasPath(vector<vector<int>>& maze, vector<int>& start,
vector<int>& destination) {
return dfs(maze,
vector<vector<bool>>(maze.size(), vector<bool>(maze[0].size())),
start[0], start[1], destination);
}

private:
const vector<int> dirs{0, 1, 0, -1, 0};

bool dfs(vector<vector<int>>& maze, vector<vector<bool>>&& seen, int i, int j,
const vector<int>& destination) {
if (i == destination[0] && j == destination[1])
return true;
if (seen[i][j])
return false;

seen[i][j] = true;

for (int k = 0; k < 4; ++k) {
int x = i;
int y = j;
while (isValid(maze, x + dirs[k], y + dirs[k + 1])) {
x += dirs[k];
y += dirs[k + 1];
}
if (dfs(maze, move(seen), x, y, destination))
return true;
}

return false;
}

bool isValid(const vector<vector<int>>& maze, int x, int y) {
return 0 <= x && x < maze.size() && 0 <= y && y < maze[0].size() &&
maze[x][y] == 0;
}
};
``````

## JAVA

``````class Solution {
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
boolean[][] seen = new boolean[maze.length][maze[0].length];
return dfs(maze, seen, start[0], start[1], destination);
}

private static final int[] dirs = {0, 1, 0, -1, 0};

private boolean dfs(int[][] maze, boolean[][] seen, int i, int j, int[] destination) {
if (i == destination[0] && j == destination[1])
return true;
if (seen[i][j])
return false;

seen[i][j] = true;

for (int k = 0; k < 4; ++k) {
int x = i;
int y = j;
while (isValid(maze, x + dirs[k], y + dirs[k + 1])) {
x += dirs[k];
y += dirs[k + 1];
}
if (dfs(maze, seen, x, y, destination))
return true;
}

return false;
}

private boolean isValid(int[][] maze, int x, int y) {
return 0 <= x && x < maze.length && 0 <= y && y < maze[0].length && maze[x][y] == 0;
}
}
``````

## Python

``````class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m = len(maze)
n = len(maze[0])
dirs = [0, 1, 0, -1, 0]

seen = set()

def isValid(x: int, y: int) -> bool:
return 0 <= x < m and 0 <= y < n and maze[x][y] == 0

def dfs(i: int, j: int) -> bool:
if [i, j] == destination:
return True
if (i, j) in seen:
return False

for k in range(4):
x = i
y = j
while isValid(x + dirs[k], y + dirs[k + 1]):
x += dirs[k]
y += dirs[k + 1]
if dfs(x, y):
return True

return False

return dfs(start[0], start[1])
``````