熱だけど元気 / PAST #3 G

子どもが熱を出している。……が元気。

---

PAST #3 第三回 アルゴリズム実技検定 過去問

• G - グリッド金移動 https://atcoder.jp/contests/past202005-open/tasks/past202005_g
  • 提出: https://atcoder.jp/contests/past202005-open/submissions/49357122
  • 素朴に BFS で最短経路を求める
  • グリッドの幅・高さの制限についての問題文を間違えて 3WA
  • -200..=200 の範囲に障害物やゴールはあるが、グリッドは無限に広がっているので -201 や 201 へと迂回することがある

use std::collections::{HashMap, HashSet, VecDeque};

use proconio::input;

fn main() {
    input! {
        n: usize,
        capital_x: i64,
        capital_y: i64,
        xy: [(i64, i64); n],
    };

    let inf = 1_usize << 60;

    let ng = xy.into_iter().collect::<HashSet<(i64, i64)>>();
    let mut dist = HashMap::new();
    let mut deque = VecDeque::new();
    deque.push_back(((0_i64, 0_i64), 0_usize));
    dist.insert((0, 0), 0_usize);
    while let Some(((x, y), d)) = deque.pop_front() {
        if d > *dist.get(&(x, y)).unwrap() {
            continue;
        }
        let dir = vec![(1, 1), (0, 1), (-1, 1), (1, 0), (-1, 0), (0, -1)];
        for (dx, dy) in dir {
            let (nx, ny, nd) = (x + dx, y + dy, d + 1);
            if !(-201_i64..=201_i64).contains(&nx) || !(-201_i64..=201_i64).contains(&ny) {
                continue;
            }
            if ng.contains(&(nx, ny)) {
                continue;
            }
            let min = *dist.get(&(nx, ny)).unwrap_or(&inf);
            if nd < min {
                dist.insert((nx, ny), nd);
                deque.push_back(((nx, ny), nd));
            }
        }
    }

    let ans = dist
        .get(&(capital_x, capital_y))
        .map(|x| *x as i64)
        .unwrap_or(-1_i64);
    println!("{}", ans);
}

---

今日のコミット。

• bbna 1 commit
  • Add tests for delete_expo_push_token
• rust-atcoder 1 commit
  • past202005-open g