Задача: 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.

😎 Решение:

class Solution {
public:
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        set<pair<int, int>> blocked_set;
        for (const auto& b : blocked) {
            blocked_set.emplace(b[0], b[1]);
        }

        if (blocked_set.count({source[0], source[1]}) || blocked_set.count({target[0], target[1]})) {
            return false;
        }

        auto bfs = [&](vector<int>& start, vector<int>& end) {
            queue<pair<int, int>> q;
            q.push({start[0], start[1]});
            set<pair<int, int>> visited;
            visited.emplace(start[0], start[1]);
            vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            int max_area = blocked.size() * (blocked.size() - 1) / 2;

            while (!q.empty()) {
                if (visited.size() > max_area) {
                    return true;
                }
                auto [x, y] = q.front();
                q.pop();
                for (auto [dx, dy] : directions) {
                    int nx = x + dx, ny = y + dy;
                    if (nx >= 0 && nx < 1'000'000 && ny >= 0 && ny < 1'000'000 && !visited.count({nx, ny}) && !blocked_set.count({nx, ny})) {
                        if (nx == end[0] && ny == end[1]) {
                            return true;
                        }
                        q.push({nx, ny});
                        visited.emplace(nx, ny);
                    }
                }
            }
            return false;
        };

        return bfs(source, target) && bfs(target, source);
    }
};

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