2023-02-07 PAST #11 の I を解いた
PAST #11 : 第11回 アルゴリズム実技検定 過去問 の I を解いた。
- I - お片付け
https://atcoder.jp/contests/past202206-open/tasks/past202206_i
- 提出: https://atcoder.jp/contests/past202206-open/submissions/38695780
- 幅優先探索で最短経路を求める問題に荷物が追加されたもの
- 通常は開始位置から各位置までの最短距離を求めていけば良い
- この問題では荷物とすぬけ君の 2 つの位置ごとに開始位置からの最短距離 (行動回数) を求めていけば良い
H, W <= 50
なのでH * W * H * W <= 6,250,000
で収まる・間に合う
use std::collections::VecDeque;
use proconio::{input, marker::Chars};
fn main() {
input! {
h: usize,
w: usize,
s: [Chars; h],
};
let mut p_a = (0, 0);
let mut p_g = (0, 0);
let mut p_s = (0, 0);
for i in 0..h {
for j in 0..w {
match s[i][j] {
'a' => p_a = (i, j),
'g' => p_g = (i, j),
's' => p_s = (i, j),
_ => {}
}
}
}
let inf = 1_usize << 60;
let mut dist = vec![vec![vec![vec![inf; w]; h]; w]; h];
let mut deque = VecDeque::new();
dist[p_a.0][p_a.1][p_s.0][p_s.1] = 0_usize;
deque.push_back((p_a.0, p_a.1, p_s.0, p_s.1));
while let Some((r1, c1, r2, c2)) = deque.pop_front() {
let d = dist[r1][c1][r2][c2];
let dir = vec![(-1, 0), (0, -1), (0, 1), (1, 0)];
for (dr, dc) in dir {
let (nr, nc) = (r2 as i64 + dr, c2 as i64 + dc);
if !(0..h as i64).contains(&nr) || !(0..w as i64).contains(&nc) {
continue;
}
let (nr2, nc2) = (nr as usize, nc as usize);
if nr2 == r1 && nc2 == c1 {
let (nr1, nc1) = (nr2 as i64 + dr, nc2 as i64 + dc);
if !(0..h as i64).contains(&nr1) || !(0..w as i64).contains(&nc1) {
continue;
}
let (nr1, nc1) = (nr1 as usize, nc1 as usize);
if dist[nr1][nc1][nr2][nc2] == inf && s[nr1][nc1] != '#' {
dist[nr1][nc1][nr2][nc2] = d + 1;
deque.push_back((nr1, nc1, nr2, nc2));
}
} else if dist[r1][c1][nr2][nc2] == inf && s[nr2][nc2] != '#' {
dist[r1][c1][nr2][nc2] = d + 1;
deque.push_back((r1, c1, nr2, nc2));
}
}
}
let mut min = inf;
for i in 0..h {
for j in 0..w {
min = min.min(dist[p_g.0][p_g.1][i][j]);
}
}
let ans = min;
if ans == inf {
println!("-1");
} else {
println!("{}", ans);
}
}
疲れている。早く寝て早く起きよう。
今日のコミット。
- rust-sandbox 1 commit
- rust-atcoder 1 commit