#![allow(unused_imports, non_snake_case, dead_code)] pub use __cargo_equip::prelude::*; use kyopro_grid::{D4, P}; use kyopro_io::get; use kyopro_utils::*; use std::cmp::min; use std::collections::{BTreeSet, BinaryHeap, VecDeque}; use std::mem::{self, swap}; use std::ops::{Index, IndexMut}; use std::{ cmp::max, collections::BTreeMap, io::{StdoutLock, Write}, }; const N: usize = 50; const M: usize = 20; const DC: [char; 4] = ['D', 'R', 'U', 'L']; struct Bomb { C: usize, L: usize, ab: Vec<(i32, i32)>, } struct Input { A: Vec>, bs: Vec, shops: Vec

, } fn read_input() -> Input { let _ = get!(usize, usize); let A = (0..N).map(|_| get!(String).chars().collect::>()).collect::>(); let mut bs = vec![]; for _ in 0..M { let (c, l) = get!(usize, usize); let mut ab = vec![]; for _ in 0..l { let (a, b) = get!(i32, i32); ab.push((a, b)); } bs.push(Bomb { C: c, L: l, ab }); } let mut shops = vec![]; for i in 0..N { for j in 0..N { if A[i][j] == '@' { shops.push(P(i, j)); } } } Input { A, bs, shops } } enum OP { MV(usize), PUT(usize), BUY(usize), } struct Operations { ops: Vec, } impl Operations { fn new() -> Self { Self { ops: vec![] } } fn move_(&mut self, d: usize) { self.ops.push(OP::MV(d)); } fn use_bomb(&mut self, m: usize) { self.ops.push(OP::PUT(m)); } fn buy_bomb(&mut self, m: usize) { self.ops.push(OP::BUY(m)); } fn get(&self) -> Vec { self.ops .iter() .map(|x| match x { OP::MV(d) => { format!("{} {}", 1, DC[*d]) } OP::BUY(m) => { format!("{} {}", 2, m + 1) } OP::PUT(m) => { format!("{} {}", 3, m + 1) } }) .collect::>() } fn len(&self) -> usize { self.ops.len() } } fn get_bpoints(p: P, ab: &[(i32, i32)], inv: bool) -> Vec

