仕事で東京へ。これは帰りの新幹線にて記述。自分で思った以上に疲れていることに↓の問題を解いていて気づいた。

• PAST #2 H - 1-9 Grid (第二回 アルゴリズム実技検定 H問題) https://atcoder.jp/contests/past202004-open/tasks/past202004_h
  • https://atcoder.jp/contests/past202004-open/submissions/40809593
  • 1 から 9 までの数字を順に通って S から G まで行く
  • 途中に大きい数などを踏んでも良い
  • 例えば S -> 1 -> 3 -> 2 は 2 まで通ったことになる
  • S から各 1 までの最短距離、各 1 から各 2 への最短距離……と求めていき G までの最短距離を求める
  • 数字がないなど到達不能のときは -1 を出力して終了する

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

fn main() {
    input! {
        n: usize,
        m: usize,
        a: [Chars; n],
    }
    let mut pos = vec![vec![]; 10 + 1];
    for i in 0..n {
        for j in 0..m {
            match a[i][j] {
                'S' => pos[0].push((i, j)),
                'G' => pos[10].push((i, j)),
                '1'..='9' => pos[(a[i][j] as u8 - b'0') as usize].push((i, j)),
                _ => unreachable!(),
            }
        }
    }

    let dist = |p: (usize, usize), q: (usize, usize)| -> i64 {
        (p.0 as i64 - q.0 as i64).abs() + (p.1 as i64 - q.1 as i64).abs()
    };
    let mut dp = vec![HashMap::new(); 10 + 1];
    dp[0].insert(pos[0][0], 0);
    for i in 0..10 {
        let keys = dp[i].keys().cloned().collect::<Vec<_>>();
        for p in keys {
            let d_p = *dp[i].get(&p).unwrap();
            for q in pos[i + 1].iter().copied() {
                let d_q = d_p + dist(q, p);
                let entry = dp[i + 1].entry(q).or_insert(d_q);
                if *entry > d_q {
                    *entry = d_q;
                }
            }
        }
    }

    if dp[10].is_empty() {
        println!("-1");
        return;
    }
    let ans = dp[10].iter().next().unwrap().1;
    println!("{}", ans);
}

今日のコミット。

• tsukota 2 commits
  • Add components/index
  • Extract useCredential hook
• rust-atcoder 1 commit
  • pastbook1 past #2 h