490. The Maze

LeetCode medium original: C# #array #csharp #graph #leetcode #medium #search #string #two-pointers

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

LeetCode Static

В лабиринте есть шар, который может перемещаться по пустым пространствам (представленным как 0) и стенам (представленным как 1). Шар может катиться по пустым пространствам вверх, вниз, влево или вправо, но он не остановится до тех пор, пока не наткнется на стену. Когда шар останавливается, он может выбрать следующее направление.

Дан лабиринт размером m x n, начальная позиция шара и место назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. return true, если шар может остановиться в месте назначения, иначе return 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++ 해법

자동 초안, 제출 전 검토

#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 обход

Если текущая ячейка уже посещена, return false. Если текущая ячейка совпадает с ячейкой назначения, return true. Отметьте текущую ячейку как посещённую. Переберите все четыре направления движения (вверх, вправо, вниз, влево): продвигайтесь в выбранном направлении до тех пор, пока не столкнётесь со стеной или границей. После остановки вызовите DFS для новой позиции.

Результат

Если любой вызов DFS returns true, завершите выполнение и return true. Если ни один путь не приводит к цели, return false.

😎

Vacancies for this task

활성 채용 with overlapping task tags are 표시됨.

전체 채용

아직 활성 채용이 없습니다.