bouzuya.hatenablog.com

ぼうずやのにっき

bbn 0.37.0 をつくった / 的あて (第五回 アルゴリズム実技検定:K問題) を解いた

bouzuya/rust-sandbox bbn 0.37.0 をつくった。

bbn view コマンドの引数として week date を取れるようにした。ぼくは 2023-W27-4 のような week date を使うことが多いので、その形式を取れると便利だなと思って変更した。

structopt → clap のアップデートも入れている。他にも古い点がたくさんあるのだけど今回は対応しないことにした。

use proconio::{input, marker::Chars};

fn main() {
    input! {
        s: [Chars; 4],
    }

    let (h, w) = (4, 4);
    let to_bit = |i: usize, j: usize| -> usize { 1 << (i * w + j) };
    let grid = {
        let mut grid = 0_usize;
        for i in 0..h {
            for j in 0..w {
                if s[i][j] == '#' {
                    grid |= to_bit(i, j);
                }
            }
        }
        grid
    };

    let mut dp = vec![std::f64::MAX; 1 << (h * w)];
    dp[0] = 0_f64;
    for s in 0..(1 << (h * w)) {
        for i in 0..h {
            for j in 0..w {
                let mut ps = vec![];

                let dir = vec![(-1, 0), (0, -1), (0, 0), (0, 1), (1, 0)];
                for (dr, dc) in dir.iter().copied() {
                    let (nr, nc) = (i as i64 + dr, j as i64 + dc);
                    if !(0..h as i64).contains(&nr) || !(0..w as i64).contains(&nc) {
                        continue;
                    }
                    let (nr, nc) = (nr as usize, nc as usize);
                    if (s & to_bit(nr, nc)) == 0 {
                        continue;
                    }

                    ps.push(s ^ to_bit(nr, nc));
                }

                if ps.is_empty() {
                    continue;
                }

                dp[s] = dp[s].min(
                    ps.iter().copied().map(|p| dp[p]).sum::<f64>() / ps.len() as f64
                        + dir.len() as f64 / ps.len() as f64,
                );
            }
        }
    }

    let ans = dp[grid];
    println!("{}", ans);
}

今日のコミット。