Module d

Expand description

§ABC 405 D - Escape Route

refs: https://atcoder.jp/contests/abc405/tasks/abc405_d

幅優先探索するだけ.

use std::collections::VecDeque;

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

fn main() {
    input! {
        h: usize, w: usize,
        mut s: [Chars; h],
    }

    let mut q = VecDeque::new();

    for (x, row) in s.iter().enumerate() {
        for (y, &cell) in row.iter().enumerate() {
            if cell == 'E' {
                q.push_back((x, y, 'E'));
            }
        }
    }

    while let Some((x, y, c)) = q.pop_front() {
        if s[x][y] == '.' {
            s[x][y] = c;
        } else if s[x][y] != 'E' {
            continue;
        }

        if x > 0 && s[x - 1][y] == '.' {
            q.push_back((x - 1, y, 'v'));
        }
        if x < h - 1 && s[x + 1][y] == '.' {
            q.push_back((x + 1, y, '^'));
        }
        if y > 0 && s[x][y - 1] == '.' {
            q.push_back((x, y - 1, '>'));
        }
        if y < w - 1 && s[x][y + 1] == '.' {
            q.push_back((x, y + 1, '<'));
        }
    }

    println!(
        "{}",
        s.iter()
            .map(|row| row.iter().collect::<String>())
            .collect::<Vec<_>>()
            .join("\n")
    )
}