import java.util.ArrayList;
import java.util.Random;

/**
 * =========================================================
 *  Island Class
 * =========================================================
 *  Represents a single island in the ocean grid.
 *
 *  An island is defined as a connected group of "land" cells where:
 *    - Land  = 1 in the ocean integer array
 *    - Water = 0 in the ocean integer array
 *
 *  Connectivity rule:
 *    Cells within an ISLAND connect only orthogonally
 *    (up, down, left, right) -- NOT diagonally.
 *
 *  Separation rule:
 *    Two DIFFERENT islands may NOT touch each other, even diagonally.
 *    They must be separated by at least one water cell in all
 *    8 surrounding directions.
 *
 *  Key concept for this lesson:
 *    Islands are built using RECURSIVE BACKTRACKING.
 *    See the grow() method for the full explanation.
 * =========================================================
 */
public class Island {

    // -------------------------------------------------------
    //  DIRECTION ARRAYS  (used to navigate the 2D grid)
    // -------------------------------------------------------

    // These paired arrays define the four orthogonal directions.
    // DR4[i] = row change, DC4[i] = column change for direction i.
    //   i=0 : UP    (row-1, col  )
    //   i=1 : DOWN  (row+1, col  )
    //   i=2 : LEFT  (row,   col-1)
    //   i=3 : RIGHT (row,   col+1)
    private static final int[] DR4 = {-1,  1,  0,  0};
    private static final int[] DC4 = { 0,  0, -1,  1};

    // All 8 surrounding directions (orthogonal + diagonal).
    // Used to enforce the "no diagonal touching between islands" rule.
    //   i=0 : UP-LEFT    i=1 : UP    i=2 : UP-RIGHT
    //   i=3 : LEFT                   i=4 : RIGHT
    //   i=5 : DOWN-LEFT  i=6 : DOWN  i=7 : DOWN-RIGHT
    private static final int[] DR8 = {-1, -1, -1,  0,  0,  1,  1,  1};
    private static final int[] DC8 = {-1,  0,  1, -1,  1, -1,  0,  1};

    // -------------------------------------------------------
    //  INSTANCE VARIABLE
    // -------------------------------------------------------

    // The ordered list of land cells that make up this island.
    // Each Coordinates object stores a (row, col) position.
    private ArrayList<Coordinates> cells;

    // -------------------------------------------------------
    //  CONSTRUCTOR
    // -------------------------------------------------------

    /**
     * Creates a new island seeded with a single land cell.
     * The island can be grown to a larger target size using grow().
     *
     * @param startCell  the first (seed) coordinate of the island
     */
    public Island(Coordinates startCell) {
        cells = new ArrayList<>();
        cells.add(startCell);
    }

    // -------------------------------------------------------
    //  GETTERS
    // -------------------------------------------------------

    /** Returns the list of all land cells that belong to this island. */
    public ArrayList<Coordinates> getCells() {
        return cells;
    }

    /** Returns the number of land cells in this island. */
    public int getSize() {
        return cells.size();
    }

    // -------------------------------------------------------
    //  HELPER: contains
    // -------------------------------------------------------

    /**
     * Returns true if this island already owns the cell at (row, col).
     *
     * This matters during growth because:
     *   - We never want to add the same cell twice.
     *   - When checking diagonal neighbors, we treat land that belongs
     *     to THIS island differently from land on a DIFFERENT island.
     *
     * @param row  row index to check
     * @param col  column index to check
     * @return true if (row, col) is part of this island
     */
    public boolean contains(int row, int col) {
        for (Coordinates c : cells) {
            if (c.getRow() == row && c.getCol() == col) {
                return true;
            }
        }
        return false;
    }

    // -------------------------------------------------------
    //  HELPER: isValidExpansion
    // -------------------------------------------------------

    /**
     * Decides whether it is legal to expand this island to include (row, col).
     *
     * Three rules must ALL pass:
     *
     *   Rule 1 - In bounds  : (row, col) must be inside the ocean grid.
     *
     *   Rule 2 - Water only : the cell must currently be water (ocean value == 0).
     *                         We cannot place land on top of land.
     *
     *   Rule 3 - No conflict: none of the 8 surrounding neighbors of (row, col)
     *                         may be land that belongs to a DIFFERENT island.
     *                         (Diagonal or orthogonal land from THIS island is fine --
     *                          that is how an island can have L-shapes or U-shapes.)
     *
     * NOTE: This method does NOT verify that (row, col) is adjacent to an existing
     * island cell.  The caller (grow) guarantees this by only passing in the
     * orthogonal neighbors of current cells.
     *
     * @param row      candidate row
     * @param col      candidate column
     * @param ocean    the 2D ocean grid
     * @param numRows  number of rows in ocean
     * @param numCols  number of columns in ocean
     * @return true if expanding to (row, col) is allowed
     */
    private boolean isValidExpansion(int row, int col,
                                     int[][] ocean, int numRows, int numCols) {
        // Rule 1: bounds check
        if (row < 0 || row >= numRows || col < 0 || col >= numCols) {
            return false;
        }

        // Rule 2: the cell must currently be water
        if (ocean[row][col] != 0) {
            return false;
        }

        // Rule 3: scan all 8 neighbors for land that belongs to a different island
        for (int d = 0; d < 8; d++) {
            int nr = row + DR8[d];
            int nc = col + DC8[d];

            // Make sure the neighbor is within the grid before checking it
            if (nr >= 0 && nr < numRows && nc >= 0 && nc < numCols) {
                // If the neighbor is land AND is NOT part of THIS island, reject!
                // That foreign land means placing here would violate the separation rule.
                if (ocean[nr][nc] == 1 && !contains(nr, nc)) {
                    return false;
                }
            }
        }

        return true; // All three rules passed
    }

