EscapeALargeMaze1.java

private final int[] xDirection = {1, 0, -1, 0};
private final int[] yDirection = {0, -1, 0, 1};
private final int ONE_MILLION = 1000000;

public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        if (blocked == null || source == null || target == null) {
            return false;
        }
        Set<String> blockLookup = this.indexBlockedMatrixToSet(blocked);

        int m = ONE_MILLION;
        int n = ONE_MILLION;

        Set<String> visited = new HashSet<>();

        Queue<String> queue = new LinkedList<>();

        String sourceString = source[0] + "," + source[1];
        queue.offer(sourceString);
        visited.add(sourceString);

        while (!queue.isEmpty()) {
            String[] curBlock = queue.poll().split(",");
            int curX = Integer.parseInt(curBlock[0]);
            int curY = Integer.parseInt(curBlock[1]);

            if (curX == target[0] && curY == target[1]) {
                return true;
            }

            for (int i = 0; i < 4; i++) {
                int nextX = curX + xDirection[i];
                int nextY = curY + yDirection[i];
                if (this.shouldExplore(nextX, nextY, ONE_MILLION, ONE_MILLION, blockLookup, visited)) {
                    String nextKey = nextX + "," + nextY;
                    visited.add(nextKey);
                    queue.offer(nextKey);
                }
            }
        }

        return false;
    }
    

    private boolean shouldExplore(
            int x,
            int y,
            int row,
            int col,
            Set<String> blockLookup,
            Set<String> visited) {
        if (!(x >= 0 && x < row && y >=0 && y < col)) {
            return false;
        }

        String index = x + "," + y;
        if (visited.contains(index)) {
            return false;
        }
        if (blockLookup.contains(index)) {
            return false;
        }

        return true;
    }

    private Set<String> indexBlockedMatrixToSet(int[][] blocked) {
        Set<String> lookup = new HashSet<>();

        for (int i = 0; i < blocked.length; i++) {
            int x = blocked[i][0];
            int y = blocked[i][1];
            String index = x + "," + y;
            lookup.add(index);
        }
        return lookup;
    }