#![allow(dead_code)] #![allow(non_upper_case_globals)] #![allow(unused_imports)] use grid::{Coord, Map2d, DC}; use std::cmp::*; use std::collections::*; use std::io::stdin; const TIME_LIMIT: f64 = 2.9; const N: usize = 50; const N2: usize = N * N; const M: usize = 20; pub fn main() { get_time(); let input = read_input(); let output = solve(&input); output.print_ans(); eprintln!("Time = {}", get_time()); } fn solve(input: &Input) -> Output { let mut state = State::new(input); state.calc_score(input); state.to_output(input) } struct State { score: usize, use_bomb: Map2d>, cnt_use: Map2d, jun: Vec<(Coord, usize)>, } impl State { fn new(input: &Input) -> Self { let score = !0; let mut use_bomb = Map2d::new(vec![vec![false; M]; N2], N); let mut cnt_use = Map2d::new(vec![0; N2], N); let mut jun = vec![]; for x in 0..N { for y in 0..N { let p = Coord::new(x, y); if input.map[p] == Square::Empty || cnt_use[p] > 0 { continue; } let (bp, bid) = input.can_hakai_rev[p][rnd::next() % input.can_hakai_rev[p].len()]; use_bomb[bp][bid] = true; for &np in input.can_hakai[bp][bid].iter() { cnt_use[np] += 1; } jun.push((bp, bid)); } } Self { score, use_bomb, cnt_use, jun, } } fn calc_score(&mut self, input: &Input) { let mut score = 0; let sz = self.jun.len(); // uso dp let mut dp = 0; let mut rui = 0; let mut mae = Coord::new(0, 0); let mut bombed = Map2d::new(vec![false; N2], N); for i in 0..sz { score += input.bomb_cost[self.jun[i].1]; let ue = if i == 0 { (!0, !0) } else { ( dp + rui + self.jun[i].0.dist(&mae), rui + self.jun[i].0.dist(&mae), ) }; let sita = if let Some(&near) = input.near_shop[self.jun[i].0] .iter() .find(|&&np| !bombed[np]) { ( dp + mae.dist(&near) + self.jun[i].0.dist(&near), self.jun[i].0.dist(&near), ) } else { (!0, !0) }; if ue.0 < sita.0 { dp = ue.0; rui = ue.1; } else { dp = sita.0; rui = sita.1; } mae = self.jun[i].0; for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() { bombed[np] = true; } } self.score = score + dp; } fn to_output(&self, input: &Input) -> Output { let mut actions = vec![]; let sz = self.jun.len(); let mut dp = 0; let mut rui = 0; let mut mae = Coord::new(0, 0); let mut bombed = Map2d::new(vec![false; N2], N); let mut buyvec = vec![]; for i in 0..sz { let ue = if i == 0 { (!0, !0) } else { ( dp + rui + self.jun[i].0.dist(&mae), rui + self.jun[i].0.dist(&mae), ) }; let sita = if let Some(&near) = input.near_shop[self.jun[i].0] .iter() .find(|&&np| !bombed[np]) { ( dp + mae.dist(&near) + self.jun[i].0.dist(&near), self.jun[i].0.dist(&near), ) } else { (!0, !0) }; if ue.0 < sita.0 { dp = ue.0; rui = ue.1; actions.extend(moves(mae, self.jun[i].0)); } else { dp = sita.0; rui = sita.1; let near = *input.near_shop[self.jun[i].0] .iter() .find(|&&np| !bombed[np]) .unwrap(); actions.extend(moves(mae, near)); // ここに購入を計算 todo // あとでここに入れる buyvec.push(vec![]); actions.push((2, !0)); // actions.extend(moves(near, self.jun[i].0)); } // use actions.push((3, self.jun[i].1 + 1)); let lll = buyvec.len() - 1; buyvec[lll].push((2, self.jun[i].1 + 1)); // mae = self.jun[i].0; for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() { bombed[np] = true; } } let mut ret_actions = vec![]; let mut buyidx = 0; for &(tp, dd) in actions.iter() { if tp != 2 { ret_actions.push((tp, dd)); } else { for &t in buyvec[buyidx].iter() { ret_actions.push(t); } buyidx += 1; } } Output { score: self.score, actions: ret_actions, } } } fn moves(a: Coord, b: Coord) -> Vec<(usize, usize)> { let mut ret = vec![]; let mut p = a; while p != b { if p.y > b.y { p.y -= 1; ret.push((1, 0)); } else if p.x > b.x { p.x -= 1; ret.push((1, 1)); } else if p.y < b.y { p.y += 1; ret.push((1, 2)); } else if p.x < b.x { p.x += 1; ret.push((1, 3)); }; } ret } #[derive(PartialEq, Eq, Clone, Copy)] enum Square { Empty, House, Shop, } struct Input { map: Map2d, bomb_cost: Vec, near_shop: Map2d>, can_hakai: Map2d>>, // そのマスで爆弾iを使って破壊できるもの can_hakai_rev: Map2d>, // そのマスを破壊することができるマスと爆弾の種類 } fn read_input() -> Input { let _nm = input_vecusize(); let mut map_ = vec![]; for _i in 0..N { let a = input_string(); map_.push(a.chars().collect::>()); } let mut map = vec![]; for x in 0..N { for y in 0..N { let c = match map_[x][y] { '.' => Square::Empty, '#' => Square::House, '@' => Square::Shop, _ => unreachable!(), }; map.push(c); } } let map = Map2d::new(map, N); let mut can_hakai = Map2d::new(vec![vec![vec![]; M]; N2], N); let mut bomb_cost = vec![]; let mut can_hakai_rev = Map2d::new(vec![vec![]; N2], N); for bombid in 0..M { let cl = input_vecusize(); let c = cl[0]; let l = cl[1]; bomb_cost.push(c); for _ in 0..l { let dxdy = input_veci32(); let dx = dxdy[0]; let dy = dxdy[1]; for x in 0..N as i32 { for y in 0..N as i32 { let nx = x + dx; let ny = y + dy; let p = Coord::new(x as usize, y as usize); let np = Coord::new(nx as usize, ny as usize); if 0 <= nx && nx < N as i32 && 0 <= ny && ny < N as i32 && map[np] != Square::Empty { can_hakai[p][bombid].push(np); can_hakai_rev[np].push((p, bombid)); } } } } } let mut near_shop = Map2d::new(vec![vec![]; N2], N); let mut shops = vec![]; for x in 0..N { for y in 0..N { let p = Coord::new(x, y); if map[p] == Square::Shop { shops.push(p); } } } for x in 0..N { for y in 0..N { let p = Coord::new(x, y); near_shop[p] = shops.clone(); near_shop[p].sort_by(|a, b| p.dist(a).cmp(&p.dist(b))); } } Input { map, bomb_cost, near_shop, can_hakai, can_hakai_rev, } } struct Output { score: usize, actions: Vec<(usize, usize)>, } impl Output { fn print_ans(&self) { let score = self.score; crate::print_data!(score); let q = self.actions.len(); println!("{}", q); for i in 0..q { if self.actions[i].0 == 1 { println!("{} {}", self.actions[i].0, DC[self.actions[i].1]); } else { println!("{} {}", self.actions[i].0, self.actions[i].1); } } } } // ここからライブラリ #[macro_export] macro_rules! print_data { ( $($x:expr),* ) => {{ $(eprintln!("[DATA] {} = {:?}", stringify!($x), $x);)* }} } pub fn get_time() -> f64 { static mut START: f64 = -1.0; let end = std::time::SystemTime::now() .duration_since(std::time::UNIX_EPOCH) .unwrap() .as_secs_f64(); unsafe { if START < 0.0 { START = end; } end - START } } #[allow(unused)] mod rnd { static mut S: usize = 88172645463325252; pub fn next() -> usize { unsafe { S ^= S << 7; S ^= S >> 9; S } } pub fn nextf() -> f64 { f64::from_bits((0x3ff0000000000000 | next() & 0xfffffffffffff) as u64) - 1. } pub fn range(a: usize, b: usize) -> usize { next() % (b - a) + a } pub fn exu(a: usize, b: usize, skip: usize) -> usize { assert!(a <= skip && skip < b); let ret = range(a, b - 1); ret + (skip <= ret) as usize } pub fn rangei(a: i64, b: i64) -> i64 { (next() % ((b - a) as usize)) as i64 + a } pub fn shuffle(list: &mut [T]) { for i in (0..list.len()).rev() { list.swap(i, next() % (i + 1)); } } } #[allow(dead_code)] mod grid { #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub struct Coord { pub x: usize, pub y: usize, } impl Coord { pub const fn new(x: usize, y: usize) -> Self { Self { x, y } } pub const fn new2(p: usize, width: usize) -> Self { Self { x: p / width, y: p % width, } } pub fn in_map(&self, size: usize) -> bool { self.x < size && self.y < size } pub const fn idx(&self, size: usize) -> usize { self.x * size + self.y } pub fn next(self, dir: usize) -> Self { self + DXY[dir] } pub const fn dist(&self, other: &Self) -> usize { Self::dist_1d(self.x, other.x) + Self::dist_1d(self.y, other.y) } const fn dist_1d(x0: usize, x1: usize) -> usize { x0.abs_diff(x1) } } impl std::ops::Add for Coord { type Output = Self; fn add(self, other: Self) -> Self { Self { x: self.x + other.x, y: self.y + other.y, } } } pub const DXY: [Coord; 4] = [ Coord::new(0, !0), Coord::new(!0, 0), Coord::new(0, 1), Coord::new(1, 0), ]; pub const DC: [char; 4] = ['L', 'U', 'R', 'D']; #[derive(Debug, Clone)] pub struct Map2d { pub height: usize, pub width: usize, map: Vec, } impl Map2d { pub fn new(map: Vec, width: usize) -> Self { let height = map.len() / width; debug_assert!(width * height == map.len()); Self { height, width, map } } pub fn fill(&mut self, value: T) { self.map.fill(value); } } impl std::ops::Index for Map2d { type Output = T; #[inline] fn index(&self, coord: Coord) -> &Self::Output { unsafe { self.map.get_unchecked(coord.x * self.width + coord.y) } } } impl std::ops::IndexMut for Map2d { #[inline] fn index_mut(&mut self, coord: Coord) -> &mut Self::Output { unsafe { self.map.get_unchecked_mut(coord.x * self.width + coord.y) } } } impl std::ops::Index<&Coord> for Map2d { type Output = T; #[inline] fn index(&self, coord: &Coord) -> &Self::Output { &self.map[coord.x * self.width + coord.y] } } impl std::ops::IndexMut<&Coord> for Map2d { #[inline] fn index_mut(&mut self, coord: &Coord) -> &mut Self::Output { &mut self.map[coord.x * self.width + coord.y] } } impl std::ops::Index for Map2d { type Output = T; #[inline] fn index(&self, p: usize) -> &Self::Output { &self.map[p] } } impl std::ops::IndexMut for Map2d { #[inline] fn index_mut(&mut self, p: usize) -> &mut Self::Output { &mut self.map[p] } } } fn input_vecusize() -> Vec { let mut a = String::new(); stdin().read_line(&mut a).unwrap(); return a .trim() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect(); } fn input_veci32() -> Vec { let mut a = String::new(); stdin().read_line(&mut a).unwrap(); return a .trim() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect(); } fn input_string() -> String { let mut a = String::new(); stdin().read_line(&mut a).unwrap(); return a.trim().parse().unwrap(); }