1036. Escape a Large Maze
leetcode hard
#array#csharp#graph#hard#hash-table#leetcode#matrix#queue#search
Task
Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.
Пример:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
C# solution
matched/originalpublic class Solution {
public bool IsEscapePossible(int[][] blocked, int[] source, int[] target) {
var blockedSet = new HashSet<(int, int)>(blocked.Select(b => (b[0], b[1])));
var src = (source[0], source[1]);
var tgt = (target[0], target[1]);
if (blockedSet.Contains(src) || blockedSet.Contains(tgt)) return false;
var directions = new (int, int)[] { (0, 1), (1, 0), (0, -1), (-1, 0) };
int maxArea = blocked.Length * (blocked.Length - 1) / 2;
bool Bfs((int, int) start, (int, int) end) {
var queue = new Queue<(int, int)>();
queue.Enqueue(start);
var visited = new HashSet<(int, int)> { start };
while (queue.Count > 0) {
if (visited.Count > maxArea) return true;
var (x, y) = queue.Dequeue();
foreach (var (dx, dy) in directions) {
var nx = x + dx;
var ny = y + dy;
var next = (nx, ny);
if (nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.Contains(next) && !blockedSet.Contains(next)) {
if (next == end) return true;
queue.Enqueue(next);
visited.Add(next);
}
}
}
return false;
}
return Bfs(src, tgt) && Bfs(tgt, src);
}
}C++ solution
auto-draft, review before submit#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 IsEscapePossible(int[][] blocked, vector<int>& source, vector<int>& target) {
var blockedSet = new HashSet<(int, int)>(blocked.Select(b => (b[0], b[1])));
var src = (source[0], source[1]);
var tgt = (target[0], target[1]);
if (blockedSet.Contains(src) || blockedSet.Contains(tgt)) return false;
var directions = new (int, int)[] { (0, 1), (1, 0), (0, -1), (-1, 0) };
int maxArea = blocked.size() * (blocked.size() - 1) / 2;
bool Bfs((int, int) start, (int, int) end) {
var queue = new queue<(int, int)>();
queue.Enqueue(start);
var visited = new HashSet<(int, int)> { start };
while (queue.size() > 0) {
if (visited.size() > maxArea) return true;
var (x, y) = queue.Dequeue();
foreach (var (dx, dy) in directions) {
var nx = x + dx;
var ny = y + dy;
var next = (nx, ny);
if (nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.Contains(next) && !blockedSet.Contains(next)) {
if (next == end) return true;
queue.Enqueue(next);
visited.push_back(next);
}
}
}
return false;
}
return Bfs(src, tgt) && Bfs(tgt, src);
}
}Java solution
matched/originalimport java.util.*;
public class Solution {
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
Set<Pair<Integer, Integer>> blockedSet = new HashSet<>();
for (int[] b : blocked) {
blockedSet.add(new Pair<>(b[0], b[1]));
}
Pair<Integer, Integer> src = new Pair<>(source[0], source[1]);
Pair<Integer, Integer> tgt = new Pair<>(target[0], target[1]);
if (blockedSet.contains(src) || blockedSet.contains(tgt)) return false;
List<int[]> directions = Arrays.asList(
new int[]{0, 1}, new int[]{1, 0},
new int[]{0, -1}, new int[]{-1, 0});
int maxArea = blocked.length * (blocked.length - 1) / 2;
boolean bfs(Pair<Integer, Integer> start, Pair<Integer, Integer> end) {
Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
queue.add(start);
Set<Pair<Integer, Integer>> visited = new HashSet<>();
visited.add(start);
while (!queue.isEmpty()) {
if (visited.size() > maxArea) return true;
Pair<Integer, Integer> current = queue.poll();
for (int[] dir : directions) {
int nx = current.getKey() + dir[0];
int ny = current.getValue() + dir[1];
Pair<Integer, Integer> next = new Pair<>(nx, ny);
if (nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.contains(next) && !blockedSet.contains(next)) {
if (next.equals(end)) return true;
queue.add(next);
visited.add(next);
}
}
}
return false;
}
return bfs(src, tgt) && bfs(tgt, src);
}
}JavaScript solution
matched/originalvar isEscapePossible = function(blocked, source, target) {
const blockedSet = new Set(blocked.map(b => `${b[0]},${b[1]}`));
const src = `${source[0]},${source[1]}`;
const tgt = `${target[0]},${target[1]}`;
if (blockedSet.has(src) || blockedSet.has(tgt)) return false;
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const maxArea = blocked.length * (blocked.length - 1) / 2;
const bfs = (start, end) => {
const queue = [start];
const visited = new Set([start]);
while (queue.length) {
if (visited.size > maxArea) return true;
const [x, y] = queue.shift().split(',').map(Number);
for (const [dx, dy] of directions) {
const nx = x + dx, ny = y + dy;
const next = `${nx},${ny}`;
if (nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.has(next) && !blockedSet.has(next)) {
if (next === end) return true;
queue.push(next);
visited.add(next);
}
}
}
return false;
};
return bfs(src, tgt) && bfs(tgt, src);
};Python solution
matched/originalfrom collections import deque
def isEscapePossible(blocked, source, target):
blocked = set(map(tuple, blocked))
source = tuple(source)
target = tuple(target)
if source in blocked or target in blocked:
return False
def bfs(start, end):
queue = deque([start])
visited = set([start])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
max_area = len(blocked) * (len(blocked) - 1) // 2
while queue:
if len(visited) > max_area:
return True
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < 10**6 and 0 <= ny < 10**6 and (nx, ny) not in visited and (nx, ny) not in blocked:
if (nx, ny) == end:
return True
queue.append((nx, ny))
visited.add((nx, ny))
return False
return bfs(source, target) and bfs(target, source)Go solution
matched/originalfunc isEscapePossible(blocked [][]int, source []int, target []int) bool {
blockedSet := make(map[[2]int]struct{})
for _, b := range blocked {
blockedSet[[2]int{b[0], b[1]}] = struct{}{}
}
src := [2]int{source[0], source[1]}
tgt := [2]int{target[0], target[1]}
if _, found := blockedSet[src]; found || _, found := blockedSet[tgt]; found {
return false
}
directions := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
maxArea := len(blocked) * (len(blocked) - 1) / 2
bfs := func(start, end [2]int) bool {
queue := [][2]int{start}
visited := map[[2]int]struct{}{start: {}}
for len(queue) > 0 {
if len(visited) > maxArea {
return true
}
cur := queue[0]
queue = queue[1:]
for _, dir := range directions {
next := [2]int{cur[0] + dir[0], cur[1] + dir[1]}
if next[0] >= 0 && next[0] < 1_000_000 && next[1] >= 0 && next[1] < 1_000_000 {
if _, found := visited[next]; !found {
if _, found := blockedSet[next]; !found {
if next == end {
return true
}
queue = append(queue, next)
visited[next] = struct{}{}
}
}
}
}
}
return false
}
return bfs(src, tgt) && bfs(tgt, src)
}Explanation
Algorithm
Обработка входных данных:
Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked.
Проверка простого случая:
Если список blocked пуст, верните true, так как путь не будет заблокирован.
Проверка начальной или целевой клетки:
Если исходная или целевая клетка заблокированы, верните false.
Поиск пути с использованием BFS или DFS:
Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток.
Если обнаружен путь, верните true, в противном случае верните false.
😎