macro_rules! input { ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr,) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::>() }; ($next:expr, usize1) => (read_value!($next, usize) - 1); ($next:expr, [ $t:tt ]) => {{ let len = read_value!($next, usize); read_value!($next, [$t; len]) }}; ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error")); } type Output = String; const TIMELIMIT: f64 = 1.935; const DIJ: [(usize, usize); 4] = [(0, !0), (!0, 0), (0, 1), (1, 0)]; const DIR: [char; 4] = ['L', 'U', 'R', 'D']; struct Input { pub h: usize, pub w: usize, pub p: usize, } struct Grid { pub yoko: Vec>>, // 確率的に壁がある } fn main() { let input = parse_input(); let mut grid = { let mut grid = vec![vec![vec![0.0; 4]; input.w]; input.h]; for j in 0..input.w { grid[0][j][1] = 1.0; grid[input.h - 1][j][3] = 1.0; } for i in 0..input.h { grid[i][0][0] = 1.0; grid[i][input.w - 1][2] = 1.0; } grid }; let mut out = vec![3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]; let mut feed = out.len() as i32; loop { println!("{}", parse_output(&out)); feed = { let mut s = String::new(); std::io::stdin().read_line(&mut s).unwrap(); let s = s.trim(); s.parse::().unwrap() }; if feed == -1 { break; } random_walk(&input, &mut out,&mut grid, feed); } } fn random_walk(input: &Input, out: &mut Vec, grid: &mut Vec>>, feed: i32) { let feed = feed as usize; let mut h = 0; let mut w = 0; for o in out.iter().take(feed) { h += DIJ[*o].0; w += DIJ[*o].1; } if feed < out.len() { grid[h][w][out[feed]] = 1.0; } // bfsして新しくoutを作る let mut que = std::collections::VecDeque::new(); let mut visited = vec![vec![false; input.w]; input.h]; let mut prev = vec![vec![4; input.w]; input.h]; visited[0][0] = true; que.push_back((0,0)); while !que.is_empty() { let v = que.pop_front().unwrap(); for (d,(di, dj)) in DIJ.iter().enumerate() { let ni = v.0 + *di; let nj = v.1 + *dj; if input.h <= ni || input.w <= nj { continue; } if visited[ni][nj] || 0.5 < grid[h][w][d] { continue; } visited[ni][nj] = true; prev[ni][nj] = d; que.push_back((ni, nj)); } } // 経路復元 let mut new_out = vec![]; let mut v = (19, 19); while v != (0,0) { let i = prev[v.0][v.1]; if i == 4 { break; } new_out.push(i); v.0 += DIJ[i ^ 2].0; v.1 += DIJ[i ^ 2].1; } new_out.reverse(); *out = new_out; } fn parse_input() -> Input { input!{ h: usize, w: usize, p: usize, } Input { h, w, p } } fn parse_output(out: &Vec) -> Output { out.iter().map(|o| DIR[*o]).collect() }