跳到主要内容

逃离大迷宫

题目描述​

在一个 10^6 x 10^6 的网格中，每个网格上方格的坐标为 (x, y) 。

现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。

每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。同时，不允许走出网格。

只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。

示例​

输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
无法向北或者向东移动是因为方格禁止通行。
无法向南或者向西移动是因为不能走出网格。

提示：

  • 0 <= blocked.length <= 200
  • blocked[i].length == 2
  • 0 <= xi, yi < 106
  • source.length == target.length == 2
  • 0 <= sx, sy, tx, ty < 106
  • source != target
  • 题目数据保证 source 和 target 不在封锁列表内

解题思路​

  1. 利用数学知识（等差数列求和）得到最大封锁区域
  2. 创建一个 std::queue q，用于广度优先搜索待探索的方格。
  3. 创建一个 std::set visited，用于记录是否访问过某个方格。
  4. 注意检查边界条件。

C++ 解法​

#include <queue>
#include <set>
#include <vector>
#include <utility>

class Solution {
public:
    bool isEscapePossible(std::vector<std::vector<int>>& blocked, std::vector<int>& source, std::vector<int>& target) {        
        // 注意：0 <= blocked.length <= 200

        /**
        * -1 -1 -1 -1 -1 -1 -1 -1
        * -1 -1 -1 -1 -1 -1 -1 -1
        * -1 -1 -1 -1 -1 -1 -1 -1
        * -1 -1 -1 -1 -1 -1 -1 -1
        * 0 -1 -1 -1 -1 -1 -1 -1
        * 1  0 -1 -1 -1 -1 -1 -1
        * 1  1  0 -1 -1 -1 -1 -1
        * 1  1  1  0 -1 -1 -1 -1
        */

        // 使用 0 为封锁点,
        // 左下直角三角形区域使用 1 为可通行区域,
        // 右上区域使用 -1 为不可通行区域
        // 能封锁的点最多有 n(n-1) / 2 个 【n 为封锁点数量】由等差数列求得

        if (blocked.empty()) return true;

        int bloced_size = blocked.size();

        // 将 blocked 转换为 set 方便查找
        std::set<std::pair<int, int>> block_set;
        for (auto &block : blocked) {
            block_set.insert({block[0], block[1]});
        }

        int max_area = bloced_size * (bloced_size - 1) / 2;

        // 双向检查 source 能否逃脱 && target 能否逃脱
        return bfs(block_set, source, target, max_area) && bfs(block_set, target, source, max_area);
    }

private:
    bool bfs(std::set<std::pair<int, int> &block_set, std::vector<int> &start, std::vector<int> &end, int max_area)
    {
        std::queue<std::pair<int, int>> q;
        std::set<std::pair<int, int>> visited;

        q.emplace(start[0], start[1]);
        visited.insert({start[0], start[1]});

        // 四个方向 上下左右
        int dirs[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            // 找到目标点
            if (x == end[0] && y == end[1]) return true;

            // 如果访问点数超过最大面积，说明没有被阻塞
            if (visited.size() > max_area) return true;

            // 探索四个方向
            for (auto &dir : dirs) {
                int next_x = x + dir[0];
                int next_y = y + dir[1];

                // 边界检查
                if (next_x < 0 || next_x >= 1000000 || next_y < 0 || next_y >= 1000000) continue;

                // 检查是否被阻塞或已访问
                if (block_set.count({next_x, next_y}) || visited.count({next_x, next_y})) continue;

                visited.insert({next_x, next_y});
                q.push({next_x, next_y});
            }
        }

        return false;
    }
};

LeetCode链接： 1036. 逃离大迷宫