Module d

ABC 398 D - Bonfire

refs: https://atcoder.jp/contests/abc398/tasks/abc398_d

すべての煙の位置を求めるのは困難なため, 別の方法で考える必要がある. 問題文では高橋くんを固定して煙を移動しているように記述されているが, 高橋くんが移動し煙が増えているというように読み替えることができる.

整理して読み替えると,

• 高橋くんは座標 $(R, C)$ から移動を開始する
• 煙の発生源は $(0, 0)$ の座標から高橋くんと同様の移動をする
• 煙は移動しない
• 移動方向は次の指定に従う
  • N: $(x, y)$ から $(x + 1, y)$
  • W: $(x, y)$ から $(x, y + 1)$
  • S: $(x, y)$ から $(x - 1, y)$
  • E: $(x, y)$ から $(x, y - 1)$

高橋くんが煙に突っ込んでいった場合に 1, そうでない場合は 0 を出力すればよい. この方式ならば, 高橋くんと煙の発生源の現在の座標と, 過去煙の発生した座標が記録されていれば計算可能.

use std::collections::HashSet;

use proconio::input;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Point {
    x: i32,
    y: i32,
}

impl Point {
    fn new(x: i32, y: i32) -> Self {
        Self { x, y }
    }

    fn next(&mut self, c: char) {
        match c {
            // Reverse the direction
            'N' => self.x += 1,
            'W' => self.y += 1,
            'S' => self.x -= 1,
            'E' => self.y -= 1,
            _ => panic!("Invalid Input"),
        }
    }
}

fn main() {
    input! {
        _: i32, r: i32, c: i32,
        s: String,
    }

    let mut human = Point::new(r, c);
    let mut fire = Point::new(0, 0);

    let mut smoke_point = HashSet::new();
    smoke_point.insert(fire);

    for c in s.chars() {
        human.next(c);
        fire.next(c);

        smoke_point.insert(fire);
        if smoke_point.contains(&human) {
            print!("1");
        } else {
            print!("0");
        }
    }
    println!();
}