https://atcoder.jp/contests/abc272/tasks/abc272_d
どこへ進めるかはナイーブに実装しても十分に間に合いますね。
何歩で行けるかはQueueを使えばよいですが、RustではVecDequeというcollectionを使うようです。
// Root M Leaper #![allow(non_snake_case)] use std::ops::Add; use std::collections::VecDeque; 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 read_input() -> (i32, i32) { let v = read_vec(); (v[0], v[1]) } #[derive(Clone, Copy)] #[derive(Debug)] struct Point { x: i32, y: i32, } impl Add for Point { type Output = Self; fn add(self, other: Self) -> Self { Self { x: self.x + other.x, y: self.y + other.y } } } // rotate 90 degrees fn rotate(dir: &Point) -> Point { Point { x: -dir.y, y: dir.x } } // reflect on x + y = 0 fn reflect(dir: &Point) -> Point { Point { x: dir.y, y: dir.x } } fn expand_dirs(dir: Point) -> Vec<Point> { let mut dirs = Vec::<Point>::new(); dirs.push(dir); for i in 0..3 { dirs.push(rotate(&dirs[i])) } if dir.x != dir.y && dir.x != 0 && dir.y != 0 { for i in 0..4 { dirs.push(reflect(&dirs[i])) } } dirs } fn find_movable_dirs(M: i32) -> Vec<Point> { let mut dirs = Vec::<Point>::new(); for x in 0.. { let y = ((M - x*x) as f64).sqrt().floor() as i32; if y < x { break; } if x*x + y*y == M { dirs.push(Point { x, y }); } } dirs.into_iter().map(|dir| expand_dirs(dir)). flatten().collect::<Vec<Point>>() } fn make_table(N: i32, M: i32) -> Vec<Vec<i32>> { let mut table: Vec<Vec<i32>> = (0..N).map(|_| (0..N).map(|_| -1).collect()).collect(); table[0][0] = 0; let dirs = find_movable_dirs(M); let mut queue = VecDeque::<Point>::new(); queue.push_back(Point { x: 0, y: 0 }); while queue.len() > 0 { let pt0 = queue.pop_front().unwrap(); let x0 = pt0.x as usize; let y0 = pt0.y as usize; for dir in dirs.iter() { let pt = pt0 + *dir; let x = pt.x as usize; let y = pt.y as usize; if 0 <= pt.x && pt.x < N && 0 <= pt.y && pt.y < N && table[x][y] == -1 { table[x][y] = table[x0][y0] + 1; queue.push_back(pt) } } } table } fn print_table(table: Vec<Vec<i32>>) { for v in table.into_iter() { println!("{}", v.iter().map(|n| n.to_string()). collect::<Vec<String>>().join(" ")) } } fn f(N: i32, M: i32) { let table = make_table(N, M); print_table(table) } fn main() { let v = read_input(); f(v.0, v.1) }