Monikulmio

use std::{collections::VecDeque, io};

fn read_next<'a, I>(iter: &mut I) -> usize
where
    I: Iterator<Item = &'a str>,
{
    iter.next()
        .expect("invalid input")
        .parse::<usize>()
        .expect("invalid integer")
}

#[derive(Clone, PartialEq)]
enum Pixel {
    Inside,
    Outside,
    LineV,
    LineH,
    Line45L,
    Line45R,
    Point,
}

fn draw_line(a: (usize, usize), b: (usize, usize), grid: &mut Vec<Vec<Pixel>>) {
    if a.0 == b.0 {
        // V-line
        let range;
        if a.1 > b.1 {
            range = b.1 + 1..a.1;
        } else {
            range = a.1 + 1..b.1;
        }
        for y in range {
            grid[y][b.0] = Pixel::LineV;
        }
    } else if a.1 == b.1 {
        // H-line
        let range;
        if a.0 > b.0 {
            range = b.0 + 1..a.0;
        } else {
            range = a.0 + 1..b.0;
        }
        for x in range {
            grid[b.1][x] = Pixel::LineH;
        }
    } else if a.0 < b.0 {
        if a.1 < b.1 {
            // 45-L
            for i in 1..(b.0 - a.0) {
                grid[a.1 + i][a.0 + i] = Pixel::Line45L;
            }
        } else {
            // 45-R
            for i in 1..(b.0 - a.0) {
                grid[a.1 - i][a.0 + i] = Pixel::Line45R;
            }
        }
    } else {
        // 45
        if a.1 < b.1 {
            // 45-R
            for i in 1..(a.0 - b.0) {
                grid[b.1 - i][b.0 + i] = Pixel::Line45R;
            }
        } else {
            // 45-L
            for i in 1..(a.0 - b.0) {
                grid[b.1 + i][b.0 + i] = Pixel::Line45L;
            }
        }
    }
}

fn flood_fill(
    queue: &mut VecDeque<(usize, usize)>,
    grid: &mut Vec<Vec<Pixel>>,
    n: usize,
    m: usize,
) {
    while queue.len() > 0 {
        let (x, y) = queue.pop_front().expect("tried filling with empty queue");
        match grid[y][x] {
            Pixel::Outside => grid[y][x] = Pixel::Inside,
            _ => continue,
        }
        if y < n - 1 {
            queue.push_back((x, y + 1));
        }
        if y > 0 {
            queue.push_back((x, y - 1));
        }
        if x < m - 1 {
            queue.push_back((x + 1, y));
        }
        if x > 0 {
            queue.push_back((x - 1, y));
        }
    }
}

// TODO: Pre-calculate vec of is_inside for entire row (if needed)
fn is_inside(i_start: usize, rest_of_line: &Vec<Pixel>) -> bool {
    let mut intersections: usize = 0;
    let mut inside_wall = false;
    for i in i_start..rest_of_line.len() {
        let el = &rest_of_line[i];
        let is_wall = match el {
            Pixel::Inside => false,
            Pixel::Outside => false,
            Pixel::Point => false, // Prevents glitches at vertices
            _ => true,
        };
        if is_wall && !inside_wall {
            intersections += 1;
        }
        inside_wall = is_wall;
    }
    intersections % 2 != 0
}

fn main() {
    // Input
    let mut nmk = String::new();
    io::stdin()
        .read_line(&mut nmk)
        .expect("failed to read line");
    let mut nmk = nmk.split_ascii_whitespace();
    let n = read_next(&mut nmk);
    let m = read_next(&mut nmk);
    let k = read_next(&mut nmk);

    let mut xys: Vec<(usize, usize)> = Vec::with_capacity(k); // Is this required?
    let mut grid: Vec<Vec<Pixel>> = vec![vec![Pixel::Outside; m]; n];
    // Lines
    for i in 0..k {
        let mut xy = String::new();
        io::stdin().read_line(&mut xy).expect("failed to read line");
        let mut xy = xy.split_ascii_whitespace();
        let y = read_next(&mut xy) - 1;
        let x = read_next(&mut xy) - 1;
        let b = (x, y);
        xys.push(b);
        grid[y][x] = Pixel::Point;
        if i > 0 {
            let a = xys[i - 1];
            draw_line(a, b, &mut grid);
        }
    }
    draw_line(xys[xys.len() - 1], xys[0], &mut grid);

    // Find a point inside the drawing and initiate flood fill
    for y in 0..n {
        for x in 0..m {
            if grid[y][x] == Pixel::Outside && is_inside(x, &grid[y]) {
                flood_fill(
                    &mut VecDeque::from([(x, y)]),
                    &mut grid,
                    n,
                    m,
                );
                //grid[y][x] = Pixel::Inside; // Ideal
            }
        }
    }

    // Print output
    for line in grid {
        for pixel in line {
            match pixel {
                Pixel::Inside => print!("#"),
                Pixel::Outside => print!("."),
                Pixel::LineH => print!("="),
                Pixel::LineV => print!("|"),
                Pixel::Line45L => print!("\\"),
                Pixel::Line45R => print!("/"),
                Pixel::Point => print!("*"),
            }
        }
        println!();
    }
}

Test 1 (public)

Verdict: ACCEPTED

Test 2 (public)

Verdict: ACCEPTED

Test 3 (public)

Verdict: ACCEPTED

Test 4 (public)

Verdict: ACCEPTED

Test 5 (public)

Verdict: ACCEPTED

Test 6 (public)

Verdict: ACCEPTED

Test 7 (public)

Verdict: ACCEPTED

Test 8 (public)

Verdict: ACCEPTED

Test 9 (public)

Verdict: ACCEPTED

Test 10 (public)

Verdict: ACCEPTED