アルゴリズムと数学 046

https://atcoder.jp/contests/math-and-algorithm/tasks/abc007_3

PointをGenericを使って書くととたんに難しくなりますね。
幅優先探索のQueueは、VecDequeを使います。

// 幅優先探索
#![allow(non_snake_case)]

use std::ops::{Add, Sub};
use std::collections::{VecDeque, HashSet};


//////////////////// 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()
}


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

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

impl<T: std::fmt::Display> Point<T> {
    fn new(x: T, y: T) -> Self {
        Self { x, y }
    }
}

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

impl<T> Sub for Point<T>
    where T: std::ops::Sub<Output = T> + Copy {
    type Output = Self;
    
    fn sub(self, other: Self) -> Self {
        Self { x: self.x - other.x, y: self.y - other.y }
    }
}

impl<T: std::str::FromStr + Copy> Point<T> {
    fn read() -> Point<T> {
        let v: Vec<T> = read_vec();
        Point::<T> { x: v[0], y: v[1] }
    }
}


//////////////////// Maze ////////////////////

struct Maze {
    m: Vec<Vec<char>>
}

impl Maze {
    fn width(&self) -> usize {
        self.m[0].len()
    }
    
    fn height(&self) -> usize {
        self.m.len()
    }
    
    fn is_accessible(&self, x: usize, y: usize) -> bool {
        if x < 0 || x >= self.width() || y < 0 || y >= self.height() {
            false
        }
        else {
            self.m[y][x] == '.'
        }
    }
    
    fn read(R: usize) -> Maze {
        let m = (0..R).map(|_| read::<String>()).
                        map(|s| s.chars().collect::<Vec<char>>()).
                        collect::<Vec<Vec<char>>>();
        Maze { m }
    }
}


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

fn read_input() -> (Maze, Point<i32>, Point<i32>) {
    let v = read_vec();
    let R: usize = v[0];
    let start = Point::<i32>::read() - Point::<i32> { x: 1, y: 1 };
    let goal = Point::<i32>::read() - Point::<i32> { x: 1, y: 1 };
    let maze = Maze::read(R);
    (maze, start, goal)
}

fn is_accessible(pt: Point<i32>, maze: &Maze) -> bool {
    maze.is_accessible(pt.y as usize, pt.x as usize)
}

fn f(maze: Maze, start: Point<i32>, goal: Point<i32>) -> i32 {
    let steps: Vec<Point<i32>> = vec![(1, 0), (0, 1), (-1, 0), (0, -1)].
                iter().map(|(x, y)| Point::<i32>::new(*x, *y)).collect();
    let mut queue = VecDeque::new();
    queue.push_back((start, 0i32));
    let mut visited: HashSet<Point<i32>> = HashSet::new();
    visited.insert(start);
    loop {
        let (pt0, num_steps) = queue.pop_front().unwrap();
        if pt0 == goal {
            return num_steps
        }
        
        for step in steps.iter() {
            let pt = pt0 + *step;
            if is_accessible(pt, &maze) && !visited.contains(&pt) {
                queue.push_back((pt, num_steps + 1));
                visited.insert(pt);
            }
        }
    }
}

fn main() {
    let (maze, start, goal) = read_input();
    println!("{}", f(maze, start, goal))
}