AtCoder Beginner Contest 308 D

https://atcoder.jp/contests/abc308/tasks/abc308_d

グラフにして、最初と最後が繋がっているかを調べます。

// Snuke Maze
#![allow(non_snake_case)]

use std::ops::{Add, Sub};
use std::collections::HashMap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn YesNo(b: bool) -> String {
    return if b { "Yes".to_string() } else { "No".to_string() }
}


//////////////////// Graph ////////////////////

type Node = usize;
type Graph = Vec<Vec<usize>>;

fn is_connected(orig: Node, dest: Node, graph: Graph) -> bool {
    let N = graph.len();
    let mut stack: Vec<Node> = vec![orig];
    let mut visited: Vec<bool> = vec![false; N];
    visited[orig] = true;
    while let Some(v) = stack.pop() {
        for &u in graph[v].iter() {
            if u == dest {
                return true
            }
            else if !visited[u] {
                visited[u] = true;
                stack.push(u)
            }
        }
    }
    false
}


//////////////////// Point ////////////////////

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

impl Add for Point {
    type Output = Self;
    
    fn add(self, other: Self) -> Self {
        Self { x: self.x + other.x, y: self.y + other.y }
    }
}

impl Sub for Point {
    type Output = Self;
    
    fn sub(self, other: Self) -> Self {
        Self { x: self.x - other.x, y: self.y - other.y }
    }
}

impl Point {
    fn new(x: i64, y: i64) -> Point {
        Point { x, y }
    }
    
    fn to_usize(&self, W: usize) -> usize {
        (self.x as usize) * W + self.y as usize
    }
}


//////////////////// process ////////////////////

fn read_input() -> Vec<String> {
    let v: Vec<usize> = read_vec();
    let H = v[0];
    let S: Vec<String> = (0..H).map(|_| read()).collect();
    S
}

fn make_graph(S: Vec<String>) -> Graph {
    
    let nexts = "snuke".to_string().chars().
                        zip("nukes".to_string().chars()).
                        collect::<HashMap<char, char>>();
    let dirs: Vec<Point> = vec![Point::new(1, 0), Point::new(0, 1),
                                Point::new(-1, 0), Point::new(0, -1)];
    let H = S.len();
    let W = S[0].len();
    let is_inner = |pt: Point| {
        0 <= pt.x && pt.x < H as i64 && 0 <= pt.y && pt.y < W as i64
    };
    
    let points =
        S.into_iter().enumerate().
        map(|(i, s)| s.chars().enumerate().
                    map(move |(j, c)| (Point::new(i as i64, j as i64), c)).
                    collect::<Vec<(Point, char)>>()).
        flatten().collect::<HashMap<Point, char>>();
    
    let mut graph: Graph = vec![vec![]; H * W];
    for (pt, c) in points.iter() {
        let next_c = nexts.get(&c);
        if next_c.is_none() {
            continue
        }
        for dir in dirs.iter() {
            let neighbor = *pt + *dir;
            if !is_inner(neighbor) {
                continue
            }
            else if points.get(&neighbor) == next_c {
                graph[pt.to_usize(W)].push(neighbor.to_usize(W))
            }
        }
    }
    graph
}

fn f(S: Vec<String>) -> bool {
    let H = S.len();
    let W = S[0].len();
    let graph = make_graph(S);
    is_connected(0, H*W-1, graph)
}


//////////////////// main ////////////////////

fn main() {
    let S = read_input();
    println!("{}", YesNo(f(S)))
}