#include constexpr int inf = (int)1e9 + 7; constexpr int N = 50, M = 20; constexpr int dr[] = {1, 0, -1, 0}; constexpr int dc[] = {0, 1, 0, -1}; using Board = std::array, N>; struct Bomb { int bomb_id; int C, L; std::vector dr, dc; Bomb() {} void input() { std::cin >> this->C >> this->L; this->dr.resize(this->L), this->dc.resize(this->L); for (int i = 0; i < this->L; i++) { std::cin >> this->dr[i] >> this->dc[i]; } } }; void input(Board &board, std::array &Bombs) { int _n, _m; std::cin >> _n >> _m; for (int i = 0; i < N; i++) { std::string s; std::cin >> s; for (int j = 0; j < N; j++) { if (s[j] == '.') board[i][j] = 0; if (s[j] == '@') board[i][j] = 1; if (s[j] == '#') board[i][j] = 2; } } for (int i = 0; i < M; i++) { Bombs[i].input(); Bombs[i].bomb_id = i; } } bool is_board_valid(const int r, const int c) { return 0 <= r and r < N and 0 <= c and c < N; } std::pair calc_wall_and_store_count(const int r, const int c, const Board &board, const Bomb &bomb) { int wall = 0, store = 0; for (int i = 0; i < bomb.L; i++) { const int nr = r + bomb.dr[i]; const int nc = c + bomb.dc[i]; if (is_board_valid(nr, nc)) { if (board[nr][nc] == 1) store += 1; if (board[nr][nc] == 2) wall += 1; } } return std::pair{store, wall}; } void calc_dist(const int sr, const int sc, std::array, N> &dist, std::array, N>, N> &back, const Board &board) { for (int i = 0; i < N; i++) { std::fill(dist[i].begin(), dist[i].end(), inf); std::fill(back[i].begin(), back[i].end(), std::pair{-1, -1}); } using T = std::tuple; std::queue q1, q2; dist[sr][sc] = 0; q1.emplace(0, sr, sc); while (not q1.empty() or not q2.empty()) { int d = -1, r = -1, c = -1; if (not q1.empty() and not q2.empty()) { if (std::get<0>(q1.front()) <= std::get<0>(q2.front())) { std::tie(d, r, c) = q1.front(); q1.pop(); } else { std::tie(d, r, c) = q2.front(); q2.pop(); } } else if (not q1.empty()) { std::tie(d, r, c) = q1.front(); q1.pop(); } else if (not q2.empty()) { std::tie(d, r, c) = q2.front(); q2.pop(); } else { assert(false); } if (d > dist[r][c]) continue; for (int i = 0; i < 4; i++) { const int nr = r + dr[i]; const int nc = c + dc[i]; if (is_board_valid(nr, nc)) { if (board[nr][nc] == 0 and dist[nr][nc] > dist[r][c] + 1) { dist[nr][nc] = dist[r][c] + 1; back[nr][nc] = {r, c}; q1.emplace(dist[nr][nc], nr, nc); } if (board[nr][nc] != 0 and dist[nr][nc] > dist[r][c] + 2) { dist[nr][nc] = dist[r][c] + 2; back[nr][nc] = {r, c}; q2.emplace(dist[nr][nc], nr, nc); } } } } } void calc_path(const int sr, const int sc, const int er, const int ec, std::vector> &res, const std::array, N>, N> &back) { std::vector path; int cr = er, cc = ec; while (cr != sr or cc != sc) { for (int i = 0; i < 4; i++) { const int pr = cr - dr[i]; const int pc = cc - dc[i]; if (is_board_valid(pr, pc) and back[cr][cc] == std::pair{pr, pc}) { path.emplace_back(i); cr = pr, cc = pc; } } } while (not path.empty()) { res.emplace_back(1, path.back()); path.pop_back(); } } void solve(Board board, const std::array &bombs) { std::array, N> dist; std::array, N>, N> back; std::set> store_set, wall_set; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (board[i][j] == 1) store_set.emplace(i, j); if (board[i][j] == 2) wall_set.emplace(i, j); } } int min_bomb_id = -1; { int max_l = -1; int min_c = inf; for (int i = 0; i < M; i++) { if (bombs[i].C < min_c or (bombs[i].C == min_c and max_l < bombs[i].L)) { min_c = bombs[i].C; min_bomb_id = i; max_l = bombs[i].L; } } } std::vector> res; std::vector> gomi; int sr = 0, sc = 0; while (not store_set.empty()) { calc_dist(sr, sc, dist, back, board); long long res_score = -(long long)inf * 1000; int r = -1, c = -1; int res_store_r = -1, res_store_c = -1; int bomb_id = -1; int d = inf; for (const auto &[to_r, to_c] : store_set) { if (dist[to_r][to_c] < d) { res_store_r = to_r; res_store_c = to_c; d = dist[to_r][to_c]; } } calc_path(sr, sc, res_store_r, res_store_c, res, back); calc_dist(res_store_r, res_store_c, dist, back, board); auto f = [&](const int tr, const int tc) -> void { if (not is_board_valid(tr, tc)) return; { auto i = min_bomb_id; auto [erase_store, erase_wall] = calc_wall_and_store_count(tr, tc, board, bombs[i]); const long long score = erase_wall + erase_store; if (erase_wall + erase_store > 0 and res_score < score and not(erase_wall < (int)wall_set.size() and erase_store == (int)store_set.size())) { res_score = score; bomb_id = i; r = tr, c = tc; } } }; gomi.clear(); for (int tr = res_store_r - 10; tr <= res_store_r + 10; tr++) { for (int tc = res_store_c - 10; tc <= res_store_c + 10; tc++) { if (is_board_valid(tr, tc)) gomi.emplace_back(tr, tc); } } std::sort(gomi.begin(), gomi.end(), [&](auto i, auto j) { return dist[i.first][i.second] > dist[j.first][j.second]; }); while (not gomi.empty()) { f(gomi.back().first, gomi.back().second); gomi.pop_back(); if (res_score == bombs[min_bomb_id].L) gomi.clear(); } if (bomb_id == -1) { for (int tr = 0; tr < N; tr++) { for (int tc = 0; tc < N; tc++) { if (not is_board_valid(tr, tc)) continue; f(tr, tc); } } } if (bomb_id == -1) break; assert(board[res_store_r][res_store_c] == 1); res.emplace_back(2, bomb_id + 1); calc_path(res_store_r, res_store_c, r, c, res, back); res.emplace_back(3, bomb_id + 1); sr = r, sc = c; assert(0 <= bomb_id and bomb_id < M); const auto &bomb = bombs[bomb_id]; for (int i = 0; i < bomb.L; i++) { const int nr = r + bomb.dr[i]; const int nc = c + bomb.dc[i]; if (is_board_valid(nr, nc)) { if (board[nr][nc] == 1) { store_set.erase(store_set.find({nr, nc})); } if (board[nr][nc] == 2) { wall_set.erase(wall_set.find({nr, nc})); } board[nr][nc] = 0; } } } const std::string DIR = "DRUL"; std::cout << res.size() << "\n"; int cost2 = 0; for (const auto &[t, val] : res) { if (t == 1) { std::cout << 1 << " " << DIR[val] << "\n"; } else { std::cout << t << " " << val << "\n"; if (t == 2) { cost2 += bombs[val - 1].C; } } } std::cerr << cost2 << "\n"; } int main() { Board board; std::array bombs; input(board, bombs); solve(board, bombs); }