Niitty

warning: unused import: `Read`
 --> input/code.rs:5:19
  |
5 |     io::{BufRead, Read},
  |                   ^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused variable: `y`
  --> input/code.rs:19:14
   |
19 |         for (y, line) in stdin_handle.take(n as usize).enumerate() {
   |              ^ help: if this is intentional, prefix it with an underscore: `_y`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `min`
  --> input/code.rs:34:13
   |
34 |         let min = kukkien_maarat.values().min().unwrap();
   |             ^^^ help: if this is intentional, prefix it with an underscore: `_min`

warning: function `calc_idx` is never used
   --> input/code.rs:165:4
    |
165 | fn calc_idx(n: u32, x: u32, y: u32) -> usize {
    |    ^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: 4 warnings emitted

use std::{
    cmp::max,
    cmp::min,
    collections::{HashMap, HashSet},
    io::{BufRead, Read},
};

fn main() {
    let mut stdin_handle = std::io::stdin().lock().lines();

    let n: u32 = stdin_handle.next().unwrap().unwrap().parse().unwrap();

    let mut kukkien_maarat: HashMap<char, u32> = HashMap::new();

    // Kerätään niitty yksiulotteiseen vektoriin, jossa kukat vasemmalta oikealle rivi kerrallaan
    // ylhäältä alas.
    let kukat: Vec<char> = {
        let mut kukat = Vec::with_capacity((n * n) as usize);
        for (y, line) in stdin_handle.take(n as usize).enumerate() {
            let line = line.unwrap();
            for kukka in line.chars() {
                kukkien_maarat
                    .entry(kukka)
                    .and_modify(|maara| *maara += 1)
                    .or_insert(1);
            }
            kukat.extend(line.chars());
        }
        kukat
    };

    // Etsitään vähiten esiintynyt kukkalaji
    let harvinaisin_kukka = {
        let min = kukkien_maarat.values().min().unwrap();
        *kukkien_maarat
            .iter()
            .min_by_key(|tuple| *tuple.1)
            .unwrap()
            .0
    };

    let esiintyyko_kaikki_kukat = |x_min: i32, x_max: i32, y_min: i32, y_max: i32| -> bool {
        let mut esiintyneet_kukat: HashSet<char> = HashSet::with_capacity(kukkien_maarat.len());
        for y in y_min..=y_max {
            for kukka in kukat[(y as usize * n as usize + x_min as usize)
                ..=(y as usize * n as usize + x_max as usize)]
                .iter()
            {
                esiintyneet_kukat.insert(*kukka);
            }
        }
        esiintyneet_kukat.len() == kukkien_maarat.len()
    };

    struct Suorakulmio {
        pinta_ala: u32,
        x_min: u32,
        x_max: u32,
        y_min: u32,
        y_max: u32,
    }

    let mut tulokset: Vec<Suorakulmio> = Vec::with_capacity(kukkien_maarat.len());
    for (i, kukka) in kukat.iter().enumerate() {
        if *kukka != harvinaisin_kukka {
            continue;
        }

        let piste = Piste {
            x: i as u32 % n,
            y: i as u32 / n,
        };

        let mut x_min = piste.x as i32;
        let mut x_max = piste.x as i32;
        let mut y_min = piste.y as i32;
        let mut y_max = piste.y as i32;

        // Nyt laajennetaan joka suuntaan yksi blokki kerrallaan muodostaen neliö tämän kukan
        // ympärille, kunnes neliön sisällä on ainakin yksi esiintymä kaikista lajeista.
        loop {
            x_min = max(x_min - 1, 0);
            x_max = min(x_max + 1, n as i32 - 1);
            y_min = max(y_min - 1, 0);
            y_max = min(y_max + 1, n as i32 - 1);

            if esiintyyko_kaikki_kukat(x_min, x_max, y_min, y_max) {
                // Kaikki kukat ovat esiintyneet neliössä.
                // println!(
                //     "Kaikki kukat esiintyvät neliössä: x_min: {}, x_max: {}, y_min: {}, y_max: {}",
                //     x_min, x_max, y_min, y_max
                // );
                break;
            }
        }
        // Nyt on löydetty neliö, jossa on kaikkia lajeja. Seuraavaksi pienennetään tämän neliön
        // vasen-, oikea-, ala- ja ylälaitoja yksi kerrallaan, kunnes suorakulmiota ei voida enää
        // pienentää hävittämättä jotain lajia.

        loop {
            let mut pienennetty = false;
            // Ylälaita.
            {
                let new_y_min = min(y_min + 1, n as i32 - 1);
                if esiintyyko_kaikki_kukat(x_min, x_max, new_y_min, y_max) && new_y_min != y_min {
                    pienennetty = true;
                    y_min = new_y_min;
                }
            }
            // Alalaita
            {
                let new_y_max = max(y_max - 1, 0);
                if esiintyyko_kaikki_kukat(x_min, x_max, y_min, new_y_max) && new_y_max != y_max {
                    pienennetty = true;
                    y_max = new_y_max;
                }
            }
            // Vasen laita
            {
                let new_x_min = min(x_min + 1, n as i32 - 1);
                if esiintyyko_kaikki_kukat(new_x_min, x_max, y_min, y_max) && new_x_min != x_min {
                    pienennetty = true;
                    x_min = new_x_min
                }
            }
            // Oikea laita
            {
                let new_x_max = max(x_max - 1, 0);
                if esiintyyko_kaikki_kukat(x_min, new_x_max, y_min, y_max) && new_x_max != x_min {
                    pienennetty = true;
                    x_max = new_x_max;
                }
            }
            if !pienennetty {
                break;
            }
        }
        tulokset.push(Suorakulmio {
            pinta_ala: ((x_max - x_min + 1) * (y_max - y_min + 1)) as u32,
            x_min: x_min as u32,
            x_max: x_max as u32,
            y_min: y_min as u32,
            y_max: y_max as u32,
        });

        // println!(
        //     "x_min: {}, x_max: {}, y_min: {}, y_max: {}",
        //     x_min, x_max, y_min, y_max
        // );
    }

    let pienin = tulokset
        .iter()
        .min_by_key(|kulmio| kulmio.pinta_ala)
        .unwrap();
    let aitausten_maara = {
        let x = pienin.x_max - pienin.x_min + 1;
        let y = pienin.y_max - pienin.y_min + 1;
        (n - y + 1) * (n - x + 1)
    };
    println!("{}", aitausten_maara);
}

// Laskee indeksin kukkavektoriin kaksiulotteisesta pisteestä.
fn calc_idx(n: u32, x: u32, y: u32) -> usize {
    (y * n + x) as usize
}

struct Piste {
    x: u32,
    y: u32,
}

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 7

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 8

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 9

Group: 2, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 10

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 12

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 13

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 14

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 15

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 16

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 17

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 18

Group: 5, 6

Verdict: WRONG ANSWER

Test 19

Group: 5, 6

Verdict: WRONG ANSWER

Test 20

Group: 5, 6

Verdict: WRONG ANSWER

Test 21

Group: 5, 6

Verdict: WRONG ANSWER

Test 22

Group: 6

Verdict: WRONG ANSWER

Test 23

Group: 6

Verdict: WRONG ANSWER

Test 24

Group: 6

Verdict: WRONG ANSWER

Test 25

Group: 6

Verdict: TIME LIMIT EXCEEDED