# 1036. Escape a Large Maze

给定二维矩阵起点和最多200个不能走的点，问能否走到终点。不能走到只有两种情况：1）200个不能走的点围住了起点 2）围住了终点。针对这两种情况比较各种围法，参考[这里](https://link.zhihu.com/?target=https%3A//blog.baozitraining.org/2019/05/leetcode-solution-1036-escape-large-maze.html)的图:![](https://pic2.zhimg.com/80/v2-752e96df64269b7585068a0c047113d5_hd.jpg)

其中图二围得面积最大，为1+2+3+...+ 199 = 19900。所以如果BFS遍历过了19900个点，说明不可能再被200个点围住，也就能到达终点了。

```cpp
/*
 * @lc app=leetcode id=1036 lang=cpp
 *
 * [1036] Escape a Large Maze
 *
 * https://leetcode.com/problems/escape-a-large-maze/description/
 *
 * algorithms
 * Hard (34.97%)
 * Likes:    113
 * Dislikes: 73
 * Total Accepted:    5.4K
 * Total Submissions: 15.3K
 * Testcase Example:  '[[0,1],[1,0]]\n[0,0]\n[0,2]'
 *
 * In a 1 million by 1 million grid, the coordinates of each grid square are
 * (x, y) with 0 <= x, y < 10^6.
 * 
 * We start at the source square and want to reach the target square.  Each
 * move, we can walk to a 4-directionally adjacent square in the grid that
 * isn't in the given list of blocked squares.
 * 
 * Return true if and only if it is possible to reach the target square through
 * a sequence of moves.
 * 
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
 * Output: false
 * Explanation: 
 * The target square is inaccessible starting from the source square, because
 * we can't walk outside the grid.
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: blocked = [], source = [0,0], target = [999999,999999]
 * Output: true
 * Explanation: 
 * Because there are no blocked cells, it's possible to reach the target
 * square.
 * 
 * 
 * 
 * 
 * Note:
 * 
 * 
 * 0 <= blocked.length <= 200
 * blocked[i].length == 2
 * 0 <= blocked[i][j] < 10^6
 * source.length == target.length == 2
 * 0 <= source[i][j], target[i][j] < 10^6
 * source != target
 * 
 * 
 */
class Solution
{
public:
    bool isEscapePossible(vector<vector<int>> &blocked, vector<int> &source, vector<int> &target)
    {
        const auto bfs = [](vector<vector<int>> &blocked, vector<int> &source, vector<int> &target) {
            queue<vector<int>> q;
            q.push(source);
            unordered_set<string> visited, blks;
            for (const auto &blk : blocked)
            {
                blks.insert(to_string(blk[0]) + "," + to_string(blk[1]));
            }
            visited.insert(to_string(source[0]) + "," + to_string(source[1]));
            const vector<vector<int>> dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
            int count = 0;
            while (!q.empty())
            {
                const auto &t = q.front();
                ++count;
                if (t[0] == target[0] && t[1] == target[1])
                    return true;
                for (const auto &dir : dirs)
                {
                    int x = t[0] + dir[0];
                    int y = t[1] + dir[1];
                    string key = to_string(x) + "," + to_string(y);
                    if (x >= 0 && x < 1000000 && y >= 0 && y < 1000000 && !visited.count(key) && !blks.count(key))
                    {
                        q.push({x, y});
                        visited.insert(key);
                    }
                }
                q.pop();

                if (count == 19901)
                    return true;
            }
            return false;
        };
        return bfs(blocked, source, target) && bfs(blocked, target, source);
    }
};

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/search/sao-ge/1036.-escape-a-large-maze.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.