AtCoder Beginner Contest 358 F

https://atcoder.jp/contests/abc358/tasks/abc358_f

基本、Kの最小は高さで、これに偶数を足した数ならOKです。ただ、高さが1のときは別です。
高さが偶数なら、適当に左に行って帰ってくるを繰り返すだけなので簡単です。
奇数だとだいぶややこしくなります。

// Easiest Maze
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Maze ////////////////////

type Point = (usize, usize);

struct Maze {
    H: usize,
    W: usize,
    n: usize,
    path: Vec<Point>
}

impl Maze {
    fn walk(&mut self) -> bool {
        if self.n < self.H || (self.n - self.H) % 2 != 0 {
            return false
        }
        
        if self.W == 1 {
            self.walk_W1()
        }
        else if self.H == 1 {
            return self.walk_H1()
        }
        else if self.H % 2 == 0 {
            self.walk_even_H();
        }
        else {
            self.walk_odd_H();
        }
        
        true
    }
    
    fn walk_W1(&mut self) {
        for x in 0..self.H {
            self.path.push((x, 0))
        }
    }
    
    fn walk_H1(&mut self) -> bool {
        self.path.push((0, self.W-1));
        self.n == 1
    }
    
    fn walk_even_H(&mut self) -> bool {
        //  4  3  2  1
        //  5  6  7  8
        // 12 11 10  9
        // 13 14 15 16
        let b = self.n >= self.H && (self.n - self.H) % 2 == 0;
        let ds = Maze::distribute(self.n/2, self.H/2);
        for x in (0..self.H).step_by(2) {
            for i in 0..ds[x/2] {
                self.path.push((x, self.W-i-1))
            }
            for i in (0..ds[x/2]).rev() {
                self.path.push((x+1, self.W-i-1))
            }
        }
        b
    }
    
    fn walk_odd_H(&mut self) {
        if self.n <= (self.H - 1) * self.W + 1 {
            self.walk_small()
        }
        else if self.W % 2 == 1 {
            self.walk_odd_W()
        }
        else {
            self.walk_even_W()
        }
    }
    
    fn walk_small(&mut self) {
        let ds = Maze::distribute(self.n / 2, (self.H - 1) / 2);
        for x in (0..self.H-2).step_by(2) {
            for i in 0..ds[x/2] {
                self.path.push((x, self.W-i-1))
            }
            for i in (0..ds[x/2]).rev() {
                self.path.push((x+1, self.W-i-1))
            }
        }
        self.path.push((self.H-1, self.W-1))
    }
    
    fn walk_odd_W(&mut self) {
        // 3 2 1
        // 4 7 8
        // 5 6 9
        let n = (self.n - self.W - self.H + 1) / 2;
        let ds = Maze::distribute(n, (self.W - 1) / 2);
        for y in (0..self.W).rev() {
            self.path.push((0, y))
        }
        for x in 1..self.H {
            self.path.push((x, 0))
        }
        for y in (1..self.W).step_by(2) {
            for x in (self.H-ds[y/2]..self.H).rev() {
                self.path.push((x, y))
            }
            for x in self.H-ds[y/2]..self.H {
                self.path.push((x, y+1))
            }
        }
    }
    
    fn walk_even_W(&mut self) {
        //  4  3  2  1
        //  5  6  7  8
        // 12 11 10  9
        // 13 16 17
        // 14 15 18 19
        if self.n >= self.H * self.W - self.H + 1 {
            let delta = self.H * self.W - self.n;
            for x in 0..self.H-delta-1 {
                if x % 2 == 0 {
                    for y in (0..self.W).rev() {
                        self.path.push((x, y))
                    }
                }
                else {
                    for y in 0..self.W {
                        self.path.push((x, y))
                    }
                }
            }
            
            for y in 0..self.W-1 {
                if y % 2 == 0 {
                    for x in self.H-delta-1..self.H {
                        self.path.push((x, y))
                    }
                }
                else {
                    for x in (self.H-delta-1..self.H).rev() {
                        self.path.push((x, y))
                    }
                }
            }
            self.path.push((self.H-1, self.W-1))
        }
        else {
            let res = self.n - self.H + self.W;
            let ds = Maze::distribute(res / 2, self.W / 2 - 1);
            for y in (0..self.W).rev() {
                self.path.push((0, y))
            }
            for x in 1..self.H {
                self.path.push((x, 0))
            }
            for y in 1..self.W-1 {
                if y % 2 == 1 {
                    for x in (ds[y/2]..self.H).rev() {
                        self.path.push((x, y))
                    }
                }
                else {
                    for x in ds[y/2-1]..self.H {
                        self.path.push((x, y))
                    }
                }
            }
            self.path.push((self.H-1, self.W-1))
        }
    }
    
    // divide n into m parts
    fn distribute(n: usize, m: usize) -> Vec<usize> {
        let q = n / m;
        let r = n % m;
        (0..m).map(|i| if i < r { q + 1 } else { q }).collect::<Vec<usize>>()
    }
    
    fn print(&self) {
        let H = self.H * 2 + 1;
        let W = self.W * 2 + 1;
        let mut css: Vec<Vec<char>> = vec![vec!['+'; W]; H];
        css[0][W-2] = 'S';
        for x in (1..H).step_by(2) {
            for y in (1..W).step_by(2) {
                css[x][y] = 'o'
            }
        }
        for x in (1..H).step_by(2) {
            for y in (2..W-1).step_by(2) {
                css[x][y] = '|'
            }
        }
        for x in (2..H-1).step_by(2) {
            for y in (1..W).step_by(2) {
                css[x][y] = '-'
            }
        }
        
        for window in self.path.windows(2) {
            let (x1, y1) = &window[0];
            let (x2, y2) = &window[1];
            if *x1 == *x2 {
                if *y1 + 1 == *y2 {
                    css[x1*2+1][y2*2] = '.'
                }
                else {
                    css[x1*2+1][y1*2] = '.'
                }
            }
            else {
                if *x1 + 1 == *x2 {
                    css[x2*2][y1*2+1] = '.'
                }
                else {
                    css[x1*2][y1*2+1] = '.'
                }
            }
        }
        
        css[H-1][W-2] = 'G';
        
        for cs in css.into_iter() {
            println!("{}", cs.into_iter().collect::<String>())
        }
    }
    
    fn create(H: usize, W: usize, n: usize) -> Maze {
        let path: Vec<Point> = vec![];
        Maze { H, W, n, path }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, usize, usize) {
    let v: Vec<usize> = read_vec();
    (v[0], v[1], v[2])
}

fn F(N: usize, M: usize, K: usize) {
    let mut maze = Maze::create(N, M, K);
    if !maze.walk() {
        println!("No");
    }
    else {
        println!("Yes");
        maze.print()
    }
}

fn main() {
    let (N, M, K) = read_input();
    F(N, M, K)
}