    // -------------------------------------------------------
    //  HELPER: alreadyCandidate
    // -------------------------------------------------------

    /**
     * Returns true if (row, col) already appears in the candidates list.
     *
     * When we collect expansion candidates, two existing island cells
     * might share the same empty neighbor.  This prevents us from adding
     * that neighbor to the candidate list twice.
     *
     * @param row        row index to check
     * @param col        column index to check
     * @param candidates the current list of candidate positions
     * @return true if (row, col) is already in candidates
     */
    private boolean alreadyCandidate(int row, int col, ArrayList<int[]> candidates) {
        for (int[] candidate : candidates) {
            if (candidate[0] == row && candidate[1] == col) {
                return true;
            }
        }
        return false;
    }

    // -------------------------------------------------------
    //  HELPER: shuffleCandidates  (Fisher-Yates Shuffle)
    // -------------------------------------------------------

    /**
     * Randomly shuffles the candidates list in-place.
     *
     * ALGORITHM: Fisher-Yates Shuffle  (O(n) time complexity)
     *   For i from the last index DOWN to 1:
     *     Pick a random index j in the range [0, i]
     *     Swap the elements at positions i and j
     *
     * Without shuffling, the grow() method would always pick candidates
     * in the same order and every island would look like a straight line
     * or have a predictable shape.  Shuffling is what gives each island
     * a unique, organic-looking form.
     *
     * @param list  the ArrayList to shuffle
     * @param rand  Random object for generating random indices
     */
    private void shuffleCandidates(ArrayList<int[]> list, Random rand) {
        for (int i = list.size() - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);   // random index in [0, i]
            // Swap list[i] and list[j]
            int[] temp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, temp);
        }
    }

    // -------------------------------------------------------
    //  RECURSIVE METHOD: grow       *** CORE ALGORITHM ***
    // -------------------------------------------------------

    /**
     * Recursively grows this island until it contains exactly targetSize cells.
     *
     * ═══════════════════════════════════════════════════════════
     *  RECURSIVE BACKTRACKING -- the big idea:
     *
     *  We solve the problem by making a choice (which cell to add),
     *  then recursing to see if that choice leads to a full solution.
     *  If the recursion reports failure, we UNDO the choice and try
     *  the next option.  This "try → recurse → undo if bad" cycle
     *  is called BACKTRACKING.
     * ═══════════════════════════════════════════════════════════
     *
     *  BASE CASE  (the stopping condition):
     *    cells.size() >= targetSize
     *    → The island is the right size.  Return true (success).
     *
     *  RECURSIVE CASE:
     *    1. Collect all valid orthogonal neighbors of current island cells.
     *    2. Shuffle them for random island shapes.
     *    3. For each candidate neighbor:
     *         a. ADD the cell (mark as land in ocean, add to cells list).
     *         b. RECURSE  -- call grow() again.
     *         c. If recursion returned true → propagate true (done!).
     *         d. If recursion returned false → BACKTRACK:
     *               remove the cell and restore ocean to water.
     *    4. If ALL candidates fail → return false (signal to backtrack further).
     *
     * @param targetSize  the desired total number of cells in this island
     * @param ocean       the 2D array (mutated as cells are added/removed)
     * @param numRows     number of rows in the ocean
     * @param numCols     number of columns in the ocean
     * @param rand        Random object for shuffling candidates
     * @return true if the island successfully reached targetSize; false otherwise
     */
    public boolean grow(int targetSize, int[][] ocean,
                        int numRows, int numCols, Random rand) {

        // ── BASE CASE ────────────────────────────────────────────────
        // The island already has enough cells -- we're done!
        if (cells.size() >= targetSize) {
            return true;
        }
        // ────────────────────────────────────────────────────────────

        // ── BUILD THE CANDIDATE LIST ─────────────────────────────────
        // Look at every orthogonal neighbor of every cell currently in
        // the island.  If the neighbor is a legal place to expand, add
        // it to our list of candidates to try.
        ArrayList<int[]> candidates = new ArrayList<>();

        for (Coordinates c : cells) {
            for (int d = 0; d < 4; d++) {
                int nr = c.getRow() + DR4[d];
                int nc = c.getCol() + DC4[d];

                // Only add valid, non-duplicate candidates
                if (isValidExpansion(nr, nc, ocean, numRows, numCols)
                        && !alreadyCandidate(nr, nc, candidates)) {
                    candidates.add(new int[]{nr, nc});
                }
            }
        }
        // ────────────────────────────────────────────────────────────

        // ── DEAD END? ────────────────────────────────────────────────
        // No legal neighbors means we're completely surrounded.
        // Return false so the caller can backtrack and try a different path.
        if (candidates.isEmpty()) {
            return false;
        }
        // ────────────────────────────────────────────────────────────

        // ── SHUFFLE for variety ──────────────────────────────────────
        // Randomize candidate order so islands grow in random directions
        // and don't always look the same.
        shuffleCandidates(candidates, rand);
        // ────────────────────────────────────────────────────────────

        // ── TRY EACH CANDIDATE (with backtracking) ───────────────────
        for (int[] candidate : candidates) {
            int r = candidate[0];
            int c = candidate[1];

            // STEP A: ADD -- commit to this cell
            cells.add(new Coordinates(r, c));
            ocean[r][c] = 1;          // Mark as land in the ocean grid

            // STEP B: RECURSE -- attempt to finish growing from here
            if (grow(targetSize, ocean, numRows, numCols, rand)) {
                return true;          // Propagate success all the way up!
            }

            // STEP C: BACKTRACK -- this path failed, undo and try the next candidate
            cells.remove(cells.size() - 1);
            ocean[r][c] = 0;          // Restore cell to water
        }
        // ────────────────────────────────────────────────────────────

        // Every candidate was tried and none worked.
        // Tell the caller to backtrack further.
        return false;
    }

    // -------------------------------------------------------
    //  STATIC FACTORY METHOD: buildIsland
    // -------------------------------------------------------

    /**
     * Attempts to build and place a complete island of targetSize cells
     * somewhere in the ocean.
     *
     * This is a "static factory" method -- it constructs and returns
     * a ready-to-use Island object (or null if placement was impossible).
     *
     * ALGORITHM:
     *   Repeat up to maxAttempts times:
     *     1. Pick a random (row, col) as the island seed.
     *     2. Skip it if it is not water.
     *     3. Skip it if ANY of its 8 neighbors are already land.
     *        (Placing a seed there would violate the separation rule.)
     *     4. Plant the seed and call grow() to finish the island.
     *     5. If grow() succeeds → return the finished Island.
     *     6. If grow() fails   → remove the seed, try again.
     *   If all attempts are exhausted → return null.
     *
     * @param ocean      the 2D ocean array
     * @param targetSize desired number of cells in the island
     * @param numRows    number of rows in the grid
     * @param numCols    number of columns in the grid
     * @param rand       Random object
     * @return a fully grown Island, or null if none could be placed
     */
    public static Island buildIsland(int[][] ocean, int targetSize,
                                     int numRows, int numCols, Random rand) {

        // Try at most this many different seed positions before giving up
        int maxAttempts = numRows * numCols;

        for (int attempt = 0; attempt < maxAttempts; attempt++) {

            // Step 1: choose a random seed location
            int startRow = rand.nextInt(numRows);
            int startCol = rand.nextInt(numCols);

            // Step 2: the seed cell must be water
            if (ocean[startRow][startCol] != 0) {
                continue;  // Already land -- try a new position
            }

            // Step 3: all 8 neighbors must also be water.
            // Any land in the neighborhood belongs to an existing island;
            // placing our seed here would create a diagonal or orthogonal
            // conflict with that island.
            boolean clearArea = true;
            for (int d = 0; d < 8; d++) {
                int nr = startRow + DR8[d];
                int nc = startCol + DC8[d];
                if (nr >= 0 && nr < numRows && nc >= 0 && nc < numCols) {
                    if (ocean[nr][nc] == 1) {
                        clearArea = false;
                        break;
                    }
                }
            }
            if (!clearArea) {
                continue;  // Too close to another island -- try elsewhere
            }

            // Step 4: plant the seed and attempt recursive growth
            Island island = new Island(new Coordinates(startRow, startCol));
            ocean[startRow][startCol] = 1;  // Mark seed as land

            if (island.grow(targetSize, ocean, numRows, numCols, rand)) {
                return island;              // SUCCESS -- island is fully built
            }

            // Step 6: growth failed -- remove the seed and try a new location
            ocean[startRow][startCol] = 0;
        }

        // All attempts exhausted -- could not fit an island in the ocean
        return null;
    }

    // -------------------------------------------------------
    //  toString
    // -------------------------------------------------------

    /**
     * Returns a human-readable description of this island,
     * showing its size and all the (row, col) coordinates it occupies.
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Island [size=").append(cells.size()).append("]: ");
        for (int i = 0; i < cells.size(); i++) {
            sb.append(cells.get(i));
            if (i < cells.size() - 1) {
                sb.append(" -> ");
            }
        }
        return sb.toString();
    }

}//end class Island