package leetcode;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * https://leetcode.com/problems/escape-a-large-maze/
 */
public class Problem1036 {
    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        Set<String> blockedSet = new HashSet<>();
        for (int[] b : blocked) {
            blockedSet.add(toString(b));
        }
        return isEscapePossible(blockedSet, source, target, 1_000_000, 1_000_000);
    }

    private static boolean isEscapePossible(Set<String> blocked, int[] source,
                                            int[] target, int maxRow, int maxCol) {
        Set<String> visited = new HashSet<>();
        Stack<int[]> coordinates = new Stack<>();
        coordinates.add(source);
        while (!coordinates.isEmpty()) {
            int[] pop = coordinates.pop();
            if (pop[0] == target[0] && pop[1] == target[1]) {
                return true;
            }
            if (coordinates.size() >= 1000) {
                return true;
            }
            if ((pop[0] < 0 || pop[0] == maxRow) || (pop[1] < 0 || pop[1] == maxCol)) {
                continue;
            }
            String key = toString(pop);
            if (blocked.contains(key) || visited.contains(key)) {
                continue;
            }
            visited.add(key);
            for (int[] a : new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}) {
                coordinates.add(new int[]{pop[0] + a[0], pop[1] + a[1]});
            }
        }
        return false;
    }

    private static String toString(int[] a) {
        return a[0] + "," + a[1];
    }

    public static void main(String[] args) {
        Problem1036 prob = new Problem1036();
        System.out.println(prob.isEscapePossible(
            new int[][]{{0, 1}, {1, 0}}, new int[]{0, 0}, new int[]{0, 2})); // false
        System.out.println(prob.isEscapePossible(
            new int[][]{}, new int[]{0, 0}, new int[]{999999,999999})); // true
    }
}

@@ -462,16 +462,98 @@
 000_000,
+ 1_000_000) &&%0A            isEscapePossible(blockedSet, target, source, 1_000_000,
  1_000_0
@@ -557,16 +557,16 @@
 0_000);%0A
-
     %7D%0A%0A 
@@ -1050,97 +1050,8 @@
   %7D%0A
-            if (coordinates.size() %3E= 1000) %7B%0A                return true;%0A            %7D%0A
     
@@ -1350,16 +1350,101 @@
 d(key);%0A
+            if (visited.size() %3E 20000) %7B%0A                return true;%0A            %7D%0A
         
@@ -1680,24 +1680,24 @@
 (int%5B%5D a) %7B%0A
+
         retu
@@ -1727,371 +1727,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1036 prob = new Problem1036();%0A        System.out.println(prob.isEscapePossible(%0A            new int%5B%5D%5B%5D%7B%7B0, 1%7D, %7B1, 0%7D%7D, new int%5B%5D%7B0, 0%7D, new int%5B%5D%7B0, 2%7D)); // false%0A        System.out.println(prob.isEscapePossible(%0A            new int%5B%5D%5B%5D%7B%7D, new int%5B%5D%7B0, 0%7D, new int%5B%5D%7B999999,999999%7D)); // true%0A    %7D
 %0A%7D%0A

Solve problem 1036