2022-01-11 1036. 逃离大迷宫

   需要一个哈希表，边缘和最大值1e6,   哈希表存储障碍
   基础变换长*base+宽
   搜索dir数组；
   check函数：check(source,target)
   双端队列组成队列
   写个哈希表记录access到的点，初始存个source，
   队列空和哈希值>max结束
       队列经过的点==target,就输出true
       通过dir开始算
            DFs边缘判定
            判定两个哈希数组是否包含点  
            队列和哈希表添加元素
           return vis.size() > MAX;

java版本：

class Solution {
    long base=131L;
    int max=(int)1e5;
    int edge=(int)1e6;
    HashSet<Long> hashset=new HashSet<>();
    int[][] dirs=new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {

         for(int[] p:blocked) hashset.add(p[0]*base+p[1]);
         int n=blocked.length;
         max=n*(n-1)/2;
        // 深度优先遍历可能复杂度比较高
    
        return check(source,target) && check(target,source);
    }
    public boolean check(int[] s,int[] t){
      HashSet<Long> vised=new HashSet<>();
        ArrayDeque<int[]> queue =new ArrayDeque<>();
        vised.add(s[0]*base+s[1]);
        queue.addLast(s);
        while(!queue.isEmpty() && vised.size()<=max ){
            int[] poll=queue.pollFirst();
             int x=poll[0],y=poll[1];
             if(x==t[0] && y==t[1]) return true;
             for(int[] dir:dirs){
                 int nx=x+dir[0];
                 int ny=y+dir[1];
                 long hash=nx*base+ny;
                 if(nx<0 || nx>=edge || ny<0 || ny>=edge) continue;
                 if(vised.contains(hash)) continue;
                 if(hashset.contains(hash)) continue;
                 queue.addLast( new int[]{nx,ny});
                  vised.add(hash);
                 
             }
       
        }
         return vised.size()>max;

    }

}