{ let mut res = vec![]; for &(a, b) in ab { let ni = p.0 as i32 + (if inv { -a } else { a }); let nj = p.1 as i32 + (if inv { -b } else { b }); if 0 <= ni && ni < N as i32 && 0 <= nj && nj < N as i32 { let ni = ni as usize; let nj = nj as usize; res.push(P(ni, nj)); } } res } fn move_to_opt(g: &Vec>, ops: &mut Operations, f: P, t: P) { let mut dp = mat![1_000_100_000;N;N]; let mut pre = mat![!0usize;N;N]; dp[f] = 0i32; let mut que = BinaryHeap::new(); que.push((0, f.0 * N + f.1)); while let Some((co, tmp)) = que.pop() { let co = -co; let p = P(tmp / N, tmp % N); if dp[p] < co { continue; } if p == t { break; } for (di, np) in p.adj4().enumerate() { if np.0 < N && np.1 < N { let pc = if g[np] == '.' { 1 } else { 2 }; let ncost = co + pc; if dp[np].setmin(ncost) { pre[np] = di; if pc == 1 { que.push((-ncost, np.0 * N + np.1)); } else { que.push((-ncost, np.0 * N + np.1)); } } } } } let mut moves = vec![]; let mut now = t; while now != f { moves.push(pre[now]); now = now.add(&D4[(pre[now] + 2) % 4]); } moves.reverse(); for d in moves { ops.move_(d); } } fn greedy_internal( inp: &Input, shops: &[P], p_to_bp: &Vec>>>, pb_cnt: &Vec>>, ) -> Operations { let mut dcost = mat![0;N;N]; let mut shop_to_npts = mat![vec![];shops.len()]; let mut p_to_nsi = mat![0;N;N]; for i in 0..N { for j in 0..N { let p = P(i, j); let mut near_shop = 0; let mut d = !0; for (si, sp) in shops.iter().enumerate() { if d.setmin(sp.dist(&p)) { near_shop = si; } } dcost[p] = d; shop_to_npts[near_shop].push(p); p_to_nsi[p] = near_shop; } } let _kill = |g: &mut Vec>, pb_cnt: &mut Vec>>, p: P, c: char| { let pre = g[p]; g[p] = c; if pre == '.' || pre == '_' { return; } for i in 0..M { for &np in &p_to_bp[p][i] { pb_cnt[np][i] -= 1; } } }; let dkill = |g: &mut Vec>, pb_cnt: &mut Vec>>, p: P| { _kill(g, pb_cnt, p, '_'); }; let kill = |g: &mut Vec>, pb_cnt: &mut Vec>>, p: P| { _kill(g, pb_cnt, p, '.'); }; let mut ng_pbs = mat![0;N;N;M]; for (i, &p) in shops.iter().enumerate() { for m in 0..M { for np in get_bpoints(p, &inp.bs[m].ab, true) { ng_pbs[np][m] |= 1usize << i; } } } let mut g = inp.A.clone(); let mut pb_cnt = pb_cnt.clone(); let mut use_bi_at_shops = vec![]; let mut ops = Operations::new(); for (si, &sp) in shops.iter().enumerate() { let mut x = 0.0; let mut bi = !0; for m in 0..M { if ng_pbs[sp][m] >> (si + 1) > 0 { continue; } let mut tot = 0; for bp in get_bpoints(sp, &inp.bs[m].ab, false) { tot += pb_cnt[bp][m]; } if x.setmax(tot as f64 / inp.bs[m].C as f64) { bi = m; } } assert!(bi != !0); use_bi_at_shops.push(bi); { for bp in get_bpoints(sp, &inp.bs[bi].ab, false) { dkill(&mut g, &mut pb_cnt, bp); } } } eprintln!("{:?}", shops); let mut curr_shop_i = 0; // move to shop[0] move_to_opt(&g, &mut ops, P(0, 0), shops[0]); while curr_shop_i < shops.len() { let can_fire = |p: P, m: usize| ng_pbs[p][m] >> curr_shop_i == 0; let mut ri = 0.0; let mut best_pm = (P(0, 0), !0, !0); for (pti, &tp) in shop_to_npts[curr_shop_i].iter().enumerate() { if g[tp] == '.' || g[tp] == '_' { continue; } for m in 0..M { for &bp in &p_to_bp[tp][m] { if can_fire(bp, m) { let val = pb_cnt[bp][m] as f64; let co = inp.bs[m].C as f64 + (bp.dist(&shops[curr_shop_i]) * 4) as f64; if ri.setmax(val / co) { best_pm = (bp, m, pti); } } } } if best_pm.1 != !0 { break; } } if best_pm.1 == !0 { // shop で bomb let m = use_bi_at_shops[curr_shop_i]; ops.buy_bomb(m); ops.use_bomb(m); for bp in get_bpoints(shops[curr_shop_i], &inp.bs[m].ab, false) { kill(&mut g, &mut pb_cnt, bp); } let rest: usize = shop_to_npts[curr_shop_i].iter().filter(|&&p| g[p] != '.').count(); eprintln!("rest:{}", rest); curr_shop_i += 1; if curr_shop_i < shops.len() { move_to_opt(&g, &mut ops, shops[curr_shop_i - 1], shops[curr_shop_i]); } } else { // m を購入して bp まで行って m でbomb let (p, m, pti) = best_pm; if p_to_nsi[p] > curr_shop_i { let tp = shop_to_npts[curr_shop_i].swap_remove(pti); shop_to_npts[p_to_nsi[p]].push(tp); } else { ops.buy_bomb(m); // shop[curr_shop_i] に戻る move_to_opt(&g, &mut ops, shops[curr_shop_i], p); ops.use_bomb(m); for bp in get_bpoints(p, &inp.bs[m].ab, false) { assert!(bp != shops[curr_shop_i]); kill(&mut g, &mut pb_cnt, bp); } move_to_opt(&g, &mut ops, p, shops[curr_shop_i]); } } } ops } fn select_shops(inp: &Input) -> Vec

{ let mut spos1 = vec![vec![]; 10]; inp.shops.iter().enumerate().for_each(|(i, &p)| { let x = min(p.0 / 16, 2); let y = min(p.1 / 16, 2); let mut prio = 20; if p.0 < 5 { prio -= p.0; } if p.0 >= N - 5 { prio -= N - p.0; } if p.1 < 5 { prio -= p.1; } if p.1 >= N - 5 { prio -= N - p.1; } spos1[x * 3 + y].push((i, p, prio as i32)); }); let mut dame = mat![false;N;N]; let mut shops = vec![]; for i in [0, 1, 2, 5, 4, 3, 6, 7, 8] { if spos1[i].len() == 0 { continue; } spos1[i].sort_by_key(|x| -x.2); for &(_, p, _) in &spos1[i] { if dame[p] { continue; } shops.push(p); for bp in get_bpoints(p, &inp.bs[0].ab, false) { dame[bp] = true; } break; } } shops } fn greedy(inp: &Input) -> Operations { let shops = select_shops(inp); let mut p_to_bp = mat![vec![];N;N;M]; // [i][j][b]: bomb b で P(i,j)に攻撃できる座標リスト let mut pb_cnt = mat![0i32;N;N;M]; // [i][j][b]: P(i,j) で b を使用したときに攻撃できる座標の数 for i in 0..N { for j in 0..N { if inp.A[i][j] == '.' { continue; } for k in 0..M { for np in get_bpoints(P(i, j), &inp.bs[k].ab, true) { p_to_bp[i][j][k].push(np); pb_cnt[np][k] += 1; } } } } let res = greedy_internal(inp, &shops, &p_to_bp, &pb_cnt); res } fn main() { let stdout = std::io::stdout(); let mut writer = std::io::BufWriter::new(stdout.lock()); let inp = read_input(); let res = greedy(&inp); writeln!(writer, "{}", res.len()).unwrap(); for s in res.get() { writeln!(writer, "{}", s).unwrap(); } } // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `kyopro-grid 0.1.0 (path+██████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::kyopro_grid` /// - `kyopro-io 0.1.0 (path+████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::kyopro_io` /// - `kyopro-utils 0.1.0 (path+███████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::kyopro_utils` #[cfg_attr(any(), rustfmt::skip)] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod kyopro_grid {use std::ops::{Index,IndexMut};pub const D4:[P;4]=[P(1,0),P(0,1),P(!0,0),P(0,!0)];#[derive(Clone,Copy,PartialEq,Eq,Debug)]pub struct P(pub usize,pub usize);impl P{pub fn adj4(self)->impl Iterator{D4.iter().map(move|&d|self.add(&P(d.0,d.1)))}pub fn add(self,rhs:&P)->P{P(self.0.wrapping_add(rhs.0),self.1.wrapping_add(rhs.1))}pub fn dist(&self,rhp:&P)->usize{let a=(self.0 as i32-rhp.0 as i32).abs()as usize;let b=(self.1 as i32-rhp.1 as i32).abs()as usize;a+b}}implIndex

for Vec>{type Output=T;fn index(&self,p:P)->&T{&self[p.0][p.1]}}implIndexMut

for Vec>{fn index_mut(&mut self,p:P)->&mut T{&mut self[p.0][p.1]}}pub struct Grid{h:usize,w:usize,g:Vec>,}implGridwhere T:Copy,{pub fn from(g:&Vec>)->Self{Grid{h:g.len(),w:g[0].len(),g:g.clone()}}#[allow(non_snake_case)]pub fn new(h:usize,w:usize,I:T)->Self{let g=vec![vec![I;w];h];Grid{h,w,g}}}implGrid{pub fn adj4<'a>(&'a self,p:P)->impl Iterator+'a{D4.iter().map(move|&d|p.add(&P(d.0,d.1))).filter(|&p|p.0(&'a self,b:P,offsets:&'a[P])->impl Iterator+'a{let x=offsets.iter().map(move|&d|P(b.0.wrapping_add(d.0),b.1.wrapping_add(d.1)));x.filter(|&p|p.0Option

{let x=b.add(&offset);if self.is_valid_position(&x){Some(x)}else{None}}pub fn is_valid_position(&self,p:&P)->bool{p.0Indexfor Grid{type Output=[T];#[inline]fn index(&self,idx:usize)->&[T]{&self.g[idx]}}implIndexMutfor Grid{#[inline]fn index_mut(&mut self,idx:usize)->&mut[T]{&mut self.g[idx]}}implIndex

for Grid{type Output=T;#[inline]fn index(&self,idx:P)->&T{&self.g[idx.0][idx.1]}}implIndexMut

for Grid{#[inline]fn index_mut(&mut self,p:P)->&mut T{&mut self.g[p.0][p.1]}}} pub mod kyopro_io {pub use crate::__cargo_equip::macros::kyopro_io::*;#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_io_get{($t:ty)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();line.trim().parse::<$t>().unwrap()}};($($t:ty),*)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();let mut iter=line.split_whitespace();($(iter.next().unwrap().parse::<$t>().unwrap(),)*)}};($t:ty;$n:expr)=>{(0..$n).map(|_|get!($t)).collect::>()};($($t:ty),*;$n:expr)=>{(0..$n).map(|_|get!($($t),*)).collect::>()};($t:ty;;)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::>()}};($t:ty;;$n:expr)=>{(0..$n).map(|_|get!($t;;)).collect::>()};}macro_rules!get{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_io_get!{$($tt)*})}} pub mod kyopro_utils {pub use crate::__cargo_equip::macros::kyopro_utils::*;use std::ops::{Add,Rem};#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_mat{($($e:expr),*)=>{Vec::from(vec![$($e),*])};($($e:expr,)*)=>{Vec::from(vec![$($e),*])};($e:expr;$d:expr)=>{Vec::from(vec![$e;$d])};($e:expr;$d:expr$(;$ds:expr)+)=>{Vec::from(vec![mat![$e$(;$ds)*];$d])};}macro_rules!mat{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_mat!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_echo{($($num:expr),*)=>{let mut tmp=vec![];$(tmp.push(format!("{}",$num));)*println!("{}",tmp.join(" "));};}macro_rules!echo{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_echo!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_YesNo{($num:expr)=>{if($num)as i64==0{println!("No");}else{println!("Yes");}};}macro_rules!YesNo{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_YesNo!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_Yes{()=>{println!("Yes");};}macro_rules!Yes{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_Yes!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_No{()=>{println!("No");};}macro_rules!No{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_No!{$($tt)*})}pub trait SetMinMax{fn setmin(&mut self,v:Self)->bool;fn setmax(&mut self,v:Self)->bool;}implSetMinMax for T where T:PartialOrd,{fn setmin(&mut self,v:T)->bool{*self>v&&{*self=v;true}}fn setmax(&mut self,v:T)->bool{*self(v:&[T])where T:std::fmt::Display,{for i in 0..v.len(){print!("{}{}",v[i],if i+1==v.len(){""}else{" "});}println!();}pub fn pmod+Rem>(x:T,m:T)->T{((x%m)+m)%m}pub fn lower_bound(a:&[T],x:&T)->usize where T:Ord,{if a.len()==0||a[0]>=*x{return 0;}let mut l=0;let mut r=a.len();while l+1(a:&[T],x:&T)->usize where T:Ord,{if a.len()==0||a[0]>*x{return 0;}let mut l=0;let mut r=a.len();while l+1