490. The Maze
В лабиринте есть шар, который может перемещаться по пустым пространствам (представленным как 0) и стенам (представленным как 1). Шар может катиться по пустым пространствам вверх, вниз, влево или вправо, но он не остановится до тех пор, пока не наткнется на стену. Когда шар останавливается, он может выбрать следующее направление.
Дан лабиринт размером m x n, начальная позиция шара и место назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните true, если шар может остановиться в месте назначения, иначе верните false.
Вы можете предположить, что границы лабиринта представляют собой стены. В приведённом ниже примере они не указаны.
Пример:
Input: 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]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
C# решение
сопоставлено/оригиналpublic class Solution {
public bool HasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.Length, n = maze[0].Length;
bool[,] visit = new bool[m, n];
return Dfs(m, n, maze, start, destination, visit);
}
private bool Dfs(int m, int n, int[][] maze, int[] curr, int[] destination, bool[,] visit) {
if (visit[curr[0], curr[1]]) return false;
if (curr.SequenceEqual(destination)) return true;
visit[curr[0], curr[1]] = true;
int[][] directions = new int[][] { new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1} };
foreach (var dir in directions) {
int r = curr[0], c = curr[1];
while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0) {
r += dir[0];
c += dir[1];
}
int[] newCurr = new int[] { r - dir[0], c - dir[1] };
if (Dfs(m, n, maze, newCurr, destination, visit)) return true;
}
return false;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public bool HasPath(int[][] maze, vector<int>& start, vector<int>& destination) {
int m = maze.size(), n = maze[0].size();
bool[,] visit = new bool[m, n];
return Dfs(m, n, maze, start, destination, visit);
}
private bool Dfs(int m, int n, int[][] maze, vector<int>& curr, vector<int>& destination, bool[,] visit) {
if (visit[curr[0], curr[1]]) return false;
if (curr.SequenceEqual(destination)) return true;
visit[curr[0], curr[1]] = true;
int[][] directions = new int[][] { new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1} };
foreach (var dir in directions) {
int r = curr[0], c = curr[1];
while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0) {
r += dir[0];
c += dir[1];
}
vector<int>& newCurr = new int[] { r - dir[0], c - dir[1] };
if (Dfs(m, n, maze, newCurr, destination, visit)) return true;
}
return false;
}
}Java решение
сопоставлено/оригиналclass Solution {
public boolean dfs(int m, int n, int[][] maze, int[] curr, int[] destination,
boolean[][] visit) {
if (visit[curr[0]][curr[1]]) {
return false;
}
if (curr[0] == destination[0] && curr[1] == destination[1]) {
return true;
}
visit[curr[0]][curr[1]] = true;
int[] dirX = {0, 1, 0, -1};
int[] dirY = {-1, 0, 1, 0};
for (int i = 0; i < 4; i++) {
int r = curr[0], c = curr[1];
while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0) {
r += dirX[i];
c += dirY[i];
}
if (dfs(m, n, maze, new int[]{r - dirX[i], c - dirY[i]}, destination, visit)) {
return true;
}
}
return false;
}
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze[0].length;
boolean[][] visit = new boolean[m][n];
return dfs(m, n, maze, start, destination, visit);
}
}JavaScript решение
сопоставлено/оригиналclass Solution {
constructor() {
this.directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
}
hasPath(maze, start, destination) {
const m = maze.length, n = maze[0].length;
const visit = Array.from({ length: m }, () => Array(n).fill(false));
return this.dfs(m, n, maze, start, destination, visit);
}
dfs(m, n, maze, curr, destination, visit) {
if (visit[curr[0]][curr[1]]) return false;
if (curr[0] === destination[0] && curr[1] === destination[1]) return true;
visit[curr[0]][curr[1]] = true;
for (const [dx, dy] of this.directions) {
let r = curr[0], c = curr[1];
while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] === 0) {
r += dx;
c += dy;
}
if (this.dfs(m, n, maze, [r - dx, c - dy], destination, visit)) return true;
}
return false;
}
}Python решение
сопоставлено/оригиналclass Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
def dfs(m, n, maze, curr, destination, visit):
if visit[curr[0]][curr[1]]:
return False
if curr == destination:
return True
visit[curr[0]][curr[1]] = True
for dx, dy in directions:
r, c = curr
while 0 <= r < m and 0 <= c < n and maze[r][c] == 0:
r += dx
c += dy
if dfs(m, n, maze, [r - dx, c - dy], destination, visit):
return True
return False
m, n = len(maze), len(maze[0])
visit = [[False] * n for _ in range(m)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
return dfs(m, n, maze, start, destination, visit)Go решение
сопоставлено/оригиналtype Solution struct {
directions [4][2]int
}
func (s *Solution) hasPath(maze [][]int, start []int, destination []int) bool {
m, n := len(maze), len(maze[0])
visit := make([][]bool, m)
for i := range visit {
visit[i] = make([]bool, n)
}
s.directions = [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
return s.dfs(m, n, maze, start, destination, visit)
}
func (s *Solution) dfs(m, n int, maze [][]int, curr, destination []int, visit [][]bool) bool {
if visit[curr[0]][curr[1]] {
return false
}
if curr[0] == destination[0] && curr[1] == destination[1] {
return true
}
visit[curr[0]][curr[1]] = true
for _, dir := range s.directions {
r, c := curr[0], curr[1]
for r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0 {
r += dir[0]
c += dir[1]
}
if s.dfs(m, n, maze, []int{r - dir[0], c - dir[1]}, destination, visit) {
return true
}
}
return false
}Algorithm
Инициализация и подготовка данных
Определите количество строк и столбцов в лабиринте (m и n). Создайте 2D массив visit для отслеживания посещённых ячеек. Запустите DFS (глубокий поиск) с начальной позиции.
DFS обход
Если текущая ячейка уже посещена, верните false. Если текущая ячейка совпадает с ячейкой назначения, верните true. Отметьте текущую ячейку как посещённую. Переберите все четыре направления движения (вверх, вправо, вниз, влево): продвигайтесь в выбранном направлении до тех пор, пока не столкнётесь со стеной или границей. После остановки вызовите DFS для новой позиции.
Результат
Если любой вызов DFS возвращает true, завершите выполнение и верните true. Если ни один путь не приводит к цели, верните false.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.