use std::collections::VecDeque;

impl Solution {
    // Define movement directions as a constant at the Solution level
    const DIRECTIONS: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];

    pub fn largest_island(mut grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let mut island_sizes = vec![0; 2]; // Stores the size of each identified island
        let mut island_id = 2; // Island IDs start from 2 to distinguish from 0 and 1
        let mut max_island_size = 1;

        // Step 1: Identify and label all islands
        for row in 0..n {
            for col in 0..n {
                if grid[row][col] == 1 {
                    // Mark the island and store its size
                    let size = Self::bfs_mark_island(&mut grid, row as i32, col as i32, island_id);
                    island_sizes.push(size);
                    max_island_size = max_island_size.max(size); // Track largest island found
                    island_id += 1;
                }
            }
        }

        // Step 2: Try converting each 0 into a 1 and compute the new island size
        for row in 0..n {
            for col in 0..n {
                if grid[row][col] == 0 {
                    let mut adj_islands = Vec::new(); // List of neighboring island IDs

                    // Check all four directions for adjacent islands
                    for &(dr, dc) in &Self::DIRECTIONS {
                        let nr = row as i32 + dr;
                        let nc = col as i32 + dc;
                        if Self::is_valid(nr, nc, n) {
                            let id = grid[nr as usize][nc as usize] as usize;
                            if id > 1 {
                                adj_islands.push(id);
                            }
                        }
                    }

                    if !adj_islands.is_empty() {
                        // Remove duplicates efficiently
                        adj_islands.sort_unstable();
                        adj_islands.dedup();

                        // Compute the new island size by merging adjacent islands
                        let new_size = 1 + adj_islands.into_iter().map(|id| island_sizes[id]).sum::<i32>();
                        max_island_size = max_island_size.max(new_size);
                    }
                }
            }
        }

        max_island_size
    }

    /// Uses BFS to mark an island and return its size
    fn bfs_mark_island(grid: &mut Vec<Vec<i32>>, r: i32, c: i32, island_id: i32) -> i32 {
        let n = grid.len();
        let mut queue = VecDeque::new();
        queue.push_back((r, c));
        grid[r as usize][c as usize] = island_id; // Mark the starting cell
        let mut size = 0;

        while let Some((row, col)) = queue.pop_front() {
            size += 1;

            // Explore all four possible directions
            for &(dr, dc) in &Self::DIRECTIONS {
                let nr = row + dr;
                let nc = col + dc;
                if Self::is_valid(nr, nc, n) && grid[nr as usize][nc as usize] == 1 {
                    grid[nr as usize][nc as usize] = island_id; // Mark the cell as part of the island
                    queue.push_back((nr, nc)); // Add to BFS queue
                }
            }
        }

        size
    }

    /// Checks if (row, col) is within the grid boundaries
    fn is_valid(r: i32, c: i32, n: usize) -> bool {
        (0..n as i32).contains(&r) && (0..n as i32).contains(&c)
    }
}