AtCoder Beginner Contest 337 D

https://atcoder.jp/contests/abc337/tasks/abc337_d

1行ごとにDPで最小値を求めます。

// Cheating Gomoku Narabe
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// 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()
}


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

type Table = Vec<Vec<char>>;

fn read_input() -> (usize, Vec<String>) {
    let v: Vec<usize> = read_vec();
    let (H, K) = (v[0], v[2]);
    let S: Vec<String> = (0..H).map(|_| read::<String>()).collect();
    (K, S)
}

fn transpose(table: &Table) -> Table {
    let H = table.len();
    let W = table[0].len();
    (0..W).map(|j| (0..H).map(|i| table[i][j]).collect::<Vec<char>>()).
                                                        collect::<Table>()
}

fn get_min_plays(num_x: usize, num_o: usize, K: usize) -> usize {
    if num_x == 0 { K - num_o } else { K + 1 }
}

fn find_min_plays_each(v: &Vec<char>, K: usize) -> usize {
    let mut num_x = (0..K).filter(|&j| v[j] == 'x').count();
    let mut num_o = (0..K).filter(|&j| v[j] == 'o').count();
    let mut min_plays = get_min_plays(num_x, num_o, K);
    for j in K..v.len() {
        match v[j-K] {
            'x' => num_x -= 1,
            'o' => num_o -= 1,
            _   => ()
        }
        match v[j] {
            'x' => num_x += 1,
            'o' => num_o += 1,
            _   => ()
        }
        min_plays = min(min_plays, get_min_plays(num_x, num_o, K))
    }
    min_plays
}

fn find_min_plays(table: &Table, K: usize) -> usize {
    if table[0].len() < K {
        return K + 1
    }
    
    let mut min_plays = K + 1;
    for v in table.iter() {
        min_plays = min(min_plays, find_min_plays_each(v, K))
    }
    min_plays
}

fn F(K: usize, S: Vec<String>) -> i32 {
    let table: Table = S.into_iter().
                    map(|s| s.chars().collect::<Vec<char>>()).collect();
    let min_plays1 = find_min_plays(&table, K);
    let table_t = transpose(&table);
    let min_plays2 = find_min_plays(&table_t, K);
    let min_plays = min(min_plays1, min_plays2);
    if min_plays == K + 1 { -1 } else { min_plays as i32 }
}

fn main() {
    let (K, S) = read_input();
    println!("{}", F(K, S))
}