代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
由空地（用 0 表示）和墙（用 1 表示）组成的迷宫 maze 中有一个球。球可以途经空地向 上、下、左、右 四个方向滚动，且在遇到墙壁前不会停止滚动。当球停下时，可以选择向下一个方向滚动。
给你一个大小为 m x n 的迷宫 maze ，以及球的初始位置 start 和目的地 destination ，其中 start = [startrow, startcol] 且 destination = [destinationrow, destinationcol] 。请你判断球能否在目的地停下：如果可以，返回 true ；否则，返回 false 。
你可以 假定迷宫的边缘都是墙壁（参考示例）。
示例 1：
输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4] 输出：true 解释：一种可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。
示例 2：
输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2] 输出：false 解释：不存在能够使球停在目的地的路径。注意，球可以经过目的地，但无法在那里停驻。
示例 3：
输入：maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1] 输出：false
提示：
m == maze.lengthn == maze[i].length1 <= m, n <= 100maze[i][j] is 0 or 1.start.length == 2destination.length == 20 <= startrow, destinationrow <= m0 <= startcol, destinationcol <= nclass Solution:
def hasPath(
self, maze: List[List[int]], start: List[int], destination: List[int]
) -> bool:
def dfs(i, j):
if vis[i][j]:
return
vis[i][j] = True
if [i, j] == destination:
return
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
x, y = i, j
while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0:
x, y = x + a, y + b
dfs(x, y)
m, n = len(maze), len(maze[0])
vis = [[False] * n for _ in range(m)]
dfs(start[0], start[1])
return vis[destination[0]][destination[1]]
class Solution {
private boolean[][] vis;
private int[][] maze;
private int[] d;
private int m;
private int n;
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
m = maze.length;
n = maze[0].length;
d = destination;
this.maze = maze;
vis = new boolean[m][n];
dfs(start[0], start[1]);
return vis[d[0]][d[1]];
}
private void dfs(int i, int j) {
if (vis[i][j]) {
return;
}
vis[i][j] = true;
if (i == d[0] && j == d[1]) {
return;
}
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i, y = j;
int a = dirs[k], b = dirs[k + 1];
while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0) {
x += a;
y += b;
}
dfs(x, y);
}
}
}
class Solution {
public:
vector<vector<int>> maze;
vector<vector<bool>> vis;
vector<int> d;
int m;
int n;
bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
m = maze.size();
n = maze[0].size();
d = destination;
vis.resize(m, vector<bool>(n, false));
this->maze = maze;
dfs(start[0], start[1]);
return vis[d[0]][d[1]];
}
void dfs(int i, int j) {
if (vis[i][j]) return;
vis[i][j] = true;
if (i == d[0] && j == d[1]) return;
vector<int> dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i, y = j;
int a = dirs[k], b = dirs[k + 1];
while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0) {
x += a;
y += b;
}
dfs(x, y);
}
}
};
func hasPath(maze [][]int, start []int, destination []int) bool {
m, n := len(maze), len(maze[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
var dfs func(i, j int)
dfs = func(i, j int) {
if vis[i][j] {
return
}
vis[i][j] = true
if i == destination[0] && j == destination[1] {
return
}
dirs := []int{-1, 0, 1, 0, -1}
for k := 0; k < 4; k++ {
x, y := i, j
a, b := dirs[k], dirs[k+1]
for x+a >= 0 && x+a < m && y+b >= 0 && y+b < n && maze[x+a][y+b] == 0 {
x += a
y += b
}
dfs(x, y)
}
}
dfs(start[0], start[1])
return vis[destination[0]][destination[1]]
}
class Solution:
def hasPath(
self, maze: List[List[int]], start: List[int], destination: List[int]
) -> bool:
m, n = len(maze), len(maze[0])
q = deque([start])
rs, cs = start
vis = {(rs, cs)}
while q:
i, j = q.popleft()
for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = i, j
while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0:
x, y = x + a, y + b
if [x, y] == destination:
return True
if (x, y) not in vis:
vis.add((x, y))
q.append((x, y))
return False
class Solution {
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze[0].length;
boolean[][] vis = new boolean[m][n];
vis[start[0]][start[1]] = true;
Deque<int[]> q = new LinkedList<>();
q.offer(start);
int[] dirs = {-1, 0, 1, 0, -1};
while (!q.isEmpty()) {
int[] p = q.poll();
int i = p[0], j = p[1];
for (int k = 0; k < 4; ++k) {
int x = i, y = j;
int a = dirs[k], b = dirs[k + 1];
while (
x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0) {
x += a;
y += b;
}
if (x == destination[0] && y == destination[1]) {
return true;
}
if (!vis[x][y]) {
vis[x][y] = true;
q.offer(new int[] {x, y});
}
}
}
return false;
}
}
class Solution {
public:
bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
int m = maze.size();
int n = maze[0].size();
queue<vector<int>> q{{start}};
vector<vector<bool>> vis(m, vector<bool>(n));
vis[start[0]][start[1]] = true;
vector<int> dirs = {-1, 0, 1, 0, -1};
while (!q.empty()) {
auto p = q.front();
q.pop();
int i = p[0], j = p[1];
for (int k = 0; k < 4; ++k) {
int x = i, y = j;
int a = dirs[k], b = dirs[k + 1];
while (x + a >= 0 && x + a < m && y + b >= 0 && y + b < n && maze[x + a][y + b] == 0) {
x += a;
y += b;
}
if (x == destination[0] && y == destination[1]) return 1;
if (!vis[x][y]) {
vis[x][y] = true;
q.push({x, y});
}
}
}
return 0;
}
};
func hasPath(maze [][]int, start []int, destination []int) bool {
m, n := len(maze), len(maze[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
vis[start[0]][start[1]] = true
q := [][]int{start}
dirs := []int{-1, 0, 1, 0, -1}
for len(q) > 0 {
i, j := q[0][0], q[0][1]
q = q[1:]
for k := 0; k < 4; k++ {
x, y := i, j
a, b := dirs[k], dirs[k+1]
for x+a >= 0 && x+a < m && y+b >= 0 && y+b < n && maze[x+a][y+b] == 0 {
x += a
y += b
}
if x == destination[0] && y == destination[1] {
return true
}
if !vis[x][y] {
vis[x][y] = true
q = append(q, []int{x, y})
}
}
}
return false
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。