public final class Point {
    public final int x;
    public final int y;
    
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + x;
        result = prime * result + y;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        Point other = (Point) obj;
        return x == other.x && y == other.y;
    }
    
    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }
    
} public class GridGraph {

    private boolean[] tiles; // Flattened 2D Array
    public final int sizeX;
    public final int sizeY;
    public final int sizeXplusOne;

    private static final float SQRT_TWO = (float)Math.sqrt(2);
    private static final double SQRT_TWO_DOUBLE = Math.sqrt(2);
    private static final float SQRT_TWO_MINUS_ONE = (float)(Math.sqrt(2) - 1);
    
    public GridGraph(int sizeX, int sizeY) {
        this.sizeX = sizeX;
        this.sizeY = sizeY;
        this.sizeXplusOne = sizeX+1;
        
        tiles = new boolean[sizeY*sizeX];
    }
    
    public final void setBlocked(int x, int y, boolean value) {
        tiles[sizeX*y + x] = value;
    }
    
    public final void trySetBlocked(int x, int y, boolean value) {
        if (isValidBlock(x,y))
            tiles[sizeX*y + x] = value;
    }
    
    public final boolean isBlocked(int x, int y) {
        if (x >= sizeX || y >= sizeY) return true;
        if (x < 0 || y < 0) return true;
        return tiles[sizeX*y + x];
    }
    
    public final boolean isBlockedRaw(int x, int y) {
        return tiles[sizeX*y + x];
    }
    
    public final boolean isValidCoordinate(int x, int y) {
        return (x <= sizeX && y <= sizeY &&
                x >= 0 && y >= 0);
    }
    
    public final boolean isValidBlock(int x, int y) {
        return (x < sizeX && y < sizeY &&
                x >= 0 && y >= 0);
    }

    public final int toOneDimIndex(int x, int y) {
        return y*sizeXplusOne + x;
    }
    
    public final int toTwoDimX(int index) {
        return index%sizeXplusOne;
    }
    
    public final int toTwoDimY(int index) {
        return index/sizeXplusOne;
    }

    public final boolean isUnblockedCoordinate(int x, int y) {
        return !topRightOfBlockedTile(x,y) ||
                !topLeftOfBlockedTile(x,y) ||
                !bottomRightOfBlockedTile(x,y) ||
                !bottomLeftOfBlockedTile(x,y);
    }
    
    public final boolean topRightOfBlockedTile(int x, int y) {
        return isBlocked(x-1, y-1);
    }

    public final boolean topLeftOfBlockedTile(int x, int y) {
        return isBlocked(x, y-1);
    }

    public final boolean bottomRightOfBlockedTile(int x, int y) {
        return isBlocked(x-1, y);
    }

    public final boolean bottomLeftOfBlockedTile(int x, int y) {
        return isBlocked(x, y);
    }
    
    /**
     * x1,y1,x2,y2 refer to the top left corner of the tile.
     * @param x1 Condition: x1 between 0 and sizeX inclusive.
     * @param y1 Condition: y1 between 0 and sizeY inclusive.
     * @param x2 Condition: x2 between 0 and sizeX inclusive.
     * @param y2 Condition: y2 between 0 and sizeY inclusive.
     * @return distance.
     */
    public final float distance(int x1, int y1, int x2, int y2) {
        int xDiff = x2 - x1;
        int yDiff = y2 - y1;
        
        if (yDiff == 0) {
            return (float)Math.abs(xDiff);
        }
        if (xDiff == 0) {
            return (float)Math.abs(yDiff);
        }
        if (xDiff == yDiff || xDiff == -yDiff) {
            return SQRT_TWO*Math.abs(xDiff);
        }
        
        int squareDistance = xDiff*xDiff + yDiff*yDiff;
        
        return (float)Math.sqrt(squareDistance);
    }
    
    public final double distance_double(int x1, int y1, int x2, int y2) {
        int xDiff = x2 - x1;
        int yDiff = y2 - y1;
        
        if (xDiff == 0) {
            return Math.abs(yDiff);
        }
        if (yDiff == 0) {
            return Math.abs(xDiff);
        }
        if (xDiff == yDiff || xDiff == -yDiff) {
            return SQRT_TWO_DOUBLE*Math.abs(xDiff);
        }
        
        int squareDistance = xDiff*xDiff + yDiff*yDiff;
        
        return Math.sqrt(squareDistance);
    }
    
    /**
     * Octile distance:
     *   min(dx,dy)*sqrt(2) + (max(dx,dy)-min(dx,dy))
     * = min(dx,dy)*(sqrt(2)-1) + max(dx,dy)
     */
    public final float octileDistance(int x1, int y1, int x2, int y2) {
        int dx = x1-x2;
        int dy = y1-y2;
        if (dx<0) dx = -dx;
        if (dy<0) dy = -dy;
        
        int min = dx;
        int max = dy;
        if (dy < dx) {
            min = dy;
            max = dx;
        }
        
        return min*SQRT_TWO_MINUS_ONE + max;
    }

    /**
     * Same as lineOfSight, but only works with a vertex and its 8 immediate neighbours.
     * Also (x1,y1) != (x2,y2)
     */
    public final boolean neighbourLineOfSight(int x1, int y1, int x2, int y2) {
        if (x1 == x2) {
            if (y1 > y2) {
                return !isBlocked(x1,y2) || !isBlocked(x1-1,y2);
            } else { // y1 < y2
                return !isBlocked(x1,y1) || !isBlocked(x1-1,y1);
            }
        } else if (x1 < x2) {
            if (y1 == y2) {
                return !isBlocked(x1,y1) || !isBlocked(x1,y1-1);
            } else if (y1 < y2) {
                return !isBlocked(x1,y1);
            } else { // y2 < y1
                return !isBlocked(x1,y2);
            }
        } else { // x2 < x1
            if (y1 == y2) {
                return !isBlocked(x2,y1) || !isBlocked(x2,y1-1);
            } else if (y1 < y2) {
                return !isBlocked(x2,y1);
            } else { // y2 < y1
                return !isBlocked(x2,y2);
            }
        }
    }


    /**
     * @return true iff there is line-of-sight from (x1,y1) to (x2,y2).
     */
    public final boolean lineOfSight(int x1, int y1, int x2, int y2) {
        int dy = y2 - y1;
        int dx = x2 - x1;

        int f = 0;

        int signY = 1;
        int signX = 1;
        int offsetX = 0;
        int offsetY = 0;
        
        if (dy < 0) {
            dy *= -1;
            signY = -1;
            offsetY = -1;
        }
        if (dx < 0) {
            dx *= -1;
            signX = -1;
            offsetX = -1;
        }
        
        if (dx >= dy) {
            while (x1 != x2) {
                f += dy;
                if (f >= dx) {
                    if (isBlocked(x1 + offsetX, y1 + offsetY))
                        return false;
                    y1 += signY;
                    f -= dx;
                }
                if (f != 0 && isBlocked(x1 + offsetX, y1 + offsetY))
                    return false;
                if (dy == 0 && isBlocked(x1 + offsetX, y1) && isBlocked(x1 + offsetX, y1 - 1))
                    return false;
                
                x1 += signX;
            }
        }
        else {
            while (y1 != y2) {
                f += dx;
                if (f >= dy) {
                    if (isBlocked(x1 + offsetX, y1 + offsetY))
                        return false;
                    x1 += signX;
                    f -= dy;
                }
                if (f != 0 && isBlocked(x1 + offsetX, y1 + offsetY))
                    return false;
                if (dx == 0 && isBlocked(x1, y1 + offsetY) && isBlocked(x1 - 1, y1 + offsetY))
                    return false;
                
                y1 += signY;
            }
        }
        return true;
    }

    public final Point findFirstBlockedTile(int x1, int y1, int dx, int dy) {
        
        int f = 0;

        int signY = 1;
        int signX = 1;
        int offsetX = 0;
        int offsetY = 0;
        
        if (dy < 0) {
            dy *= -1;
            signY = -1;
            offsetY = -1;
        }
        if (dx < 0) {
            dx *= -1;
            signX = -1;
            offsetX = -1;
        }
        
        if (dx >= dy) {
            while (true) {
                f += dy;
                if (f >= dx) {
                    if (isBlocked(x1 + offsetX, y1 + offsetY))
                        return new Point(x1+offsetX, y1+offsetY);
                    y1 += signY;
                    f -= dx;
                }
                if (f != 0 && isBlocked(x1 + offsetX, y1 + offsetY))
                    return new Point(x1+offsetX, y1+offsetY);
                if (dy == 0 && isBlocked(x1 + offsetX, y1) && isBlocked(x1 + offsetX, y1 - 1))
                    return new Point(x1+offsetX, -1);
                
                x1 += signX;
            }
        }
        else {
            while (true) {
                f += dx;
                if (f >= dy) {
                    if (isBlocked(x1 + offsetX, y1 + offsetY))
                        return new Point(x1+offsetX, y1+offsetY);
                    x1 += signX;
                    f -= dy;
                }
                if (f != 0 && isBlocked(x1 + offsetX, y1 + offsetY))
                    return new Point(x1+offsetX, y1+offsetY);
                if (dx == 0 && isBlocked(x1, y1 + offsetY) && isBlocked(x1 - 1, y1 + offsetY))
                    return new Point(-1, y1+offsetY);
                
                y1 += signY;
            }
        }
        //return null;
    }
    

    /**
     * Used by Accelerated A* and MazeAnalysis.
     * leftRange is the number of blocks you can move left before hitting a blocked tile.
     * downRange is the number of blocks you can move down before hitting a blocked tile.
     * For blocked tiles, leftRange, downRange are both -1.
     * 
     * How to use the maxRange property:
     * 
     *  x,y is the starting point.
     *  k is the number of tiles diagonally up-right of the starting point.
     *  int i = x-y+sizeY;
     *  int j = Math.min(x, y);
     *  return maxRange[i][j + k] - k;
     */
    public final int[][] computeMaxDownLeftRanges() {
        int[][] downRange = new int[sizeY+1][sizeX+1];
        int[][] leftRange = new int[sizeY+1][sizeX+1];

        for (int y=0; y<sizeY; ++y) {
            if (isBlocked(0, y))
                leftRange[y][0] = -1;
            else 
                leftRange[y][0] = 0;
            
            for (int x=1; x<sizeX; ++x) {
                if (isBlocked(x, y)) {
                    leftRange[y][x] = -1;
                } else {
                    leftRange[y][x] = leftRange[y][x-1] + 1;
                }
            }
        }

        for (int x=0; x<sizeX; ++x) {
            if (isBlocked(x, 0))
                downRange[0][x] = -1;
            else 
                downRange[0][x] = 0;
            
            for (int y=1; y<sizeY; ++y) {
                if (isBlocked(x, y)) {
                    downRange[y][x] = -1;
                } else {
                    downRange[y][x] = downRange[y-1][x] + 1;
                }
            }
        }
        
        for (int x=0; x<sizeX+1; ++x) {
            downRange[sizeY][x] = -1;
            leftRange[sizeY][x] = -1;
        }
        
        for (int y=0; y<sizeY; ++y) {
            downRange[y][sizeX] = -1;
            leftRange[y][sizeX] = -1;
        }
        
        int[][] maxRanges = new int[sizeX+sizeY+1][];
        int maxSize = Math.min(sizeX, sizeY) + 1;
        for (int i=0; i<maxRanges.length; ++i) {
            int currSize = Math.min(i+1, maxRanges.length-i);
            if (maxSize < currSize)
                currSize = maxSize;
            maxRanges[i] = new int[currSize];
            
            int currX = i - sizeY;
            if (currX < 0) currX = 0;
            int currY = currX - i + sizeY;
            for (int j=0; j<maxRanges[i].length; ++j) {
                maxRanges[i][j] = Math.min(downRange[currY][currX], leftRange[currY][currX]);
                currY++;
                currX++;
            }
            
        }
        return maxRanges;
    }
    
    /**
     * @return the percentage of blocked tiles as compared to the total grid size.
     */
    public final float getPercentageBlocked() {
        return (float)getNumBlocked() / (sizeX*sizeY);
    }
    
    /**
     * @return the number of blocked tiles in the grid.
     */
    public final int getNumBlocked() {
        int nBlocked = 0;
        for (int y=0; y<sizeY; y++) {
            for (int x=0; x<sizeX; x++) {
                if (isBlocked(x, y)) {
                    nBlocked++;
                }
            }
        }
        return nBlocked;
    }

    public final boolean isOuterCorner(int x, int y) {
        boolean a = isBlocked(x-1, y-1);
        boolean b = isBlocked(x, y-1);
        boolean c = isBlocked(x, y);
        boolean d = isBlocked(x-1, y);
        
        return ((!a && !c) || (!d && !b)) && (a || b || c || d);
        
        /* NOTE
         *   ___ ___
         *  |   |||||
         *  |...X'''| <-- this is considered a corner in the above definition
         *  |||||___|
         *  
         *  The definition below excludes the above case.
         */
        
        /*int results = 0;
        if(a)results++;
        if(b)results++;
        if(c)results++;
        if(d)results++;
        return (results == 1);*/
    }

    /**
     * Checks whether the path (x1,y1),(x2,y2),(x3,y3) is taut.
     */
    public final boolean isTaut(int x1, int y1, int x2, int y2, int x3, int y3) {
        if (x1 < x2) {
            if (y1 < y2) {
                return isTautFromBottomLeft(x1, y1, x2, y2, x3, y3);
            } else if (y2 < y1) {
                return isTautFromTopLeft(x1, y1, x2, y2, x3, y3);
            } else { // y1 == y2
                return isTautFromLeft(x1, y1, x2, y2, x3, y3);
            }
        } else if (x2 < x1) {
            if (y1 < y2) {
                return isTautFromBottomRight(x1, y1, x2, y2, x3, y3);
            } else if (y2 < y1) {
                return isTautFromTopRight(x1, y1, x2, y2, x3, y3);
            } else { // y1 == y2
                return isTautFromRight(x1, y1, x2, y2, x3, y3);
            }
        } else { // x2 == x1
            if (y1 < y2) {
                return isTautFromBottom(x1, y1, x2, y2, x3, y3);
            } else if (y2 < y1) {
                return isTautFromTop(x1, y1, x2, y2, x3, y3);
            } else { // y1 == y2
                throw new UnsupportedOperationException("v == u?");
            }
        }
    }

    
    private final boolean isTautFromBottomLeft(int x1, int y1, int x2, int y2, int x3,
            int y3) {
        if (x3 < x2 || y3 < y2) return false;
        
        int compareGradients = (y2-y1)*(x3-x2) - (y3-y2)*(x2-x1); // m1 - m2
        if (compareGradients < 0) { // m1 < m2
            return bottomRightOfBlockedTile(x2, y2);
        } else if (compareGradients > 0) { // m1 > m2
            return topLeftOfBlockedTile(x2, y2);
        } else { // m1 == m2
            return true;
        }
    }

    
    private final boolean isTautFromTopLeft(int x1, int y1, int x2, int y2, int x3,
            int y3) {
        if (x3 < x2 || y3 > y2) return false;
        
        int compareGradients = (y2-y1)*(x3-x2) - (y3-y2)*(x2-x1); // m1 - m2
        if (compareGradients < 0) { // m1 < m2
            return bottomLeftOfBlockedTile(x2, y2);
        } else if (compareGradients > 0) { // m1 > m2
            return topRightOfBlockedTile(x2, y2);
        } else { // m1 == m2
            return true;
        }
    }
    
    private final boolean isTautFromBottomRight(int x1, int y1, int x2, int y2, int x3,
            int y3) {
        if (x3 > x2 || y3 < y2) return false;
        int compareGradients = (y2-y1)*(x3-x2) - (y3-y2)*(x2-x1); // m1 - m2
        if (compareGradients < 0) { // m1 < m2
            return topRightOfBlockedTile(x2, y2);
        } else if (compareGradients > 0) { // m1 > m2
            return bottomLeftOfBlockedTile(x2, y2);
        } else { // m1 == m2
            return true;
        }
    }

    
    private final boolean isTautFromTopRight(int x1, int y1, int x2, int y2, int x3,
            int y3) {
        if (x3 > x2 || y3 > y2) return false;
        
        int compareGradients = (y2-y1)*(x3-x2) - (y3-y2)*(x2-x1); // m1 - m2
        if (compareGradients < 0) { // m1 < m2
            return topLeftOfBlockedTile(x2, y2);
        } else if (compareGradients > 0) { // m1 > m2
            return bottomRightOfBlockedTile(x2, y2);
        } else { // m1 == m2
            return true;
        }
    }

    
    private final boolean isTautFromLeft(int x1, int y1, int x2, int y2, int x3,
            int y3) {
        if (x3 < x2) return false;
        
        int dy = y3 - y2;
        if (dy < 0) { // y3 < y2
            return topRightOfBlockedTile(x2, y2);
        } else if (dy > 0) { // y3 > y2
            return bottomRightOfBlockedTile(x2, y2);
        } else { // y3 == y2
            return true;
        }
    }

    private final boolean isTautFromRight(int x1, int y1, int x2, int y2, int x3,
            int y3) {
        if (x3 > x2) return false;
        
        int dy = y3 - y2;
        if (dy < 0) { // y3 < y2
            return topLeftOfBlockedTile(x2, y2);
        } else if (dy > 0) { // y3 > y2
            return bottomLeftOfBlockedTile(x2, y2);
        } else { // y3 == y2
            return true;
        }
    }

    private final boolean isTautFromBottom(int x1, int y1, int x2, int y2, int x3,
            int y3) {
        if (y3 < y2) return false;
        
        int dx = x3 - x2;
        if (dx < 0) { // x3 < x2
            return topRightOfBlockedTile(x2, y2);
        } else if (dx > 0) { // x3 > x2
            return topLeftOfBlockedTile(x2, y2);
        } else { // x3 == x2
            return true;
        }
    }

    private final boolean isTautFromTop(int x1, int y1, int x2, int y2, int x3,
            int y3) {
        if (y3 > y2) return false;
        
        int dx = x3 - x2;
        if (dx < 0) { // x3 < x2
            return bottomRightOfBlockedTile(x2, y2);
        } else if (dx > 0) { // x3 > x2
            return bottomLeftOfBlockedTile(x2, y2);
        } else { // x3 == x2
            return true;
        }
    }
} public class MazeAnalysis {
    
    public int sizeX;
    public int sizeY;
    public int nBlocked;
    public float blockDensity;
    public float averageOpenSpaceSize;
    public float averageBlockedIslandSize;
    public float averageFloatingBlockedIslandSize;
    public float largestRatioToSecond;
    public float largestRatioToRemaining;
    
    public boolean hasSqueezableCorners;
    public ArrayList<ArrayList<Point>> connectedSets;
    public ArrayList<Point> largestConnectedSet;
    
    public Options options;

    public MazeAnalysis(GridGraph gridGraph) {
        this.sizeX = gridGraph.sizeX;
        this.sizeY = gridGraph.sizeY;
        this.nBlocked = gridGraph.getNumBlocked();
        this.blockDensity = (float)nBlocked / (sizeX*sizeY);
        this.hasSqueezableCorners = checkHasSqueezableCorners(gridGraph);
        this.connectedSets = findConnectedSetsFast(gridGraph);
        this.largestConnectedSet = getLargestSet(connectedSets);
        this.largestRatioToSecond = getLargestComponentRatioToSecondLargest(connectedSets);
        this.largestRatioToRemaining = getLargestComponentRatioToRemaining(connectedSets);
        this.averageOpenSpaceSize = computeAverageMaxSquare(gridGraph);
        this.averageBlockedIslandSize = computeAverageBlockedIslandSize(gridGraph, true);
        this.averageFloatingBlockedIslandSize = computeAverageBlockedIslandSize(gridGraph, false);
    }

    public MazeAnalysis(GridGraph gridGraph, Options o) {
        
        if (o.sizeX) this.sizeX = gridGraph.sizeX;
        if (o.sizeY) this.sizeY = gridGraph.sizeY;
        if (o.nBlocked||o.blockDensity) this.nBlocked = gridGraph.getNumBlocked();
        if (o.blockDensity) this.blockDensity = (float)nBlocked / (sizeX*sizeY);
        if (o.hasSqueezableCorners) this.hasSqueezableCorners = checkHasSqueezableCorners(gridGraph);
        if (o.connectedSets||o.largestConnectedSet||o.largestRatioToSecond||o.largestRatioToRemaining) this.connectedSets = findConnectedSetsFast(gridGraph);
        if (o.largestConnectedSet) this.largestConnectedSet = getLargestSet(connectedSets);
        if (o.largestRatioToSecond) this.largestRatioToSecond = getLargestComponentRatioToSecondLargest(connectedSets);
        if (o.largestRatioToRemaining) this.largestRatioToRemaining = getLargestComponentRatioToRemaining(connectedSets);
        if (o.averageOpenSpaceSize) this.averageOpenSpaceSize = computeAverageMaxSquare(gridGraph);
        if (o.averageBlockedIslandSize) this.averageBlockedIslandSize = computeAverageBlockedIslandSize(gridGraph, true);
        if (o.averageFloatingBlockedIslandSize) this.averageFloatingBlockedIslandSize = computeAverageBlockedIslandSize(gridGraph, false);
        this.options = o;
    }
    
    public static MazeAnalysis options(GridGraph gridGraph, String... options) {
        return new MazeAnalysis(gridGraph, new Options(options));
    }
    
    public static boolean checkHasSqueezableCorners(GridGraph gridGraph) {
        for (int y=1; y<gridGraph.sizeY; y++) {
            for (int x=1; x<gridGraph.sizeX; x++) {
                if (gridGraph.bottomLeftOfBlockedTile(x, y) && gridGraph.topRightOfBlockedTile(x, y) &&
                        !gridGraph.bottomRightOfBlockedTile(x, y) && !gridGraph.topLeftOfBlockedTile(x, y)) {
                    return true;
                }
                if (gridGraph.bottomRightOfBlockedTile(x, y) && gridGraph.topLeftOfBlockedTile(x, y) &&
                        !gridGraph.bottomLeftOfBlockedTile(x, y) && !gridGraph.topRightOfBlockedTile(x, y)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    public static ArrayList<Point> getLargestSet(ArrayList<ArrayList<Point>> sets) {
        ArrayList<Point> largestSet = null;
        int largestSize = 0;
        
        for (ArrayList<Point> set : sets) {
            if (set.size() > largestSize) {
                largestSet = set;
                largestSize = set.size();
            }
        }
        
        return largestSet;
    }
    
    public static float getLargestComponentRatioToSecondLargest(ArrayList<ArrayList<Point>> sets) {
        int largestSize = 0;
        int secondLargestSize = 0;
        
        for (ArrayList<Point> set : sets) {
            int size = set.size();
            if (size > secondLargestSize) {
                if (size > largestSize) {
                    secondLargestSize = largestSize;
                    largestSize = size;
                } else {
                    secondLargestSize = size;
                }
            }
        }
        
        return (float)largestSize / secondLargestSize;
    }

    
    public static float getLargestComponentRatioToRemaining(ArrayList<ArrayList<Point>> sets) {
        int totalSize = 0;
        int largestSize = 0;
        
        for (ArrayList<Point> set : sets) {
            int size = set.size();
            if (size > largestSize) {
                largestSize = size;
            }
            totalSize += size;
        }
        
        return (float)largestSize / (totalSize-largestSize);
    }

    public static ArrayList<ArrayList<Point>> findConnectedSets(GridGraph gridGraph) {
        //HashSet<Point> hashSet = new HashSet<>();
        boolean[] visited = new boolean[(gridGraph.sizeX+1)*(gridGraph.sizeY+1)];
        ArrayList<ArrayList<Point>> connectedSets = new ArrayList<>();
        
        for (int y=0; y<=gridGraph.sizeY; y++) {
            for (int x=0; x<=gridGraph.sizeX; x++) {
                if (visited[gridGraph.toOneDimIndex(x, y)]) continue;
                ArrayList<Point> list;
                list = ReachableNodes.computeReachable(gridGraph, x, y, visited);
                if (list.size() > 1) {
                    connectedSets.add(list);
                }
            }
        }
        // sort in descending order.
        Collections.sort(connectedSets, (set1, set2) -> set2.size() - set1.size());
        return connectedSets;
    }
    
    public static ArrayList<ArrayList<Point>> findConnectedSetsFast(GridGraph gridGraph) {
        //HashSet<Point> hashSet = new HashSet<>();
        boolean[] visited = new boolean[(gridGraph.sizeX+1)*(gridGraph.sizeY+1)];
        ArrayList<ArrayList<Point>> connectedSets = new ArrayList<>();
        
        ReachableNodesFast reachable = new ReachableNodesFast(gridGraph);
        for (int y=0; y<=gridGraph.sizeY; y++) {
            for (int x=0; x<=gridGraph.sizeX; x++) {
                if (visited[gridGraph.toOneDimIndex(x, y)]) continue;
                ArrayList<Point> list;
                list = reachable.computeReachable(visited, x, y);
                if (list.size() > 1) {
                    connectedSets.add(list);
                }
            }
        }
        // sort in descending order.
        Collections.sort(connectedSets, (set1, set2) -> set2.size() - set1.size());
        return connectedSets;
    }
    
    public static float computeAverageMaxSquare(GridGraph gridGraph) {
        long total = 0;
        long count = 0;
        
        int[][] maxRanges = gridGraph.computeMaxDownLeftRanges();
        for (int y=0; y<gridGraph.sizeY; ++y) {
            for (int x=0; x<gridGraph.sizeX; ++x) {
                if (gridGraph.isUnblockedCoordinate(x, y)) {
                    count += 1;
                    int maxSquare = detectMaxSquare(maxRanges, gridGraph.sizeY, x, y);
                    total += maxSquare;
                }
            }
        }
        if (count == 0) {
            return 0;
        }
        return (float)((double)total/count);
    }

    private static float computeAverageBlockedIslandSize(GridGraph gridGraph, boolean acceptBorderIslands) {

        boolean[] visited = new boolean[gridGraph.sizeX*gridGraph.sizeY];
        int nIslands = 0;
        int totalIslandSizes = 0;
        
        BlockedIslandSearch reachable = new BlockedIslandSearch(gridGraph);
        int sizeX = gridGraph.sizeX;
        int sizeY = gridGraph.sizeY;
        for (int y=0; y<sizeY; y++) {
            for (int x=0; x<sizeX; x++) {
                if (visited[y*sizeX + x]) continue;
                int islandSize = reachable.computeIslandSize(visited, x, y, acceptBorderIslands);
                
                if (islandSize == 0) continue;
                totalIslandSizes += islandSize;
                nIslands++;
            }
        }

        if (nIslands == 0) return 0;
        return (float)totalIslandSizes / nIslands;
    }

    /**
     * <pre>
     * returns the size of the max square at (x,y). can possibly return 0.
     * Method copied from AcceleratedAStar.
     * 1: XX
     *    XX
     * 
     * 2: XXX
     *    XXX
     *    XXX
     * </pre>
     */
    private static int detectMaxSquare(int[][] maxRanges, int sizeY, int x, int y) {
        // This is the newer, O(n) method.
        int lower = 0;
        int upper = Integer.MAX_VALUE;
        int newUpper;
        int i = x-y+sizeY;
        int j = Math.min(x, y);
        if (upper <= lower) return 0;

        while (true) {
            newUpper = checkUpperBoundNew(maxRanges, i,j,lower);
            if (newUpper < upper) upper = newUpper;
            if (upper <= lower) break;

            newUpper = checkUpperBoundNew(maxRanges, i,j,-1-lower);
            if (newUpper < upper) upper = newUpper;
            if (upper <= lower) break;
            
            lower++;
            if (upper <= lower) break;
        }
        return lower;
    }

    /**
     * <pre>
     *          _______  This function returns the upper bound detected by
     *         |   |k=1| the a leftward and downward search.
     *         |___|___| k is the number of steps moved in the up-right direction.
     *         |k=0|   | k = 0 the the square directly top-right of grid point (x,y).
     *  _______.___|___|
     * |   |-1 |(x,y)    
     * |___|___|  point of concern
     * |-2 |   |
     * |___|___|
     * </pre>
     */
    private static int checkUpperBoundNew(int[][] maxRange, int i, int j, int k) {
        return maxRange[i][j + k] - k;
    }
    
    public void addParameter(StringBuilder sb, String name, Object value){
        sb.append(name + ": " + value.toString()).append("\n");
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        addParameter(sb, "sizeX", sizeX);
        addParameter(sb, "sizeY", sizeY);
        addParameter(sb, "nTiles", sizeX*sizeY);
        addParameter(sb, "nBlocked", nBlocked);
        addParameter(sb, "blockDensity", blockDensity);
        addParameter(sb, "averageOpenSpaceSize", averageOpenSpaceSize);
        addParameter(sb, "averageBlockedIslandSize", averageBlockedIslandSize);
        addParameter(sb, "averageFloatingBlockedIslandSize", averageFloatingBlockedIslandSize);
        addParameter(sb, "largestRatioToSecond", largestRatioToSecond);
        addParameter(sb, "largestRatioToRemaining", largestRatioToRemaining);
        addParameter(sb, "hasSqueezableCorners", hasSqueezableCorners);
        addParameter(sb, "largestConnectedSetSize", largestConnectedSet.size());
        addParameter(sb, "numConnectedSets", connectedSets.size());
        addParameter(sb, "connectedSetSizes", computeConnectedSetSizeList());
        return sb.toString();
    }

    public static class Options {
        public boolean sizeX;
        public boolean sizeY;
        public boolean nBlocked;
        public boolean blockDensity;
        public boolean averageOpenSpaceSize;
        public boolean hasSqueezableCorners;
        public boolean connectedSets;
        public boolean largestConnectedSet;
        public boolean averageBlockedIslandSize;
        public boolean averageFloatingBlockedIslandSize;
        public boolean largestRatioToSecond;
        public boolean largestRatioToRemaining;
        
        public Options (String...options) {
            for (String option : options) {
                switch(option.toLowerCase()) {
                    case "sizex": sizeX=true;break;
                    case "sizey": sizeY=true;break;
                    case "nblocked": nBlocked=true;break;
                    case "blockdensity": blockDensity=true;break;
                    case "averageopenspacesize": averageOpenSpaceSize=true;break;
                    case "hassqueezablecorners": hasSqueezableCorners=true;break;
                    case "connectedsets": connectedSets=true;break;
                    case "largestconnectedset": largestConnectedSet=true;break;
                    case "averageBlockedIslandSize": averageBlockedIslandSize=true;break;
                    case "averageFloatingBlockedIslandSize": averageFloatingBlockedIslandSize=true;break;
                    case "largestRatioToSecond": largestRatioToSecond=true;break;
                    case "largestRatioToRemaining": largestRatioToRemaining=true;break;
                }
            }
        }
        
    }

    public ArrayList<Integer> computeConnectedSetSizeList() {
        ArrayList<Integer> list = new ArrayList<>();
        for (ArrayList<Point> connectedSet : connectedSets) {
            list.add(connectedSet.size());
        }
        return list;
    }
} public class TwoPoint {
    public final Point p1, p2;
    public TwoPoint (Point p1, Point p2) {
        this.p1 = p1; this.p2 = p2;
    }
    public TwoPoint (int x1, int y1, int x2, int y2) {
        this.p1 = new Point(x1,y1);
        this.p2 = new Point(x2,y2);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof TwoPoint)) return false;
        TwoPoint other = (TwoPoint)obj;
        if (p1.equals(other.p1) && p2.equals(other.p2)) {
            return true;
        }
        if (p1.equals(other.p2) && p2.equals(other.p1)) {
            return true;
        }
        return false;
    }

    @Override
    public int hashCode() {
        // Symmetric. Switching p1 and p2 should give the same hash code.
        final int prime = 31;
        int result = 1;
        int v1 = (p1 == null) ? 0 : p1.hashCode();
        int v2 = (p2 == null) ? 0 : p2.hashCode();
        int sum = v1 + v2;
        int diff = Math.abs(v1 - v2);
        
        result = prime * result + sum;
        result = prime * result + diff;
        return result;
    }
    
    @Override
    public String toString() {
        return p1.x + " " + p1.y + " " + p2.x + " " + p2.y;
    }
} public class AutomataGenerator {

    public static GridAndGoals generateUnseeded(int sizeX, int sizeY, int unblockedRatio, int iterations, float resolutionMultiplier, int cutoffOffset, boolean bordersAreBlocked, int sx, int sy, int ex, int ey) {
        GridGraph gridGraph = generate(false, 0, sizeX, sizeY, unblockedRatio, iterations, resolutionMultiplier, cutoffOffset, bordersAreBlocked);
        return new GridAndGoals(gridGraph, sx, sy, ex, ey);
    }

    public static GridAndGoals generateSeeded(long seed, int sizeX, int sizeY, int unblockedRatio, int iterations, float resolutionMultiplier, int cutoffOffset, boolean bordersAreBlocked, int sx, int sy, int ex, int ey) {
        GridGraph gridGraph = generate(true, seed, sizeX, sizeY, unblockedRatio, iterations, resolutionMultiplier, cutoffOffset, bordersAreBlocked);
        return new GridAndGoals(gridGraph, sx, sy, ex, ey);
    }
    
    public static GridGraph generateSeededGraphOnly(long seed, int sizeX, int sizeY, int unblockedRatio, int iterations, float resolutionMultiplier, int cutoffOffset, boolean bordersAreBlocked) {
        GridGraph gridGraph = generate(true, seed, sizeX, sizeY, unblockedRatio, iterations, resolutionMultiplier, cutoffOffset, bordersAreBlocked);
        return gridGraph;
    }

    public static GridAndGoals generateUnseededDynamicCutoff(int sizeX, int sizeY, float initialPercentBlocked, int iterations, float resolutionMultiplier, boolean bordersAreBlocked, int sx, int sy, int ex, int ey) {
        GridGraph gridGraph = generateDynamicCutoff(false, 0, sizeX, sizeY, initialPercentBlocked, iterations, resolutionMultiplier, bordersAreBlocked);
        return new GridAndGoals(gridGraph, sx, sy, ex, ey);
    }

    public static GridAndGoals generateSeededDynamicCutoff(long seed, int sizeX, int sizeY, float initialPercentBlocked, int iterations, float resolutionMultiplier, boolean bordersAreBlocked, int sx, int sy, int ex, int ey) {
        GridGraph gridGraph = generateDynamicCutoff(true, seed, sizeX, sizeY, initialPercentBlocked, iterations, resolutionMultiplier, bordersAreBlocked);
        return new GridAndGoals(gridGraph, sx, sy, ex, ey);
    }
    
    public static GridGraph generateSeededGraphOnlyDynamicCutoff(long seed, int sizeX, int sizeY, float initialPercentBlocked, int iterations, float resolutionMultiplier, boolean bordersAreBlocked) {
        GridGraph gridGraph = generateDynamicCutoff(true, seed, sizeX, sizeY, initialPercentBlocked, iterations, resolutionMultiplier, bordersAreBlocked);
        return gridGraph;
    }

    private static GridGraph generate(boolean seededRandom, long seed, int sizeX, int sizeY, int unblockedRatio, int iterations, float resolutionMultiplier, int cutoffOffset, boolean bordersAreBlocked) {
        GridGraph gridGraph = new GridGraph(sizeX, sizeY);

        Random rand = new Random();
        if (!seededRandom) {
            seed = rand.nextInt();
            System.out.println("Starting random with random seed = " + seed);
        } else {
            System.out.println("Starting random with predefined seed = " + seed);
        }
        rand = new Random(seed);
        
        generateRandomMap(rand, gridGraph, unblockedRatio, iterations, resolutionMultiplier, cutoffOffset, bordersAreBlocked);
        
        return gridGraph;
    }

    private static GridGraph generateDynamicCutoff(boolean seededRandom, long seed, int sizeX, int sizeY, float initialPercentBlocked, int iterations, float resolutionMultiplier, boolean bordersAreBlocked) {
        GridGraph gridGraph = new GridGraph(sizeX, sizeY);

        Random rand = new Random();
        if (!seededRandom) {
            seed = rand.nextInt();
            System.out.println("Starting random with random seed = " + seed);
        } else {
            System.out.println("Starting random with predefined seed = " + seed);
        }
        rand = new Random(seed);
        
        generateRandomMapDynamicCutoff(rand, gridGraph, initialPercentBlocked, iterations, resolutionMultiplier, bordersAreBlocked);
        
        return gridGraph;
    }
    
    
    private static void generateRandomMap(Random rand, GridGraph gridGraph, int frequency, int iterations, float resolutionMultiplier, int cutoffOffset, boolean bordersAreBlocked) {
        int sizeX = gridGraph.sizeX;
        int sizeY = gridGraph.sizeY;
        int resolution = Math.max((int)((sizeX+sizeY)*resolutionMultiplier/150), 1);
        int cutoff = (int)(0.8f*resolution*resolution + 1.75f*resolution + 0.8f) + cutoffOffset;

        System.out.println("Resolution " + resolution + ", Cutoff " + cutoff);
        
        boolean[][] grid = new boolean[sizeY][];
        // Count: used for DP computation of number of blocked neighbours.
        //  Note: count includes the current tile as well. We subtract it when we compare with cutoff.
        int[][] count = new int[sizeY][];
        for (int y=0;y<sizeY;++y) {
            grid[y] = new boolean[sizeX];
            count[y] = new int[sizeX];
            for (int x=0;x<sizeX;++x) {
                grid[y][x] = rand.nextInt()%frequency == 0;
            }
        }
        
        for (int itr=0;itr<iterations;++itr) {
            if (bordersAreBlocked) runAutomataIterationBlockedBorders(sizeX, sizeY, resolution, grid, count);
            else runAutomataIterationUnblockedBorders(sizeX, sizeY, resolution, grid, count);
            
            for (int y=0;y<sizeY;++y) {
                for (int x=0;x<sizeX;++x) {
                    grid[y][x] = (count[y][x] - (grid[y][x] ? 1 : 0) >= cutoff);
                }
            }
        }
        
        for (int y=0;y<sizeY;++y) {
            for (int x=0;x<sizeX;++x) {
                gridGraph.setBlocked(x, y, grid[y][x]);
            }
        }
    }


    private static void generateRandomMapDynamicCutoff(Random rand, GridGraph gridGraph, float percentBlocked, int iterations, float resolutionMultiplier, boolean bordersAreBlocked) {
        int sizeX = gridGraph.sizeX;
        int sizeY = gridGraph.sizeY;
        int resolution = Math.max((int)((sizeX+sizeY)*resolutionMultiplier/150), 1);

        boolean[][] grid = new boolean[sizeY][];
        // Count: used for DP computation of number of blocked neighbours.
        //  Note: count includes the current tile as well. We subtract it when we compare with cutoff.
        int[][] count = new int[sizeY][];
        for (int y=0;y<sizeY;++y) {
            grid[y] = new boolean[sizeX];
            count[y] = new int[sizeX];
            for (int x=0;x<sizeX;++x) {
                grid[y][x] = rand.nextFloat() < percentBlocked;
            }
        }
        
        int maxCount = (resolution*2+1);
        maxCount = maxCount*maxCount - 1;
        
        for (int itr=0;itr<iterations;++itr) {
            if (bordersAreBlocked) runAutomataIterationBlockedBorders(sizeX, sizeY, resolution, grid, count);
            else runAutomataIterationUnblockedBorders(sizeX, sizeY, resolution, grid, count);
            
            // Adjust counts to exclude the center.
            for (int y=0;y<sizeY;++y) {
                for (int x=0;x<sizeX;++x) {
                    count[y][x] = (count[y][x] - (grid[y][x] ? 1 : 0));
                }
            }
            
            // Compute mean.
            long totalCount = 0;
            for (int y=0;y<sizeY;++y) {
                for (int x=0;x<sizeX;++x) {
                    totalCount += count[y][x];
                }
            }
            float mean = (float)totalCount / (sizeX*sizeY);
            
            // Compute approximately the value at the pth percentile. (where p = percentBlocked)
            int nBins = (int)Math.sqrt(sizeX*sizeY);
            
            // bin 0: <= low
            // bin n+1: >= low+range
            // bin i: low + d*(i-1) < x < low + d*(i)
            int[] bins = new int[nBins+2];
            float[] binAverage = new float[nBins+2];
            
            float low = mean*0.5f;
            float range = (mean + maxCount)/2 - low;
            float d = range/nBins;
            for (int y=0;y<sizeY;++y) {
                for (int x=0;x<sizeX;++x) {
                    int bin = (int)((count[y][x] - low)*nBins / range) + 1;
                    bin = Math.max(Math.min(bin, nBins+1), 0); // Clamp bin to [0,n+1]
                    binAverage[bin] = (binAverage[bin]*bins[bin] + count[y][x]) / (bins[bin]+1);
                    bins[bin]++;
                }
            }
            
            // cutoff = value at pth percentile (similar to median)
            // using the value at the pth percentile allows us to maintain the same percentageBlocked each iteration.
            int remainingCumSum = (int)(sizeX*sizeY * (1-percentBlocked));
            float cutoff = -1;
            for (int i=0;i<bins.length;++i) {
                remainingCumSum -= bins[i];
                if (remainingCumSum < 0) {
                    cutoff = binAverage[i];
                    break;
                }
            }
            
            for (int y=0;y<sizeY;++y) {
                for (int x=0;x<sizeX;++x) {
                    grid[y][x] = count[y][x] >= cutoff;
                }
            }
        }
        
        for (int y=0;y<sizeY;++y) {
            for (int x=0;x<sizeX;++x) {
                gridGraph.setBlocked(x, y, grid[y][x]);
            }
        }
    }
    
    protected static void runAutomataIterationUnblockedBorders(int sizeX, int sizeY, int resolution, boolean[][] grid, int[][] count) {
        /*
         * Note: for brevity, the following code:
         * nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || grid[py][px]) ? 1 : 0;
         * 
         * Is a shortened version of:
         * if (px < 0 || py < 0 || px >= sizeX || py >= sizeY) {
         *     nBlocked++;
         * } else {
         *     nBlocked += grid[py][px] ? 1 : 0;
         * }
         */
        
        { // Base case: y = 0
            int y = 0;
            { // Base case: x = 0
                int x = 0;
                int nBlocked = 0;
                for (int i=-resolution;i<=resolution;++i) {
                    for (int j=-resolution;j<=resolution;++j) {
                        int px = x + i;
                        int py = y + j;
                        nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || !grid[py][px]) ? 0 : 1;
                    }
                }
                
                count[y][x] = nBlocked;
            }

            // y = 0, x > 0
            for (int x=1;x<sizeX;++x) {
                int nBlocked = count[y][x-1];

                { // subtract for (x-1-r,?)
                    int px = x - resolution - 1;
                    for (int j=-resolution;j<=resolution;++j) {
                        int py = y + j;
                        nBlocked -= (px < 0 || py < 0 || px >= sizeX || py >= sizeY || !grid[py][px]) ? 0 : 1;
                    }
                }
                
                { // add for (x+r,?)
                    int px = x + resolution;
                    for (int j=-resolution;j<=resolution;++j) {
                        int py = y + j;
                        nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || !grid[py][px]) ? 0 : 1;
                    }
                }
                
                count[y][x] = nBlocked;
            }
        }

        // y > 0
        for (int y=1;y<sizeY;++y) {
            // y > 0, x = 0
            {
                int x = 0;
                int nBlocked = count[y-1][x];

                { // subtract for (?,y-1-r)
                    int py = y - resolution - 1;
                    for (int i=-resolution;i<=resolution;++i) {
                        int px = x + i;
                        nBlocked -= (px < 0 || py < 0 || px >= sizeX || py >= sizeY || !grid[py][px]) ? 0 : 1;
                    }
                }
                
                { // add for (?,y+r)
                    int py = y + resolution;
                    for (int i=-resolution;i<=resolution;++i) {
                        int px = x + i;
                        nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || !grid[py][px]) ? 0 : 1;
                    }
                }

                count[y][x] = nBlocked;
            }
            
            // y > 0, x > 0
            for (int x=1;x<sizeX;++x) {
                int nBlocked = count[y-1][x] + count[y][x-1] - count[y-1][x-1];

                { // add (x-1-r,y-1-r)
                    int px = x - resolution - 1;
                    int py = y - resolution - 1;
                    nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || !grid[py][px]) ? 0 : 1;
                }
                { // add (x+r,y+r)
                    int px = x + resolution;
                    int py = y + resolution;
                    nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || !grid[py][px]) ? 0 : 1;
                }
                { // subtract (x-1-r,y+r)
                    int px = x - resolution - 1;
                    int py = y + resolution;
                    nBlocked -= (px < 0 || py < 0 || px >= sizeX || py >= sizeY || !grid[py][px]) ? 0 : 1;
                }
                { // subtract (x+r,y-1-r)
                    int px = x + resolution;
                    int py = y - resolution - 1;
                    nBlocked -= (px < 0 || py < 0 || px >= sizeX || py >= sizeY || !grid[py][px]) ? 0 : 1;
                }
                
                count[y][x] = nBlocked;
            }
        }
    }

    private static void runAutomataIterationBlockedBorders(int sizeX, int sizeY, int resolution, boolean[][] grid, int[][] count) {
        /*
         * Note: for brevity, the following code:
         * nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || grid[py][px]) ? 1 : 0;
         * 
         * Is a shortened version of:
         * if (px < 0 || py < 0 || px >= sizeX || py >= sizeY) {
         *     nBlocked++;
         * } else {
         *     nBlocked += grid[py][px] ? 1 : 0;
         * }
         */
        
        { // Base case: y = 0
            int y = 0;
            { // Base case: x = 0
                int x = 0;
                int nBlocked = 0;
                for (int i=-resolution;i<=resolution;++i) {
                    for (int j=-resolution;j<=resolution;++j) {
                        int px = x + i;
                        int py = y + j;
                        nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || grid[py][px]) ? 1 : 0;
                    }
                }
                
                count[y][x] = nBlocked;
            }

            // y = 0, x > 0
            for (int x=1;x<sizeX;++x) {
                int nBlocked = count[y][x-1];

                { // subtract for (x-1-r,?)
                    int px = x - resolution - 1;
                    for (int j=-resolution;j<=resolution;++j) {
                        int py = y + j;
                        nBlocked -= (px < 0 || py < 0 || px >= sizeX || py >= sizeY || grid[py][px]) ? 1 : 0;
                    }
                }
                
                { // add for (x+r,?)
                    int px = x + resolution;
                    for (int j=-resolution;j<=resolution;++j) {
                        int py = y + j;
                        nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || grid[py][px]) ? 1 : 0;
                    }
                }
                
                count[y][x] = nBlocked;
            }
        }

        // y > 0
        for (int y=1;y<sizeY;++y) {
            // y > 0, x = 0
            {
                int x = 0;
                int nBlocked = count[y-1][x];

                { // subtract for (?,y-1-r)
                    int py = y - resolution - 1;
                    for (int i=-resolution;i<=resolution;++i) {
                        int px = x + i;
                        nBlocked -= (px < 0 || py < 0 || px >= sizeX || py >= sizeY || grid[py][px]) ? 1 : 0;
                    }
                }
                
                { // add for (?,y+r)
                    int py = y + resolution;
                    for (int i=-resolution;i<=resolution;++i) {
                        int px = x + i;
                        nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || grid[py][px]) ? 1 : 0;
                    }
                }

                count[y][x] = nBlocked;
            }
            
            // y > 0, x > 0
            for (int x=1;x<sizeX;++x) {
                int nBlocked = count[y-1][x] + count[y][x-1] - count[y-1][x-1];

                { // add (x-1-r,y-1-r)
                    int px = x - resolution - 1;
                    int py = y - resolution - 1;
                    nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || grid[py][px]) ? 1 : 0;
                }
                { // add (x+r,y+r)
                    int px = x + resolution;
                    int py = y + resolution;
                    nBlocked += (px < 0 || py < 0 || px >= sizeX || py >= sizeY || grid[py][px]) ? 1 : 0;
                }
                { // subtract (x-1-r,y+r)
                    int px = x - resolution - 1;
                    int py = y + resolution;
                    nBlocked -= (px < 0 || py < 0 || px >= sizeX || py >= sizeY || grid[py][px]) ? 1 : 0;
                }
                { // subtract (x+r,y-1-r)
                    int px = x + resolution;
                    int py = y - resolution - 1;
                    nBlocked -= (px < 0 || py < 0 || px >= sizeX || py >= sizeY || grid[py][px]) ? 1 : 0;
                }
                
                count[y][x] = nBlocked;
            }
        }
    }

    /**
     * Generates a truly random map for the gridGraph.
     * No longer used as this does not generate very good or realistic grids.
     */
    private static void generateRandomMap_slow(Random rand, GridGraph gridGraph, int frequency, int iterations, int cutoffOffset) {
        int sizeX = gridGraph.sizeX;
        int sizeY = gridGraph.sizeY;
        int resolution = Math.max((sizeX+sizeY)/150, 1);
        int cutoff = (int)(0.8f*resolution*resolution + 1.75f*resolution + 0.8f) + cutoffOffset;

        System.out.println("Resolution " + resolution + ", Cutoff " + cutoff);
        
        boolean[][] grid = new boolean[sizeY][];
        boolean[][] grid2 = new boolean[sizeY][];
        for (int y=0;y<sizeY;++y) {
            grid[y] = new boolean[sizeX];
            grid2[y] = new boolean[sizeX];
            for (int x=0;x<sizeX;++x) {
                grid[y][x] = rand.nextInt()%frequency == 0;
            }
        }
        
        for (int itr=0;itr<iterations;++itr) {
            
            for (int y=0;y<sizeY;++y) {
                for (int x=0;x<sizeX;++x) {
                    int nBlocked = 0;
                    for (int i=-resolution;i<=resolution;++i) {
                        for (int j=-resolution;j<=resolution;++j) {
                            if (i == 0 && j == 0) continue;
                            int px = x + i;
                            int py = y + j;
                            if (px < 0 || py < 0 || px >= sizeX || py >= sizeY) {
                                nBlocked++;
                            } else {
                                nBlocked += grid[py][px] ? 1 : 0;
                            }
                        }
                    }
                    grid2[y][x] = nBlocked >= cutoff;
                }
            }
            
            boolean[][] temp = grid;
            grid = grid2;
            grid2 = temp;
        }
        
        for (int y=0;y<sizeY;++y) {
            for (int x=0;x<sizeX;++x) {
                gridGraph.setBlocked(x, y, grid[y][x]);
            }
        }
    }
    
    
} public class MazeMapGenerator {

    /**
     * connectednessRatio is between 0 and 1.
     *   0: n-1 edges
     *   1: max possible number of edges.
     */
    public static GridAndGoals generateUnseeded(int sizeX, int sizeY,
            int corridorWidth, float connectednessRatio, int sx, int sy, int ex, int ey) {
        GridGraph gridGraph = generate(false, 0, sizeX, sizeY, corridorWidth, connectednessRatio);
        return new GridAndGoals(gridGraph, sx, sy, ex, ey);
    }

    public static GridGraph generateUnseededGraphOnly(int sizeX, int sizeY,
            int corridorWidth, float connectednessRatio) {
        GridGraph gridGraph = generate(false, 0, sizeX, sizeY, corridorWidth, connectednessRatio);
        return gridGraph;
    }

    public static GridAndGoals generateSeeded(long seed, int sizeX, int sizeY,
            int corridorWidth, float connectednessRatio, int sx, int sy, int ex, int ey) {
        GridGraph gridGraph = generate(true, seed, sizeX, sizeY, corridorWidth, connectednessRatio);
        return new GridAndGoals(gridGraph, sx, sy, ex, ey);
    }

    public static GridGraph generateSeededGraphOnly(long seed, int sizeX, int sizeY,
            int corridorWidth, float connectednessRatio) {
        GridGraph gridGraph = generate(true, seed, sizeX, sizeY, corridorWidth, connectednessRatio);
        return gridGraph;
    }

    private static GridGraph generate(boolean seededRandom, long seed,
            int sizeX, int sizeY, int corridorWidth, float connectednessRatio) {
        GridGraph gridGraph = new GridGraph(sizeX, sizeY);

        Random rand = new Random();
        if (!seededRandom) {
            seed = rand.nextInt();
            System.out.println("Maze Map with random seed = " + seed);
        } else {
            System.out.println("Maze Map with predefined seed = " + seed);
        }
        rand = new Random(seed);

        MazeMapGenerator generator = new MazeMapGenerator(rand, sizeX, sizeY, corridorWidth, connectednessRatio);
        generator.writeToGridGraph(gridGraph);
        return gridGraph;
    }

    /* Diagram of how we index vertices, horizontal edges and vertical edges
     * used in the algorithm below.
     *
     *(0,0) ___________________ (2,0)
     *     |  [0,0]  |  [1,0]  |
     *     |         |         |
     *     |{0,0}    |{1,0}    |{2,0}
     *     |         |         |
     *(0,1)|_________|_________|(2,1)
     *     |  [0,1]  |  [1,1]  |
     *     |         |         |
     *     |{0,1}    |{1,1}    |{1,2}
     *     |         |         |
     *     |_________|_________|
     *(0,2)   [0,2]     [1,2]   (2,2)
     */

    private final int nNodesX;
    private final int nNodesY;
    private final int nVertEdgesX;
    private final int nVertEdgesY;
    private final int nVertEdges;
    private final int nHoriEdgesX;
    private final int nHoriEdgesY;

    private final int[] nodeCurrentSet;
    private final ArrayList<ArrayList<Integer>> sets;
    private final int[] edges;

    private final int nAdditionalEdges;

    private final int corridorWidth;
    private final Random rand;

    private int firstEdge = -1;

    private MazeMapGenerator(Random rand, int sizeX, int sizeY, int corridorWidth, float connectednessRatio) {
        this.rand = rand;
        this.corridorWidth = corridorWidth;

        nNodesX = (sizeX/corridorWidth - 1)/2;
        nNodesY = (sizeY/corridorWidth - 1)/2;

        nVertEdgesX = nNodesX;
        nVertEdgesY = nNodesY-1;
        nHoriEdgesX = nNodesX-1;
        nHoriEdgesY = nNodesY;

        nVertEdges = nVertEdgesX*nVertEdgesY;

        nodeCurrentSet = new int[nNodesX*nNodesY];
        sets = new ArrayList<ArrayList<Integer>>();
        edges = new int[nVertEdgesX*nVertEdgesY + nHoriEdgesX*nHoriEdgesY];

        for (int i=0; i<nodeCurrentSet.length; ++i) {
            nodeCurrentSet[i] = i;
            sets.add(new ArrayList<>());
            sets.get(i).add(i);
        }

        for (int i=0; i<edges.length; ++i) {
            edges[i] = i;
        }

        int minEdges = nNodesX*nNodesY - 1;
        int maxEdges = edges.length;

        nAdditionalEdges = (int)(connectednessRatio*(maxEdges-minEdges));

        generateRandomMap();
    }

    private final void generateRandomMap() {
        // First we pick n-1 edges to form a spanning tree.
        // Wont pick: edges that link two nodes from the same component.
        // Picked: edges in the spanning tree.
        int nMinusOne = nNodesX*nNodesY - 1;
        int start = 0;
        int end = edges.length;

        /*
         *           start                  end
         *  ___________|_____________________|________
         * |___________|_____________________|________|
         *  '----.----' '---------.---------' '---.---'
         *   Won't pick      Unprocessed        Picked
         */

        // STEP 1: Pick n-1 edges to form a spanning tree.
        int[] endPoints = new int[4];
        while (edges.length - end < nMinusOne) {
            int index = rand.nextInt(end-start) + start;
            int edge = edges[index];

            getEndpoints(edge, endPoints);
            int v1 = indexOf(endPoints[0], endPoints[1]);
            int v2 = indexOf(endPoints[2], endPoints[3]);

            if (nodeCurrentSet[v1] == nodeCurrentSet[v2]) {
                // Same set. Don't pick edge.
                swapEdge(index, start);
                ++start;
            } else {
                // Different set. Merge sets and pick edge.
                swapEdge(index, end-1);
                --end;
                mergeSets(v1, v2);
            }
        }

        // STEP 2: Pick random additional edges.
        for (int i=0; i<nAdditionalEdges; ++i) {
            // We can pick any edge before end. (it doesn't have to be unprocessed)
            int index = rand.nextInt(end);

            swapEdge(index, end-1);
            --end;
        }

        firstEdge = end;
    }

    private final void swapEdge(int e1, int e2) {
        int temp = edges[e1];
        edges[e1] = edges[e2];
        edges[e2] = temp;
    }

    private final void mergeSets(int v1, int v2) {
        if (sets.get(nodeCurrentSet[v1]).size() < sets.get(nodeCurrentSet[v2]).size()) {
            mergeSets(v2, v1);
            return;
        }

        // wtf lol. I wrote c++ instead of java. fix this!

        // Assume v2 is smaller than v1.
        // We merge v2 into v1.
        int v1SetIndex = nodeCurrentSet[v1];
        int v2SetIndex = nodeCurrentSet[v2];
        ArrayList<Integer> v1Set = sets.get(v1SetIndex);
        ArrayList<Integer> v2Set = sets.get(v2SetIndex);

        for (int vertex : v2Set) {
            nodeCurrentSet[vertex] = v1SetIndex;
        }

        // add v2Set to v1Set, clear v2Set.
        v1Set.addAll(v2Set);
        v2Set.clear();
    }

    private final int indexOf(int px, int py) {
        return py*nNodesX + px;
    }

    private final void getEndpoints(int index, int[] return_coords) {
        if (index < nVertEdges) {
            // Vertical edge
            int indexX = index%nVertEdgesX;
            int indexY = index/nVertEdgesX;

            // Example: Edge {1,0} bridges points (1,0) and (1,1)
            return_coords[0] = indexX;
            return_coords[1] = indexY;
            return_coords[2] = indexX;
            return_coords[3] = indexY+1;
        } else {
            // Horizontal edge
            index -= nVertEdges;
            int indexX = index%nHoriEdgesX;
            int indexY = index/nHoriEdgesX;

            // Example: Edge [0,1] bridges points (0,1) and (1,1)
            return_coords[0] = indexX;
            return_coords[1] = indexY;
            return_coords[2] = indexX+1;
            return_coords[3] = indexY;
        }
    }

    private final void getEdgeTile(int index, int[] return_edgeTile) {
        if (index < nVertEdges) {
            // Vertical edge
            int indexX = index%nVertEdgesX;
            int indexY = index/nVertEdgesX;

            // Example: Edge {1,0} bridges points (1,0) and (1,1)
            // point (x,y) is at tile (2*x+1, 2*y+1)
            return_edgeTile[0] = 2*indexX+1;
            return_edgeTile[1] = 2*indexY+2;
        } else {
            // Horizontal edge
            index -= nVertEdges;
            int indexX = index%nHoriEdgesX;
            int indexY = index/nHoriEdgesX;

            // Example: Edge [0,1] bridges points (0,1) and (1,1)
            // point (x,y) is at tile (2*x+1, 2*y+1)
            return_edgeTile[0] = 2*indexX+2;
            return_edgeTile[1] = 2*indexY+1;
        }
    }

    private final void writeToGridGraph(GridGraph grid) {
        for (int y=0; y<grid.sizeY; ++y) {
            for (int x=0; x<grid.sizeX; ++x) {
                grid.setBlocked(x, y, true);
            }
        }

        for (int y=0; y<nNodesY; ++y) {
            for (int x=0; x<nNodesX; ++x) {
                int baseX = (2*x+1)*corridorWidth;
                int baseY = (2*y+1)*corridorWidth;
                int endX = baseX + corridorWidth;
                int endY = baseY + corridorWidth;
                for (int py=baseY; py<endY; ++py) {
                    for (int px=baseX; px<endX; ++px) {
                        grid.setBlocked(px, py, false);
                    }
                }
            }
        }

        int[] edgeTile = new int[2];
        for (int i=firstEdge; i<edges.length; ++i) {
            getEdgeTile(edges[i], edgeTile);

            int baseX = edgeTile[0]*corridorWidth;
            int baseY = edgeTile[1]*corridorWidth;
            int endX = baseX + corridorWidth;
            int endY = baseY + corridorWidth;
            for (int py=baseY; py<endY; ++py) {
                for (int px=baseX; px<endX; ++px) {
                    grid.setBlocked(px, py, false);
                }
            }
        }
    }
} public class TiledMapGenerator {
    
    public static GridAndGoals mergeMapsDefault(GridGraph[] gridGraphs, int nCols, int nRows) {
        return new GridAndGoals(mergeMaps(gridGraphs, nCols, nRows), 0, 0, 0, 0);
    }
    
    
    public static GridGraph mergeMaps(GridGraph[] gridGraphs, int nCols, int nRows) {
        // Do checks first.
        if (gridGraphs.length != nCols*nRows) {
            throw new UnsupportedOperationException("Wrong number of maps to tile! Expected: " + 
                                                    (nCols*nRows) + ". Actual: " + gridGraphs.length);
        }
        
        int graphSizeX = gridGraphs[0].sizeX;
        int graphSizeY = gridGraphs[0].sizeY;
        
        for (int i=0;i<gridGraphs.length;++i) {
            if (gridGraphs[i].sizeX != graphSizeX || gridGraphs[i].sizeY != graphSizeY) {
                throw new UnsupportedOperationException("GridGraphs are not all of the same size: " + i);
            }       
        }

        int sizeX = graphSizeX * nCols;
        int sizeY = graphSizeY * nRows;
        
        boolean[][] grid = new boolean[sizeY][];
        for (int y=0;y<sizeY;++y) grid[y] = new boolean[sizeX];
        
        for (int r=0;r<nRows;++r) {
            for (int c=0;c<nCols;++c) {
                GridGraph gridGraph = gridGraphs[r*nCols + c];
                int baseX = c*graphSizeX;
                int baseY = r*graphSizeY;
                
                for (int y=0;y<graphSizeY;++y) {
                    for (int x=0;x<graphSizeX;++x) {
                        grid[y+baseY][x+baseX] = gridGraph.isBlocked(x, y);
                    }
                }
            }
        }
        
        joinMaps(gridGraphs, grid, graphSizeX, graphSizeY, nCols, nRows);
        
        
        GridGraph newGridGraph = new GridGraph(sizeX, sizeY);
        for (int y=0;y<sizeY;++y) {
            for (int x=0;x<sizeX;++x) {
                newGridGraph.setBlocked(x, y, grid[y][x]);
            }
        }
        return newGridGraph;
    }


    private static void joinMaps(GridGraph[] gridGraphs, boolean[][] grid, int graphSizeX, int graphSizeY, int nCols, int nRows) {
        int[][] yMinyMaxxMinxMax = new int[gridGraphs.length][];
        int midX = graphSizeX/2;
        int midY = graphSizeY/2;
        
        for (int i=0;i<gridGraphs.length;++i) {
            ArrayList<ArrayList<Point>> connectedSets = MazeAnalysis.findConnectedSetsFast(gridGraphs[i]);
            ArrayList<Point> largestConnectedSet = MazeAnalysis.getLargestSet(connectedSets);
            int yMin = graphSizeY;
            int yMax = -1;
            int xMin = graphSizeX;
            int xMax = -1;
            
            for (Point point : largestConnectedSet) {
                if (point.x == midX) {
                    if (point.y < yMin) yMin = point.y;
                    if (point.y > yMax) yMax = point.y;
                }
                if (point.y == midY) {
                    if (point.x < xMin) xMin = point.x;
                    if (point.x > xMax) xMax = point.x;
                }
            }
            yMinyMaxxMinxMax[i] = new int[]{yMin,yMax,xMin,xMax};
        }
        
        for (int r=0;r<nRows;++r) {
            for (int c=0;c<nCols;++c) {
                int g2 = r*nCols + c; 
                if (r > 0) {
                    // Connect vertical bridges
                    int bridgeX = c*graphSizeX + midX;
                    
                    int g1 = g2 - nCols;
                    int yStart = yMinyMaxxMinxMax[g1][1] + (r-1)*graphSizeY;
                    int yEnd = yMinyMaxxMinxMax[g2][0] + r*graphSizeY;
                    
                    for (int i=yStart;i<=yEnd;++i) {
                        grid[i][bridgeX] = false;
                    }
                }
                

                if (c > 0) {
                    // Connect horizontal bridges
                    int bridgeY = r*graphSizeY + midY;
                    
                    int g1 = g2 - 1;
                    int xStart = yMinyMaxxMinxMax[g1][3] + (c-1)*graphSizeX;
                    int xEnd = yMinyMaxxMinxMax[g2][2] + c*graphSizeX;

                    for (int i=xStart;i<=xEnd;++i) {
                        grid[bridgeY][i] = false;
                    }
                }
            }
        }
    }
} public class UpscaledMapGenerator {
    
    public static GridAndGoals upscale(GridAndGoals gridAndGoals, int multiplier, boolean smooth) {
        StartGoalPoints sgp = gridAndGoals.startGoalPoints;
        GridGraph newGridGraph = upscale(gridAndGoals.gridGraph, multiplier, smooth);
        
        return new GridAndGoals(newGridGraph, sgp.sx*multiplier, sgp.sy*multiplier, sgp.ex*multiplier, sgp.ey*multiplier);
    }
    
    public static GridGraph upscale(GridGraph graph, int multiplier, boolean smooth) {
        int sizeX = graph.sizeX * multiplier;
        int sizeY = graph.sizeY * multiplier;
        
        boolean[][] grid = new boolean[sizeY][];
        for (int y=0;y<sizeY;++y) grid[y] = new boolean[sizeX];
        
        for (int y=0;y<sizeY;y+=multiplier) {
            for (int x=0;x<sizeX;x+=multiplier) {
                boolean blocked = graph.isBlocked(x/multiplier, y/multiplier);
                for (int i=0;i<multiplier;++i) {
                    for (int j=0;j<multiplier;++j) {
                        grid[y+i][x+j] = blocked;
                    }
                }
            }
        }
        
        if (smooth) {
            smoothUpscaledMap(multiplier, sizeX, sizeY, grid);
        }
        
        GridGraph newGraph = new GridGraph(sizeX, sizeY);
        for (int y=0;y<sizeY;++y) {
            for (int x=0;x<sizeX;++x) {
                newGraph.setBlocked(x,y,grid[y][x]);
            }
        }
        return newGraph;
    }

    private static void smoothUpscaledMap(int multiplier, int sizeX, int sizeY, boolean[][] grid) {
        int resolution = multiplier-1;
        int width = resolution*2+1;
        int cutoff = width*width/2;
        
        int[][] count = new int[sizeY][];
        for (int y=0;y<sizeY;++y) count[y] = new int[sizeX];
        
        // Compute counts. For now we don't include off-edge tiles in the count.
        AutomataGenerator.runAutomataIterationUnblockedBorders(sizeX, sizeY, resolution, grid, count);
        
        for (int y=0;y<sizeY;++y) {
            for (int x=0;x<sizeX;++x) {
                // Idea: For tiles that are off the edge of the map, we count them as blocked/unblocked tiles depending
                //       on whether the current tile is blocked. (bias towards not changing)
                
                // If grid[y][x] is unblocked, off-map tiles are counted as 0.
                int bias = 0;
                
                if (grid[y][x]) {
                    // If grid[y][x] is blocked, we count the number of off-map tiles that count[y][x] should have included.
                    int blankUp = Math.max(0, 0-y+resolution);
                    int blankLeft = Math.max(0, 0-x+resolution);
                    int blankDown = Math.max(0, y-sizeY+resolution);
                    int blankRight = Math.max(0, x-sizeX+resolution);
                    bias = width*width - (width-blankUp-blankDown)*(width-blankLeft-blankRight);
                }
                
                grid[y][x] = count[y][x] + bias > cutoff;
            }
        }
    }
} public class StartEndPointData {
    public final Point start;
    public final Point end;
    public final double shortestPath;
    
    public StartEndPointData(Point start, Point end, double shortestPath) {
        this.start = start;
        this.end = end;
        this.shortestPath = shortestPath;
    }
    
    public TwoPoint toTwoPoint() {
        return new TwoPoint(start, end);
    }
} public class Stringifier {

    public static String makeProblemName(int sx, int sy, int ex, int ey) {
        return sx + "-" + sy + "_" + ex + "-" + ey;
    }

    public static String defaultToString(int seed, int sizeX, int sizeY, int unblockedRatio) {
        StringBuilder sb = new StringBuilder("def_");
        sb.append(intToStr(seed)).append("_");
        sb.append(intToStr(sizeX)).append("_");
        sb.append(intToStr(sizeY)).append("_");
        sb.append(intToStr(unblockedRatio));
        return sb.toString();
    }
    
    public static String automataToString(long seed, int sizeX, int sizeY, int unblockedRatio, int iterations, float resolutionMultiplier, int cutoffOffset, boolean bordersAreBlocked) {
        StringBuilder sb = new StringBuilder("gen_");
        sb.append(sizeX).append("x");
        sb.append(sizeY).append("_");
        sb.append(unblockedRatio).append("_");
        sb.append(iterations).append("_");
        sb.append((int)(resolutionMultiplier*1000)).append("_");
        sb.append(cutoffOffset).append("_");
        sb.append(bordersAreBlocked ? "T" : "F").append("_");
        sb.append(longToStr(seed));
        return sb.toString();
    }
    
    public static String automataDCToString(long seed, int sizeX, int sizeY, float percentBlocked, int iterations, float resolutionMultiplier, boolean bordersAreBlocked) {
        StringBuilder sb = new StringBuilder("autodc_");
        sb.append(sizeX).append("x");
        sb.append(sizeY).append("_");
        sb.append((int)(percentBlocked*1000)).append("_");
        sb.append(iterations).append("_");
        sb.append((int)(resolutionMultiplier*1000)).append("_");
        sb.append(bordersAreBlocked ? "T" : "F").append("_");
        sb.append(longToStr(seed));
        return sb.toString();
    }
    
    public static String mazeMapToString(long seed, int sizeX, int sizeY, int corridorWidth, float connectednessRatio) {
        StringBuilder sb = new StringBuilder("maze_");
        sb.append(sizeX).append("x");
        sb.append(sizeY).append("_");
        sb.append(corridorWidth).append("_");
        sb.append(floatToOneDigitStandardFormStr(connectednessRatio)).append("_");
        sb.append(longToStr(seed));
        return sb.toString();
    }

    public static String defaultToStringReadable(int seed, int sizeX, int sizeY, int unblockedRatio) {
        StringBuilder sb = new StringBuilder("gen_");
        sb.append(sizeX).append("x");
        sb.append(sizeY).append("_");
        sb.append(unblockedRatio).append("_");
        sb.append(intToStr(seed));
        return sb.toString();
    }
    
    public static int[] defaultToParameters(String input) {
        String[] args = input.split("_");
        if (!args[0].equals("def"))
            throw new UnsupportedOperationException("Invalid string: " + input);
        int[] pars = new int[args.length-1];
        for (int i=0; i<pars.length; i++) {
            pars[i] = strToInt(args[i+1]);
        }
        return pars;
    }

    public static String intToStr(int i) {
        StringBuilder sb = new StringBuilder("i");
        while (i != 0) {
            sb.append(digitToChar((i%32+32)%32));
            i = i>>>5;
        }
        return sb.toString();
    }
    
    public static String longToStr(long i) {
        StringBuilder sb = new StringBuilder("i");
        while (i != 0) {
            sb.append(digitToChar((int)(i%32+32)%32));
            i = i>>>5;
        }
        return sb.toString();
    }

    public static String floatToOneDigitStandardFormStr(float f) {
        float EPS = 0.0000001f;

        if (f == 0) return "0E0";
        int digits = 0;
    
        while (Math.abs(f) > 1+EPS) {
            f /= 10;
            digits++;
        }
        while (Math.abs(f) < 1-EPS) {
            f *= 10;
            digits--;
        }
        return (int)(f > 0 ? f+EPS : f-EPS) + "E" + digits;
    }
    
    public static int strToInt(String s) {
        int num = 0;
        for (int i=1; i<s.length(); i++) {
            num += charToDigit(s.charAt(i)) << (5*(i-1));
        }
        return num;
    }
    
    public static char digitToChar(int d) {
        if (d < 0) {
            throw new UnsupportedOperationException("Exceeds range: " + d);
        } else if (d < 26) {
            return (char)('A' + d);
        } else if (d < 36) {
            return (char)('0' + (d-26));
        } else {
            throw new UnsupportedOperationException("Exceeds range: " + d);
        }
    }
    
    public static int charToDigit(char c) {
        if (c >= 'A' && c <= 'Z') {
            return (int)(c-'A');
        } else if (c >= '0' && c <= '9') {
            return (int)(c-'0')+26;
        } else {
            throw new UnsupportedOperationException("Exceeds range: " + c);
        }
        
    }
    
} public class Utility {

    /**
     * Compute the length of a given path. (Using euclidean distance)
     */
    public static double computePathLength(GridGraph gridGraph, int[][] path) {
        path = removeDuplicatesInPath(path);
        double pathLength = 0;
        for (int i=0; i<path.length-1; i++) {
            pathLength += gridGraph.distance_double(path[i][0], path[i][1],
                            path[i+1][0], path[i+1][1]);
        }
        return pathLength;
    }
    
    public static double computeOptimalPathLengthOnline(GridGraph gridGraph, Point start, Point end) {
        return computeOptimalPathLengthOnline(gridGraph, start.x, start.y, end.x, end.y);
    }
    
    public static double computeOptimalPathLengthOnline(GridGraph gridGraph, int sx, int sy, int ex, int ey) {
        int[][] path = computeOptimalPathOnline(gridGraph, sx, sy, ex, ey);
        return computePathLength(gridGraph, path);
    }
    
    public static int[][] computeOptimalPathOnline(GridGraph gridGraph, int sx, int sy, int ex, int ey) {
        // Optimal Online algorithm.
        PathFindingAlgorithm algo = new Anya16(gridGraph, sx, sy, ex, ey);
        algo.computePath();
        int[][] path = algo.getPath();
        path = removeDuplicatesInPath(path);
        return path;
    }
    
    public static double computeOptimalPathLengthOffline(GridGraph gridGraph, Point start, Point end) {
        return computeOptimalPathLengthOffline(gridGraph, start.x, start.y, end.x, end.y);
    }
    
    public static double computeOptimalPathLengthOffline(GridGraph gridGraph, int sx, int sy, int ex, int ey) {
        int[][] path = computeOptimalPathOffline(gridGraph, sx, sy, ex, ey);
        return computePathLength(gridGraph, path);
    }
    
    public static int[][] computeOptimalPathOffline(GridGraph gridGraph, int sx, int sy, int ex, int ey) {
        // Optimal Offline algorithm. (preprocessing for faster pathfinding)
        PathFindingAlgorithm algo = EdgeNLevelSparseVisibilityGraphAlgorithm.graphReuse(gridGraph, sx, sy, ex, ey);
        algo.computePath();
        int[][] path = algo.getPath();
        path = removeDuplicatesInPath(path);
        return path;
    }
    
    public static ArrayList<StartEndPointData> fixProblemPathLength(GridGraph gridGraph, ArrayList<StartEndPointData> problems) {
        ArrayList<StartEndPointData> fixedProblems = new ArrayList<>();
        for (StartEndPointData problem : problems) {
            //System.out.println(problem.start + " | " + problem.end);
            double shortestPathLength = computeOptimalPathLengthOnline(gridGraph, problem.start, problem.end);
            fixedProblems.add(new StartEndPointData(problem.start, problem.end, shortestPathLength));
            if (shortestPathLength > problem.shortestPath + 0.0001) System.out.println("REPAIRING: " + problem.shortestPath + " -> " + shortestPathLength);
        }
        return fixedProblems;
    }

    public static int[][] removeDuplicatesInPath(int[][] path) {
        if (path.length <= 2) return path;
        
        int[][] newPath = new int[path.length][];
        int index = 0;
        newPath[0] = path[0];
        for (int i=1; i<path.length-1; ++i) {
            if (isCollinear(path[i][0], path[i][1], path[i+1][0], path[i+1][1], newPath[index][0], newPath[index][1])) {
                // skip
            } else {
                index++;
                newPath[index] = path[i];
            }
        }
        index++;
        newPath[index] = path[path.length-1];
        return Arrays.copyOf(newPath, index+1);
    }
    
    private static boolean isCollinear(int x1, int y1, int x2, int y2, int x3, int y3) {
        return (y3-y1)*(x2-x1) == (x3-x1)*(y2-y1);
    }
    
    /**
     * Generates a path between two points on a grid.
     * @return an array of int[2] indicating the coordinates of the path.
     */
    public static int[][] generatePath(AlgoFunction algoFunction, GridGraph gridGraph,
            int sx, int sy, int ex, int ey) {
        PathFindingAlgorithm algo = algoFunction.getAlgo(gridGraph, sx, sy, ex, ey);
        algo.computePath();
        
        int[][] path = algo.getPath();
        return path;
    }
    
    public static boolean isPathTaut(GridGraph gridGraph, int[][] path) {
        int v1 = 0;
        int v2 = 1;
        for (int v3=2; v3<path.length; ++v3) {
            if (!gridGraph.isTaut(path[v1][0], path[v1][1], path[v2][0], path[v2][1], path[v3][0], path[v3][1])) return false;
            ++v1;
            ++v2;
        }
        return true;
    }

    public static boolean isOptimal(double length, double optimalLength) {
        //System.out.println(length + " | " + optimalLength + " | " + ((length - optimalLength) < 0.0001)); 
        return (length - optimalLength) < 0.0001;
    }
    
    public static boolean validateMazeConnectedSetSize(GridGraph gridGraph, float cutoffLargestRatioToRemaining) {
        MazeAnalysis.Options options = new MazeAnalysis.Options();
        options.largestRatioToSecond = true;
        options.largestRatioToRemaining = true;
        MazeAnalysis mazeAnalysis = new MazeAnalysis(gridGraph, options);
        System.out.println(mazeAnalysis.largestRatioToRemaining + " " + mazeAnalysis.largestRatioToSecond);
        return mazeAnalysis.largestRatioToRemaining >= cutoffLargestRatioToRemaining;
    }
    
    public static void cleanUpPreallocatedMemory() {
        Anya.clearMemory();
        Anya16.clearMemory();
        VisibilityGraph.clearMemory();
        SparseVisibilityGraph.clearMemory();
        SparseVisibilityGraphAlgorithmFibHeap.clearMemory();
        Memory.clearMemory();
        ReusableIndirectHeap.clearMemory();
        LineOfSightScanner.clearMemory();
        EdgeNLevelSparseVisibilityGraph.clearMemory();
        EdgeNLevelSparseVisibilityGraphAlgorithmFibHeap.clearMemory();
        VisibilityGraphOptimised.clearMemory();
        SnapshotItem.clearCached();
        //IVGAlgorithm.clearCached();
        
        System.gc(); System.gc();
    }
} public class GraphImporter {
    private GridGraph gridGraph;
    
    private GraphImporter(String filepath) {
        boolean[][] result = null;

        File file = new File(filepath);
        try {
            FileReader fileReader = new FileReader(file);
            Scanner sc = new Scanner(fileReader);
            int x = sc.nextInt();
            int y = sc.nextInt();
            result = new boolean[y][];
            for (int i=0; i<y; i++) {
                result[i] = new boolean[x];
                for (int j=0; j<x; j++) {
                    result[i][j] = (sc.nextInt() != 0);
                }
            }
            sc.close();
        } catch (FileNotFoundException e) {
            System.out.println("File " + filepath + " not found");
        }
        /* Commented out because of Unreachable Catch Clause warning.
        catch (IOException e) {
            e.printStackTrace();
        }*/
        
        create(result);          
    }

    private void create(boolean[][] result) {
        gridGraph = new GridGraph(result[0].length, result.length);
        for (int y=0;y<result.length;y++) {
            for (int x=0;x<result[0].length;x++) {
                gridGraph.setBlocked(x, y, result[y][x]);
            }
        }
    }

    private void createDoubleSize(boolean[][] result) {
        int size = 2;
        
        gridGraph = new GridGraph(result[0].length*size, result.length*size);
        for (int y=0;y<result.length*size;y++) {
            for (int x=0;x<result[0].length*size;x++) {
                gridGraph.setBlocked(x, y, result[y/size][x/size]);
            }
        }
    }
    
    private GridGraph retrieve() {
        return gridGraph;
    }
    
    public static ArrayList<String> getAllMazeNames() {
        ArrayList<String> mazeNames = new ArrayList<>();
        
        String path = AnyAnglePathfinding.PATH_MAZEDATA + "/";
        File dir = new File(path);
        File[] files = dir.listFiles();
        for (File file : files) {
            mazeNames.add(file.getName());
        }
        
        return mazeNames;
    }

    /**
     * Import a graph from a file in the predefinedgrids directory.
     * Look into the GraphImporter documentation for details on how to create a grid file.
     */
    public static GridGraph importGraphFromFile(String filename) {
        String filepath = AnyAnglePathfinding.PATH_GRAPHIMPORT + filename;
        return importGraphFromFilePath(filepath);
    }

    /**
     * Import a graph from a file in the predefinedgrids directory,
     * and also set the start and goal points.
     */
    public static GridAndGoals importGraphFromFile(String filename, int sx, int sy, int ex, int ey) {
        String filepath = AnyAnglePathfinding.PATH_GRAPHIMPORT + filename;
        return importGraphFromFilePath(filepath, sx, sy, ex, ey);
    }

    /**
     * Import a graph from a file in the AnyAnglePathfinding directory.
     */
    public static GridGraph importGraphFromFilePath(String filepath) {
        GridGraph gridGraph;
        GraphImporter graphImporter = new GraphImporter(filepath);
        gridGraph = graphImporter.retrieve();
        return gridGraph;
    }

    /**
     * Import a graph from a file in the AnyAnglePathfinding directory,
     * and also set the start and goal points.
     */
    public static GridAndGoals importGraphFromFilePath(String filepath, int sx, int sy, int ex, int ey) {
        GridGraph gridGraph = GraphImporter.importGraphFromFilePath(filepath);
        return new GridAndGoals(gridGraph, sx, sy, ex, ey);
    }

    public static GridAndGoals loadStoredMaze(String mazeName, String problemName) {
        String filepath = AnyAnglePathfinding.PATH_MAZEDATA + mazeName + "/maze.txt";
        TwoPoint tp = readProblem(problemName);
        return importGraphFromFilePath(filepath, tp.p1.x, tp.p1.y, tp.p2.x, tp.p2.y);
    }
    
    public static GridGraph loadStoredMaze(String mazeName) {
        String filepath = AnyAnglePathfinding.PATH_MAZEDATA + mazeName + "/maze.txt";
        return importGraphFromFilePath(filepath);
    }

    public static ArrayList<TwoPoint> loadStoredMazeProblems(String mazeName) {
        String path = AnyAnglePathfinding.PATH_MAZEDATA + mazeName + "/";
        File dir = new File(path);
        File[] files = dir.listFiles((file, name) -> name.endsWith(".problem"));
        
        ArrayList<TwoPoint> list = new ArrayList<>(files.length);
        for (File file : files) {
            TwoPoint tp = readProblem(file);
            list.add(tp);
        }
        return list;
    }

    public static ArrayList<StartEndPointData> loadStoredMazeProblemData(String mazeName) {
        String path = AnyAnglePathfinding.PATH_MAZEDATA + mazeName + "/";
        File dir = new File(path);
        File[] files = dir.listFiles((file, name) -> name.endsWith(".problem"));
        
        ArrayList<StartEndPointData> list = new ArrayList<>(files.length);
        for (File file : files) {
            TwoPoint tp = readProblem(file);
            String sp = readFile(file).get("shortestPathLength");
            double shortestPath = Double.parseDouble(sp);
            list.add(new StartEndPointData(tp.p1, tp.p2, shortestPath));
        }
        return list;
    }
    
    private static TwoPoint readProblem(File file) {
        String s = file.getName();
        s = s.substring(0, s.lastIndexOf('.')); // remove extension
        return readProblem(s);
    }

    private static TwoPoint readProblem(String problemName) {
        String[] args = problemName.split("[-_]");
        
        if (args.length != 4)
            throw new UnsupportedOperationException("Invalid problem name: " + problemName);
        return new TwoPoint(
                Integer.parseInt(args[0]),
                Integer.parseInt(args[1]),
                Integer.parseInt(args[2]),
                Integer.parseInt(args[3])
                );
    }
    
    private static HashMap<String, String> readFile(File file) {
        HashMap<String,String> dict = new HashMap<>();
        try {
            FileReader fr = new FileReader(file);
            BufferedReader br = new BufferedReader(fr);
            String s = br.readLine();
            while (s != null) {
                put(dict, s);
                s = br.readLine();
            }
    
        } catch (IOException e) {
            e.printStackTrace();
        }
        
        return dict;
    }
        
    private static void put(HashMap<String,String> dict, String input) {
        String[] args = input.split(":", 2);
        dict.put(args[0].trim(), args[1].trim());
    }
}
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;
import algorithms.datatypes.Point;
import grid.GridGraph;
import main.analysis.MazeAnalysis;
import main.analysis.TwoPoint;
import main.graphgeneration.AutomataGenerator;
import main.graphgeneration.MazeMapGenerator;
import main.graphgeneration.TiledMapGenerator;
import main.graphgeneration.UpscaledMapGenerator;
import main.testgen.StartEndPointData;
import main.testgen.Stringifier;
import main.utility.Utility;
import uiandio.GraphImporter;
        int seed = mazeName.hashCode()+(multiplier+1)*31;
        
        ArrayList<StartEndPointData> newProblems = generateProblems(newGridGraph, nProblems, seed);
        
        String newMazeName = mazeName + "_x" + multiplier;
        return new MazeAndTestCases(newMazeName, newGridGraph, newProblems);
    }

    public static MazeAndTestCases loadTiledMaze(int mazePoolIndex, int size) {
        int nTiles = size*size;
        GridGraph[] mazePool = getMazePool(mazePoolIndex);
        GridGraph[] mazes = new GridGraph[nTiles];
        for (int i=0;i<nTiles;++i) {
            mazes[i] = mazePool[i%mazePool.length];
        }
        
        GridGraph newGridGraph = TiledMapGenerator.mergeMaps(mazes, size, size);
        
        int nProblems = NUM_TEST_PROBLEMS;
        int seed = size*787+(mazePoolIndex+1)*23;
        
        ArrayList<StartEndPointData> newProblems = generateProblems(newGridGraph, nProblems, seed);
        
        String newMazeName = "tiled_" + mazePoolIndex + "_" + size;
        
        return new MazeAndTestCases(newMazeName, newGridGraph, newProblems);
    }

    public static MazeAndTestCases loadMazeMaze(int sizeIndex, int corridorWidthIndex, int connectednessIndex) {

        int sizeX, sizeY;
        switch (sizeIndex) {
            case 0: sizeX = sizeY = 500; break;
            case 1: sizeX = sizeY = 1000; break;
            case 2: sizeX = sizeY = 2000; break;
            case 3: sizeX = sizeY = 3000; break;
            case 4: sizeX = sizeY = 4000; break;
            case 5: sizeX = sizeY = 5000; break;
            case 6: sizeX = sizeY = 6000; break;
            default: throw new UnsupportedOperationException("Invalid sizeIndex: " + sizeIndex);
        }

        int corridorWidth;
        switch (corridorWidthIndex) {
            case 0: corridorWidth = 1; break;
            case 1: corridorWidth = 2; break;
            case 2: corridorWidth = 4; break;
            default: throw new UnsupportedOperationException("Invalid corridorWidthIndex: " + corridorWidthIndex);
        }

        float connectednessRatio;
        switch (connectednessIndex) {
            case 0: connectednessRatio = 0f; break;
            case 1: connectednessRatio = 0.0001f; break;
            case 2: connectednessRatio = 0.001f; break;
            case 3: connectednessRatio = 0.01f; break;
            case 4: connectednessRatio = 0.1f; break;
            default: throw new UnsupportedOperationException("Invalid connectednessIndex: " + connectednessIndex);
        }

        int nProblems = NUM_TEST_PROBLEMS;
        int seed = (sizeIndex+1)*197;
        seed = (seed + connectednessIndex+1)*53;
        seed = (seed + corridorWidthIndex+1)*131;
        int problemSeed = (seed + sizeIndex+1)*13;
        
        GridGraph gridGraph = MazeMapGenerator.generateSeededGraphOnly(seed, sizeX, sizeY, corridorWidth, connectednessRatio);
        ArrayList<StartEndPointData> problems = generateProblemsInLargestSetOffline(gridGraph, nProblems, problemSeed); 
        String mazeName = Stringifier.mazeMapToString(seed, sizeX, sizeY, corridorWidth, connectednessRatio);
        return new MazeAndTestCases(mazeName, gridGraph, problems);
    }
    
    private static GridGraph[] getMazePool(int mazePoolIndex) {
        switch (mazePoolIndex) {
            case 0:
                return loadMazesFromNames(new String[] {
                    "sc1_BigGameHunters",
                    "sc1_RedCanyons",
                    "sc1_Eruption",
                });
            case 1:
                return loadMazesFromNames(new String[] {
                    "sc1_HotZone",
                    "sc1_Isolation",
                    "sc1_SpaceAtoll",
                    "sc1_Ramparts",
                    "sc1_OrbitalGully",
                });
            case 2:
                return loadMazesFromNames(new String[] {
                    "wc3_bootybay",
                    "wc3_darkforest",
                    "wc3_icecrown",
                });
            case 3:
                return loadMazesFromNames(new String[] {
                    "wc3_hillsofglory",
                    "wc3_nighthaven",
                    "wc3_theglaive",
                    "wc3_battleground",
                    "wc3_deadwaterdrop",
                });
        }
        
        throw new UnsupportedOperationException("Invalid maze pool index: " + mazePoolIndex);
    }
    
    private static GridGraph[] loadMazesFromNames(String[] mazeNames) {
        GridGraph[] gridGraphs = new GridGraph[mazeNames.length];
        for (int i=0;i<mazeNames.length;++i) {
            gridGraphs[i] = GraphImporter.loadStoredMaze(mazeNames[i]);
        }
        return gridGraphs;
    }


    private static ArrayList<StartEndPointData> generateProblems(GridGraph gridGraph, int nProblems, int seed) {
        ArrayList<ArrayList<Point>> connectedSets = MazeAnalysis.findConnectedSetsFast(gridGraph);
        Random rand = new Random(seed);
        ArrayList<StartEndPointData> problemList = new ArrayList<>();
        HashSet<TwoPoint> chosenProblems = new HashSet<>();