AGC 014 C - Closed Rooms

問題

atcoder.jp

解法

もし、魔法の操作の順序が入れ替わっていて、魔法が「Kこの部屋を選んで解放し、その後、K回移動する」という操作だったら、移動しながら部屋を開けていけば良いので、非常に単純なBFSになる。ここに落とし込むために、操作を以下のように言い換える。

• 1回目のみ「K回移動する。しまっている部屋には入れない」
• 2回目以降「K回移動する。どの部屋も入り放題」

もし1回目の操作、すなわちKステップ以内のゴールできれば1を出力する。そうでない場合、Kステップで到達できる点を視点として距離をリセットし、単純にBFSする。

コード

use std::collections::VecDeque;

const INF: u64 = 1e15 as u64;

const DX: [i64; 4] = [0, 0, 1, -1];
const DY: [i64; 4] = [1, -1, 0, 0];

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let h: usize = sc.read();
    let w: usize = sc.read();
    let k: u64 = sc.read();
    let s: Vec<Vec<char>> = (0..h).map(|_| sc.chars()).collect();
    let mut dist = vec![vec![INF; w]; h];
    let mut q = VecDeque::new();
    for i in 0..h {
        for j in 0..w {
            if s[i][j] == 'S' {
                dist[i][j] = 0;
                q.push_back((i, j));
            }
        }
    }

    while let Some((i, j)) = q.pop_front() {
        if i == 0 || j == 0 || i == h - 1 || j == w - 1 {
            println!("1");
            return;
        }
        for d in 0..4 {
            let ni = (i as i64) + DX[d];
            let nj = (j as i64) + DY[d];
            if ni < 0 || nj < 0 || ni >= (h as i64) || nj >= (w as i64) {
                continue;
            }
            let ni = ni as usize;
            let nj = nj as usize;
            if dist[ni][nj] > dist[i][j] + 1 && s[ni][nj] != '#' && dist[i][j] + 1 <= k {
                dist[ni][nj] = dist[i][j] + 1;
                q.push_back((ni, nj));
            }
        }
    }

    for i in 0..h {
        for j in 0..w {
            if dist[i][j] != INF {
                dist[i][j] = k;
                q.push_back((i, j));
            }
        }
    }

    while let Some((i, j)) = q.pop_front() {
        if i == 0 || j == 0 || i == h - 1 || j == w - 1 {
            println!("{}", (dist[i][j] + k - 1) / k);
            return;
        }
        for d in 0..4 {
            let ni = (i as i64) + DX[d];
            let nj = (j as i64) + DY[d];
            if ni < 0 || nj < 0 || ni >= (h as i64) || nj >= (w as i64) {
                continue;
            }
            let ni = ni as usize;
            let nj = nj as usize;
            if dist[ni][nj] > dist[i][j] + 1 {
                dist[ni][nj] = dist[i][j] + 1;
                q.push_back((ni, nj));
            }
        }
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}