Задача: 1036. Escape a Large Maze
Сложность: hard

Имеется сетка размером 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

👨‍💻 Алгоритм:

1⃣Обработка входных данных:
Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked.

2⃣Проверка простого случая:
Если список blocked пуст, верните true, так как путь не будет заблокирован.
Проверка начальной или целевой клетки:
Если исходная или целевая клетка заблокированы, верните false.

3⃣Поиск пути с использованием BFS или DFS:
Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток.
Если обнаружен путь, верните true, в противном случае верните false.

😎 Решение:

import 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);
    }
}

Ставь 👍 и забирай 📚 Базу знаний