AtCoder Beginner Contest 348 D

https://atcoder.jp/contests/abc348/tasks/abc348_d

ふつうにQueueを使ってたどればよいです。

// Medicines on Grid
#![allow(non_snake_case)]

use std::collections::VecDeque;


//////////////////// 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" } else { "No" }.to_string()
}


//////////////////// Table ////////////////////

type Point = (usize, usize);

struct Table {
    H: usize,
    W: usize,
    cells: Vec<Vec<(char, i32)>>
}

impl Table {
    fn is_obstacle(&self, pt: Point) -> bool {
        self.cells[pt.0][pt.1].0 == '#'
    }
    
    fn get_medicine(&self, pt: Point) -> i32 {
        self.cells[pt.0][pt.1].1
    }
    
    fn nexts(&self, pt: Point) -> Vec<Point> {
        let (x, y) = pt;
        let mut pts: Vec<Point> = vec![];
        if x > 0 && !self.is_obstacle((x-1, y)) {
            pts.push((x-1, y))
        }
        if x < self.H - 1 && !self.is_obstacle((x+1, y)) {
            pts.push((x+1, y))
        }
        if y > 0 && !self.is_obstacle((x, y-1)) {
            pts.push((x, y-1))
        }
        if y < self.W - 1 && !self.is_obstacle((x, y+1)) {
            pts.push((x, y+1))
        }
        pts
    }
    
    fn find(&self, c: char) -> Option<Point> {
        for (x, v) in self.cells.iter().enumerate() {
            for (y, c1) in v.iter().enumerate() {
                if c1.0 == c {
                    return Some((x, y))
                }
            }
        }
        None
    }
    
    fn read() -> Table {
        let v: Vec<usize> = read_vec();
        let (H, W) = (v[0], v[1]);
        let mut cells: Vec<Vec<(char, i32)>> = (0..H).map(|_| 
                                                        read::<String>().
                                                        chars().
                                                        map(|c| (c, 0)).
                                                        collect::<Vec<_>>()
                                                    ).collect();
        
        let N: usize = read();
        for _ in 0..N {
            let w: Vec<usize> = read_vec();
            let (R, C) = (w[0]-1, w[1]-1);
            let E = w[2] as i32;
            cells[R][C].1 = E
        }
        
        Table { H, W, cells }
    }
}


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

fn F(table: Table) -> bool {
    let mut energies = vec![vec![0; table.W]; table.H];
    let mut queue: VecDeque<(Point, i32)> = VecDeque::new();
    let S = table.find('S').unwrap();
    let T = table.find('T').unwrap();
    queue.push_back((S, table.get_medicine(S)));
    while let Some((pt, energy)) = queue.pop_front() {
        if energy == 0 || energy < energies[pt.0][pt.1] {
            continue
        }
        for pt1 in table.nexts(pt).into_iter() {
            if pt1 == T {
                return true
            }
            let m = table.get_medicine(pt1);
            let e = std::cmp::max(m, energy - 1);
            if e > energies[pt1.0][pt1.1] {
                energies[pt1.0][pt1.1] = e;
                queue.push_back((pt1, e))
            }
        }
    }
    false
}

fn main() {
    let table = Table::read();
    println!("{}", YesNo(F(table)))
}