1036. Escape a Large Maze

https://leetcode.com/problems/escape-a-large-maze/

给定二维矩阵起点和最多200个不能走的点，问能否走到终点。不能走到只有两种情况：1）200个不能走的点围住了起点 2）围住了终点。针对这两种情况比较各种围法，参考这里的图:

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

/*
 * @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);
    }
};