1036. Escape a Large Maze.md

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 {
    private static int[][] dirs={{0,1},{1,0},{-1,0},{0,-1}};
    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        if(blocked.length==0) return true;
        Set<String> block=new HashSet<>();
        for(int[] blocks:blocked){
            block.add(""+blocks[0]+blocks[1]);
        }
        // we are doing AND operation because we need to make sure that both source and target are not trapped
        return dfs(source,source,target,block,new HashSet<>()) && dfs(target,target,source,block,new HashSet<>());
    }
    public static boolean dfs(int[] curr,int[] source,int[] target,Set<String> blocks,Set<String> visited){
        if(curr[0]==target[0] && curr[1]==target[1]) return true;
        if(Math.abs(curr[0]-source[0])+Math.abs(curr[1]-source[1])>200) return true; // we are calculating the manhanttan distance here like in A* algorithm . this is most important part here as we can't reach target if and only if we are trapped by blocked nodes and those are 200 so we must be trapped by 200 nodes and if cross 200 distance then we dont't have any loop around us
        visited.add(""+curr[0]+curr[1]);
        for(int[] dir:dirs){
            int row=dir[0]+curr[0];
            int col=dir[1]+curr[1];
            
            if(row>=0 && row<=999999 && col>=0 && col<=999999 && !blocks.contains(""+row+col) && !visited.contains(""+row+col) && dfs(new int[]{row,col},source,target,blocks,visited))
                return true;
        }
        return false;
    }
}
 // S W T
 // W 0 0
 // 0 0 0