AtCoder Beginner Contest 387 D

https://atcoder.jp/contests/abc387/tasks/abc387_d

幅優先探索すればいいのですが、同じマスでも上下から入った場合と左右から入った場合で分けるとよいです。

// Snaky Walk
#![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()
}


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

type Point = (usize, usize, usize);
type Maze = Vec<Vec<char>>;

fn create_maze(S: Vec<String>) -> Maze {
    S.into_iter().map(|s| s.chars().collect::<Vec<_>>()).collect::<Vec<_>>()
}

fn find_start(maze: &Vec<Vec<char>>) -> (usize, usize) {
    let H = maze.len();
    let W = maze[0].len();
    for x in 0..H {
        for y in 0..W {
            if maze[x][y] == 'S' {
                return (x, y)
            }
        }
    }
    return (H, W)
}

fn neighbors(pt0: Point, maze: &Maze) -> Vec<Point> {
    let H = maze.len();
    let W = maze[0].len();
    let mut neighs: Vec<Point> = vec![];
    let (x, y, dir) = pt0;
    if dir == 0 {
        if y > 0 && maze[x][y-1] != '#' {
            neighs.push((x, y-1, 1))
        }
        if y < W-1 && maze[x][y+1] != '#' {
            neighs.push((x, y+1, 1))
        }
    }
    else {
        if x > 0 && maze[x-1][y] != '#' {
            neighs.push((x-1, y, 0))
        }
        if x < H-1 && maze[x+1][y] != '#' {
            neighs.push((x+1, y, 0))
        }
    }
    neighs
}

fn get_dist(pt: Point, dist: &Vec<Vec<Vec<i32>>>) -> i32 {
    dist[pt.0][pt.1][pt.2]
}

fn set_dist(pt: Point, d: i32, dist: &mut Vec<Vec<Vec<i32>>>) {
    dist[pt.0][pt.1][pt.2] = d
}

fn F(S: Vec<String>) -> i32 {
    let maze = create_maze(S);
    let H = maze.len();
    let W = maze[0].len();
    let mut queue = VecDeque::<Point>::new();
    let mut dist: Vec<Vec<Vec<i32>>> = vec![vec![vec![-1; 2]; W]; H];
    let S = find_start(&maze);
    let S0 = (S.0, S.1, 0);
    let S1 = (S.0, S.1, 1);
    queue.push_back(S0);
    queue.push_back(S1);
    set_dist(S0, 0, &mut dist);     // 上下から
    set_dist(S1, 0, &mut dist);     // 左右から
    while let Some(pt) = queue.pop_front() {
        for pt1 in neighbors(pt, &maze) {
            if get_dist(pt1, &dist) == -1 {
                set_dist(pt1, get_dist(pt, &dist) + 1, &mut dist);
                if maze[pt1.0][pt1.1] == 'G' {
                    return get_dist(pt1, &dist)
                }
                queue.push_back(pt1)
            }
        }
    }
    -1
}

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