题目描述 [ 逃离大迷宫]
在一个 10^6 x 10^6 的网格中,每个网格块的坐标为 (x, y),其中 0 <= x, y < 10^6。
我们从源方格 source 开始出发,意图赶往目标方格 target。每次移动,我们都可以走到网格中在四个方向上相邻的方格,只要该方格不在给出的封锁列表 blocked 上。
只有在可以通过一系列的移动到达目标方格时才返回 true。否则,返回 false。
示例
输入:blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出:false
解释:
从源方格无法到达目标方格,因为我们无法在网格中移动
解题思路
如果走不到那么肯定是source和target被围在了两块不同的区域,并且这两块区域至少有一块的面积是小于等于M=K(K-1)/2的(K是block的大小) 那么就是对source进行如下操作: 从source为起点,去查它最近的且能到达的若干个区域,最多查K(K-1)/2,如果查到target说明它俩并没有在两块不同区域,直接返回true;如果没查到,两种情况——要么souce所有连通区域都查遍了都没有target,此时直接就是false;要么source的连通区域超出K(K-1)/2,说明至少source不是在那块小于等于M=K(K-1)/2的区域,此时把source和target互换重新进行上述步骤。
代码
class Solution {
public:
set<vector<int> > hashset;
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
hashset.clear();
for(int i=0;i<blocked.size();i++)
hashset.insert(blocked[i]);
int m=help(source,target);
if(m==2)return true;
if(m==0)return false;
return help(target,source);
}
int help(vector<int>& source, vector<int>& target){
queue<vector<int> > q;
const int max_num = hashset.size()*(hashset.size()-1)/2;
q.push(source);
int total = 0;
set<vector<int> > visited;
while(!q.empty()&&total<=max_num){
vector<int> temp = q.front();
q.pop();
if(temp==target) return 2;
if(hashset.count(temp) || visited.count(temp)) continue;
total++;
visited.insert(temp);
if(temp[0]!=0) q.push(vector<int>{temp[0]-1, temp[1]});
if(temp[0]!=1e6-1) q.push(vector<int>{temp[0]+1, temp[1]});
if(temp[1]!=0) q.push(vector<int>{temp[0], temp[1]-1});
if(temp[1]!=1e6-1) q.push(vector<int>{temp[0], temp[1]+1});
}
if(!q.empty()) return 1;
else return 0;
}
};