https://atcoder.jp/contests/abc273/tasks/abc273_d
これも行と列で分けて考えることができます。
壁の座標を各行、各列で格納します。
その際に二分探索をするのでソートしますが、HashMapの中のVecをどうソートしていいのか分からなかったので、新たにHashMapを構築しました。
// LRUD Instructions #![allow(non_snake_case)] use std::collections::HashMap; use std::cmp::min; use std::cmp::max; 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() } struct Point { x: i32, y: i32, } fn read_point() -> Point { let v: Vec<i32> = read::<String>().split_whitespace() .map(|e| e.parse().ok().unwrap()).collect(); Point { x: v[1], y: v[0] } } fn read_input() -> (i32, i32, Point, Vec<Point>, Vec<(char, i32)>) { let v = read_vec(); let H: i32 = v[0]; let W: i32 = v[1]; let pt0 = Point { x: v[3], y: v[2] }; let N: i32 = read(); let walls: Vec<Point> = (0..N).map(|_| read_point()).collect(); let Q: i32 = read(); let queries: Vec<(char, i32)> = (0..Q).map(|_| read_vec::<String>()). map(|v| (v[0].chars().next().unwrap(), v[1].parse().unwrap())). collect(); (H, W, pt0, walls, queries) } struct Walls { walls: Vec<i32> } impl Walls { fn push(&mut self, x: i32) { self.walls.push(x) } fn find_range(&self, x: i32, first: usize, last: usize) -> usize { if first == last - 1 { first } else { let mid = (first + last) / 2; if x < self.walls[mid] { self.find_range(x, first, mid) } else { self.find_range(x, mid, last) } } } fn walk_x(&self, x: i32, n: i32) -> i32 { let first = self.find_range(x, 0, self.walls.len() - 1); if n > 0 { let upper = self.walls[first+1] - 1; min(upper, x + n) } else { let lower = self.walls[first] + 1; max(lower, x + n) } } } struct Board { H: i32, W: i32, HWalls: HashMap<i32, Walls>, VWalls: HashMap<i32, Walls>, } impl Board { fn walk(&self, pt: Point, query: &(char, i32)) -> Point { match *query { ('L', n) => self.walk_x(pt, -n), ('R', n) => self.walk_x(pt, n), ('U', n) => self.walk_y(pt, -n), ('D', n) => self.walk_y(pt, n), _ => pt } } fn walk_x(&self, pt: Point, n: i32) -> Point { match self.HWalls.get(&pt.y) { Some(walls) => Point { x: walls.walk_x(pt.x, n), y: pt.y }, None => { if n > 0 { Point { x: min(pt.x + n, self.W), y: pt.y } } else { Point { x: max(pt.x + n, 1), y: pt.y } } } } } fn walk_y(&self, pt: Point, n: i32) -> Point { match self.VWalls.get(&pt.x) { Some(walls) => Point { x: pt.x, y: walls.walk_x(pt.y, n) }, None => { if n > 0 { Point { x: pt.x, y: min(pt.y + n, self.H) } } else { Point { x: pt.x, y: max(pt.y + n, 1) } } } } } fn create(H: i32, W: i32, walls: &Vec<Point>) -> Board { let mut walls1 = HashMap::<i32, Walls>::new(); let mut walls2 = HashMap::<i32, Walls>::new(); for wall in walls.iter() { let v = walls1.entry(wall.y).or_insert(Walls { walls: vec![] }); v.push(wall.x); let w = walls2.entry(wall.x).or_insert(Walls { walls: vec![] }); w.push(wall.y); } let HWalls = Board::sort(walls1, W); let VWalls = Board::sort(walls2, H); Board { H, W, HWalls, VWalls } } fn sort(walls: HashMap<i32, Walls>, U: i32) -> HashMap<i32, Walls> { let mut sorted_walls = HashMap::<i32, Walls>::new(); for (&y, wall) in &walls { let mut xs1 = wall.walls.iter().map(|&x| x).collect::<Vec::<i32>>(); xs1.sort(); xs1.insert(0, 0); xs1.push(U + 1); sorted_walls.insert(y, Walls { walls: xs1 }); } sorted_walls } } fn f(H: i32, W: i32, pt0: Point, walls: Vec<Point>, queries: Vec<(char, i32)>) { let board = Board::create(H, W, &walls); let mut pt = pt0; for query in queries.iter() { pt = board.walk(pt, query); println!("{} {}", pt.y, pt.x) } } fn main() { let v = read_input(); f(v.0, v.1, v.2, v.3, v.4) }