結果

問題 No.5019 Hakai Project
ユーザー wanuiwanui
提出日時 2023-11-20 20:53:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,741 ms / 3,000 ms
コード長 33,103 bytes
コンパイル時間 4,934 ms
コンパイル使用メモリ 285,492 KB
実行使用メモリ 506,708 KB
スコア 2,858,661,450
最終ジャッジ日時 2023-11-20 20:56:17
合計ジャッジ時間 145,797 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,616 ms
444,968 KB
testcase_01 AC 2,695 ms
485,824 KB
testcase_02 AC 2,604 ms
502,128 KB
testcase_03 AC 2,603 ms
501,224 KB
testcase_04 AC 2,587 ms
501,380 KB
testcase_05 AC 2,530 ms
501,632 KB
testcase_06 AC 2,560 ms
501,172 KB
testcase_07 AC 2,741 ms
501,416 KB
testcase_08 AC 2,624 ms
501,748 KB
testcase_09 AC 2,677 ms
501,316 KB
testcase_10 AC 2,549 ms
501,420 KB
testcase_11 AC 2,591 ms
501,252 KB
testcase_12 AC 2,683 ms
501,456 KB
testcase_13 AC 2,593 ms
506,668 KB
testcase_14 AC 2,691 ms
506,676 KB
testcase_15 AC 2,614 ms
506,648 KB
testcase_16 AC 2,592 ms
506,664 KB
testcase_17 AC 2,619 ms
506,680 KB
testcase_18 AC 2,646 ms
506,672 KB
testcase_19 AC 2,630 ms
506,644 KB
testcase_20 AC 2,607 ms
506,676 KB
testcase_21 AC 2,698 ms
506,644 KB
testcase_22 AC 2,533 ms
506,652 KB
testcase_23 AC 2,689 ms
506,652 KB
testcase_24 AC 2,676 ms
506,692 KB
testcase_25 AC 2,632 ms
506,660 KB
testcase_26 AC 2,619 ms
506,652 KB
testcase_27 AC 2,609 ms
506,680 KB
testcase_28 AC 2,613 ms
506,648 KB
testcase_29 AC 2,588 ms
506,704 KB
testcase_30 AC 2,586 ms
506,680 KB
testcase_31 AC 2,631 ms
506,680 KB
testcase_32 AC 2,651 ms
506,664 KB
testcase_33 AC 2,604 ms
506,676 KB
testcase_34 AC 2,674 ms
506,676 KB
testcase_35 AC 2,739 ms
506,640 KB
testcase_36 AC 2,635 ms
506,628 KB
testcase_37 AC 2,628 ms
506,656 KB
testcase_38 AC 2,660 ms
506,624 KB
testcase_39 AC 2,550 ms
506,704 KB
testcase_40 AC 2,612 ms
506,696 KB
testcase_41 AC 2,686 ms
506,696 KB
testcase_42 AC 2,621 ms
506,628 KB
testcase_43 AC 2,701 ms
506,708 KB
testcase_44 AC 2,680 ms
506,600 KB
testcase_45 AC 2,584 ms
506,660 KB
testcase_46 AC 2,553 ms
506,640 KB
testcase_47 AC 2,646 ms
506,664 KB
testcase_48 AC 2,590 ms
506,652 KB
testcase_49 AC 2,696 ms
506,680 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int getmove(point, point)':
main.cpp:113:1: warning: control reaches end of non-void function [-Wreturn-type]
  113 | }
      | ^

ソースコード

diff #

#include <bits/stdc++.h>
// clang-format off
using namespace std;
void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}
void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);}
#define debug1(a) { cerr<<#a<<":"<<a<<endl; }
#define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; }
#define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; }
#define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; }

struct point {int r; int c; };
bool operator==(const point &lhs, const point &rhs) { return (lhs.r == rhs.r && lhs.c == rhs.c); }
bool operator!=(const point &lhs, const point &rhs) { return !(lhs == rhs); }
bool operator<(const point &lhs, const point &rhs) {
    if (lhs.r != rhs.r){return lhs.r<rhs.r;}
    return lhs.c<rhs.c;
}
point operator-(const point &self){
    return {-self.r, -self.c};
}
point operator+(const point &lhs, const point &rhs){
    return {lhs.r+rhs.r, lhs.c+rhs.c};
}
point operator-(const point &lhs, const point &rhs){
    return lhs + (-rhs);
}
std::ostream &operator<<(std::ostream &os, point &pt) {
    string s;
    s = "(" + to_string(int(pt.r)) + ", " + to_string(int(pt.c)) + ")";
    return os << s;
};
const int inf = 1e9;
using pii = pair<int, int>;
// clang-format on
namespace marathon {
mt19937 engine(0);
clock_t start_time;
double now() {
    return 1000.0 * (clock() - start_time) / CLOCKS_PER_SEC;
}
void marathon_init() {
    start_time = clock();
    random_device seed_gen;
    engine.seed(seed_gen());
}
int randint(int mn, int mx) {
    int rng = mx - mn + 1;
    return mn + (engine() % rng);
}
double uniform(double x, double y) {
    const int RND = 1e8;
    double mean = (x + y) / 2.0;
    double dif = y - mean;
    double p = double(engine() % RND) / RND;
    return mean + dif * (1.0 - 2.0 * p);
}
template <typename T>
T random_choice(vector<T> &vec) {
    return vec[engine() % vec.size()];
}
bool anneal_accept(double new_score, double old_score, double cur_time, double begin_time, double end_time, double begin_temp, double end_temp) {
    static int called = 0;
    static double temp = 0;
    if ((called & 127) == 0) {
        double ratio = (cur_time - begin_time) / (end_time - begin_time);
        ratio = min(ratio, 1.0);
        temp = pow(begin_temp, 1.0 - ratio) * pow(end_temp, ratio);
    }
    called++;

    const int ANNEAL_RND = 1e8;
    const double ANNEAL_EPS = 1e-6;

    return (exp((new_score - old_score) / temp) > double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS);
}
}  // namespace marathon
struct operation_t {
    int kind;
    int xyz;
};
struct bomb_t {
    int cost;
    vector<point> ranges;
};
const int _U_ = 0;
const int _R_ = 1;
const int _D_ = 2;
const int _L_ = 3;
const int N = 50;
const int M = 20;
const int N2 = 2500;
const int NNM = 50000;
vector<point> mvs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
using bsn2 = bitset<N2>;
vector<vector<int>> mvtbl(N2);
bsn2 break_bomb_bs[N][N][M];
char TBL_INIT[N][N];
bomb_t BOMBS[M];
int getmove(point src, point dest) {
    assert(abs(src.r - dest.r) + abs(src.c - dest.c) == 1);
    if (src.r < dest.r) {
        return _D_;
    }
    if (src.r > dest.r) {
        return _U_;
    }
    if (src.c < dest.c) {
        return _R_;
    }
    if (src.c > dest.c) {
        return _L_;
    }
}
bool ingrid(int i, int j) {
    return 0 <= i && i < N && 0 <= j && j < N;
}
bool ingrid(point p) {
    return ingrid(p.r, p.c);
}
int _p(int r, int c) {
    return r * N + c;
}
int _p(point p) {
    return _p(p.r, p.c);
}

void init_data() {
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            point u = {r, c};
            for (auto mv : mvs) {
                auto v = mv + u;
                if (!ingrid(v)) continue;
                mvtbl[_p(u)].push_back(_p(v));
            }
        }
    }
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            for (int bid = 0; bid < M; bid++) {
                break_bomb_bs[r][c][bid] = 0;
                point now = {r, c};
                for (auto drc : BOMBS[bid].ranges) {
                    point pt = now + drc;
                    if (!ingrid(pt)) continue;
                    break_bomb_bs[r][c][bid][_p(pt)] = 1;
                }
            }
        }
    }
}
vector<vector<int>> dij_cost(point ini, vector<vector<char>> &tbl) {
    // コスト上限が400くらいなのでpriority_queue不要
    vector<char> tbl_(N2);
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            tbl_[_p(r, c)] = tbl[r][c];
        }
    }
    vector<bool> done(N2);
    vector<int> costs(N2, inf);
    vector<vector<int>> cost_points(N * 4);
    cost_points[0].push_back(_p(ini));
    costs[_p(ini)] = 0;
    for (int cost = 0; cost < N * 4; cost++) {
        for (auto u : cost_points[cost]) {
            if (done[u]) continue;
            done[u] = true;
            for (auto v : mvtbl[u]) {
                int nc = cost + 1;
                if (tbl_[v] != '.') {
                    nc = cost + 2;
                }
                if (done[v]) continue;
                if (costs[v] <= nc) continue;
                costs[v] = nc;
                cost_points[nc].push_back(v);
            }
        }
    }
    vector<vector<int>> result(N, vector<int>(N));
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            result[r][c] = costs[_p(r, c)];
        }
    }
    return result;
}
void dij_goto_ops(point &hulk, point dest, vector<operation_t> &ops, vector<vector<char>> &tbl) {
    priority_queue<tuple<int, point, point>, vector<tuple<int, point, point>>, greater<tuple<int, point, point>>> pq;
    pq.push({0, hulk, {-1, -1}});
    vector<vector<int>> costs(N, vector<int>(N, inf));
    vector<vector<point>> froms(N, vector<point>(N, {-1, -1}));
    while (pq.size()) {
        int cost;
        point u, frm;
        tie(cost, u, frm) = pq.top();
        pq.pop();
        if (costs[u.r][u.c] <= cost) continue;
        costs[u.r][u.c] = cost;
        froms[u.r][u.c] = frm;
        if (u == dest) break;
        for (auto mv : mvs) {
            point v = mv + u;
            if (!ingrid(v)) continue;
            int nc = cost + 1;
            if (tbl[v.r][v.c] != '.') {
                nc = cost + 2;
            }
            pq.push({nc, v, u});
        }
    }
    {
        point cur = dest;
        vector<point> route;
        while (true) {
            route.push_back(cur);
            if (cur == hulk) break;
            cur = froms[cur.r][cur.c];
        }
        reverse(route.begin(), route.end());
        for (int i = 1; i < int(route.size()); i++) {
            point pre = route[i - 1];
            point nxt = route[i];
            int mvid = getmove(pre, nxt);
            ops.push_back({1, mvid});
        }
    }
    hulk = dest;
}
pii evaluate_ops(vector<operation_t> &ops) {
    vector<vector<char>> tbl(N, vector<char>(N));
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            tbl[r][c] = TBL_INIT[r][c];
        }
    }
    int move_cost = 0;
    int bomb_cost = 0;
    point hulk = {0, 0};
    int bombs = 0;
    for (auto op : ops) {
        if (op.kind == 1) {
            hulk = hulk + mvs[op.xyz];
            if (tbl[hulk.r][hulk.c] == '.') {
                move_cost += (1 + bombs) * (1 + bombs);
            } else {
                move_cost += 2 * (1 + bombs) * (1 + bombs);
            }
        } else if (op.kind == 2) {
            bombs++;
            int bombid = op.xyz;
            bomb_cost += BOMBS[bombid].cost;
        } else {
            bombs--;  // WAにはならない前提
            int bombid = op.xyz;
            for (auto drc : BOMBS[bombid].ranges) {
                point pt = hulk + drc;
                if (!ingrid(pt)) continue;
                tbl[pt.r][pt.c] = '.';
            }
        }
    }
    return {move_cost, bomb_cost};
}
int bomb_place_id(point p, int b) {
    return b * N * N + p.r * N + p.c;
}
int bpid2bombid(int bpid) {
    return bpid / N2;
}
point bpid2point(int bpid) {
    return point{(bpid / N) % N, bpid % N};
}
namespace bomb_place_ns {

// buildingと書くのがタイプ数多いのでwallとしておく
uint16_t bpid2walls[NNM][N2];
uint16_t bpid2wall_size[NNM];
uint16_t wall2bpids[N2][NNM];
uint16_t wall2bpid_size[N2];
uint16_t good_bpids[NNM];
uint16_t good_bpid_size;
void push_bpid2walls(uint16_t bpid, uint16_t wall) {
    bpid2walls[bpid][bpid2wall_size[bpid]] = wall;
    bpid2wall_size[bpid]++;
}
void push_wall2bpids(uint16_t wall, uint16_t bpid) {
    wall2bpids[wall][wall2bpid_size[wall]] = bpid;
    wall2bpid_size[wall]++;
}
void push_goodbpids(uint16_t bpid) {
    good_bpids[good_bpid_size] = bpid;
    good_bpid_size++;
}
vector<int> hc_bomb_places(vector<int> init_bomb_places, vector<int> init_fillcnt) {
    // 破壊再構築系の山登り
    vector<int> bpid2cost(NNM);
    for (int bpid = 0; bpid < NNM; bpid++) {
        bpid2cost[bpid] = BOMBS[bpid2bombid(bpid)].cost;
    }

    int old_score = 0;
    auto bomb_places = init_bomb_places;
    auto fillcnt = init_fillcnt;
    for (auto bpid : bomb_places) {
        old_score += -bpid2cost[bpid];
    }
    debug1(old_score);
    double begin_time = marathon::now();
    double end_time = min(1500.0, begin_time + 1000);

    int hc_iter = 0;
    int hc_accept = 0;
    static uint16_t bpid_cnt[NNM];
    while (marathon::now() < end_time) {
        hc_iter++;
        vector<int> new_bomb_places = bomb_places;
        auto new_fillcnt = fillcnt;
        vector<int> notfilled;
        int new_score = old_score;

        int rmnum = marathon::randint(4, 6);
        bitset<NNM> removed_bpids = 0;
        for (int r = 0; r < rmnum; r++) {
            int remove_bpid = marathon::random_choice(new_bomb_places);
            removed_bpids[remove_bpid] = 1;
            new_bomb_places.erase(std::remove(new_bomb_places.begin(), new_bomb_places.end(), remove_bpid), new_bomb_places.end());
            new_score += bpid2cost[remove_bpid];
            for (int _wid = 0; _wid < bpid2wall_size[remove_bpid]; _wid++) {
                int pt = bpid2walls[remove_bpid][_wid];
                new_fillcnt[pt]--;
                if (new_fillcnt[pt] == 0) notfilled.push_back(pt);
            }
        }

        int added = 0;
        int added_must_change = rmnum - 1;
        int changed = 0;
        while (notfilled.size()) {  // この中の処理が非常に重い
            for (int _gid = 0; _gid < good_bpid_size; _gid++) {
                int bpid = good_bpids[_gid];
                bpid_cnt[bpid] = 0;
            }

            for (auto wall : notfilled) {
                for (int _bid = 0; _bid < wall2bpid_size[wall]; _bid++) {
                    int bpid = wall2bpids[wall][_bid];
                    bpid_cnt[bpid]++;
                }
            }

            int bestbpid = 0;
            int bestscore = -inf;
            for (int _gid = 0; _gid < good_bpid_size; _gid++) {
                int bpid = good_bpids[_gid];
                if (changed == 0 && added == added_must_change && removed_bpids[bpid]) continue;
                if (bpid_cnt[bpid] > 0) {
                    // int score = -1000 * marathon::uniform(1.0, 2.0) * bpid2cost[bpid] / bpid_cnt[bpid];
                    int score = -1000 * bpid2cost[bpid] / bpid_cnt[bpid];
                    if (bestscore < score) {
                        bestscore = score;
                        bestbpid = bpid;
                    }
                }
            }

            for (int _wid = 0; _wid < bpid2wall_size[bestbpid]; _wid++) {
                int wall = bpid2walls[bestbpid][_wid];
                new_fillcnt[wall]++;
                if (new_fillcnt[wall] == 1) {
                    notfilled.erase(std::remove(notfilled.begin(), notfilled.end(), wall), notfilled.end());
                }
            }
            new_score -= bpid2cost[bestbpid];
            new_bomb_places.push_back(bestbpid);
            changed += 1 - removed_bpids[bestbpid];
            added++;
        }
        if (new_score >= old_score) {
            old_score = new_score;
            bomb_places = new_bomb_places;
            fillcnt = new_fillcnt;
            hc_accept++;
        }
    }
    debug3(hc_iter, hc_accept, old_score);
    return bomb_places;
}

vector<int> make_bomb_places() {
    // 詰み防止のため建物がなくなるまで破壊してはいけない店舗を1個だけ決めておく
    vector<bool> is_hub_shop(N2);
    if (0) {
        point center = {12, 12};
        pair<int, point> minshop = {inf, {-1, -1}};
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (TBL_INIT[r][c] == '@') {
                    point now = {r, c};
                    int distance = abs(center.r - now.r) + abs(center.c - now.c);
                    minshop = min(minshop, {distance, now});
                }
            }
        }
        is_hub_shop[_p(minshop.second)] = true;
    }

    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            for (int b = 0; b < M; b++) {
                point place = point{r, c};
                int bpid = bomb_place_id(place, b);
                // ハブ店を破壊する爆弾配置は除外する
                bool valid = true;
                for (auto drc : BOMBS[b].ranges) {
                    point pt = place + drc;
                    if (!ingrid(pt)) continue;
                    if (is_hub_shop[_p(pt)]) valid = false;
                }
                if (!valid) continue;
                for (auto drc : BOMBS[b].ranges) {
                    point pt = place + drc;
                    if (!ingrid(pt)) continue;
                    if (TBL_INIT[pt.r][pt.c] != '#') continue;
                    push_bpid2walls(bpid, _p(pt));
                    push_wall2bpids(_p(pt), bpid);
                }
            }
        }
    }

    // 初期解を作る
    // 破壊できる確率が低い建物を破壊できたときのスコアを高く見積もる
    vector<int> wall_score(N2);
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            int u = _p(r, c);
            if (wall2bpid_size[u]) {
                wall_score[u] = 2e5 / wall2bpid_size[u];
            }
        }
    }
    int all_walls = 0;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            if (TBL_INIT[r][c] == '#') all_walls++;
        }
    }

    {  // よい爆弾位置を絞る
        vector<pair<double, int>> cand;
        for (int bpid = 0; bpid < NNM; bpid++) {
            int ws = 0;
            for (int _wid = 0; _wid < bpid2wall_size[bpid]; _wid++) {
                int wall = bpid2walls[bpid][_wid];
                ws += wall_score[wall];
            }
            double score = -1.0 * BOMBS[bpid2bombid(bpid)].cost / ws;
            cand.push_back({score, bpid});
        }
        sort(cand.rbegin(), cand.rend());
        const int usenum = NNM / 3;
        for (int i = 0; i < usenum; i++) {
            push_goodbpids(cand[i].second);
        }
    }
    {
        // good_bpidしか存在しないことにして再計算
        {
            vector<int> wallcnts(N2);
            for (int _gid = 0; _gid < good_bpid_size; _gid++) {
                int bpid = good_bpids[_gid];
                for (int _wid = 0; _wid < bpid2wall_size[bpid]; _wid++) {
                    int wall = bpid2walls[bpid][_wid];
                    wallcnts[wall]++;
                }
            }
            for (int u = 0; u < N2; u++) {
                wall_score[u] = 2e5 / wallcnts[u];
            }
        }
        {
            for (int u = 0; u < N2; u++) {
                wall2bpid_size[u] = 0;
            }
            for (int _gid = 0; _gid < good_bpid_size; _gid++) {
                int bpid = good_bpids[_gid];
                for (int _wid = 0; _wid < bpid2wall_size[bpid]; _wid++) {
                    int wall = bpid2walls[bpid][_wid];
                    push_wall2bpids(wall, bpid);
                }
            }
        }
    }

    vector<int> bomb_places;
    vector<int> fillcnt(N2);
    {
        bsn2 filled = 0;
        while (filled.count() < all_walls) {
            double bestscore = -1e18;
            int bestbpid = -1;
            vector<pair<double, int>> topbpids;
            for (int _gid = 0; _gid < good_bpid_size; _gid++) {
                int bpid = good_bpids[_gid];
                int ws = 0;
                for (int _wid = 0; _wid < bpid2wall_size[bpid]; _wid++) {
                    int wall = bpid2walls[bpid][_wid];
                    if (!filled[wall]) {
                        ws += wall_score[wall];
                    }
                }
                if (ws > 0) {
                    double score = -1.0 * BOMBS[bpid2bombid(bpid)].cost / ws;
                    if (bestscore < score) {
                        bestscore = score;
                        bestbpid = bpid;
                    }
                }
            }
            bomb_places.push_back(bestbpid);
            for (int _wid = 0; _wid < bpid2wall_size[bestbpid]; _wid++) {
                int wall = bpid2walls[bestbpid][_wid];
                fillcnt[wall]++;
                filled[wall] = 1;
            }
        }
    }
    debug2("greedy_end", marathon::now());
    return hc_bomb_places(bomb_places, fillcnt);
}
}  // namespace bomb_place_ns

void dprestore(vector<int> route, vector<int> bomb_places, vector<vector<pii>> frm, vector<vector<point>> &midshops,
               vector<operation_t> &ops, vector<vector<char>> &ops_tbl, point &ops_hulk) {
    vector<pii> dpstates;
    {
        int hasbomb = 0;
        int r = int(route.size()) - 2;
        dpstates.push_back({hasbomb, r});
        while (r > 0) {
            dpstates.push_back(frm[hasbomb][r]);
            tie(hasbomb, r) = frm[hasbomb][r];
        }
    }

    reverse(dpstates.begin(), dpstates.end());

    int m = dpstates.size();
    for (int i = 1; i < m; i++) {
        int hasbomb, r;
        tie(hasbomb, r) = dpstates[i];

        int bpid = bomb_places[route[r]];
        point bombpt = bpid2point(bpid);
        int pre_bombs = dpstates[i - 1].first;

        if (pre_bombs == 0) {
            point shop = midshops[hasbomb][r];
            int mind = inf;
            dij_goto_ops(ops_hulk, shop, ops, ops_tbl);

            int buynum = hasbomb + 1;
            for (int future = i; future < i + buynum; future++) {
                int fr = dpstates[future].second;
                int fbombid = bpid2bombid(bomb_places[route[fr]]);
                ops.push_back({2, fbombid});
            }

            dij_goto_ops(ops_hulk, bombpt, ops, ops_tbl);
        } else {
            dij_goto_ops(ops_hulk, bombpt, ops, ops_tbl);
        }
        int bombid = bpid2bombid(bomb_places[route[r]]);
        ops.push_back({3, bombid});
        for (auto drc : BOMBS[bombid].ranges) {
            point pt = ops_hulk + drc;
            if (!ingrid(pt)) continue;
            ops_tbl[pt.r][pt.c] = '.';
        }
    }
}
double route_move(vector<int> &route, vector<int> &bomb_places, bool do_restore, vector<operation_t> &ops, vector<vector<char>> &ops_tbl, point &ops_hulk) {
    // ABCの典型っぽい。 中間点を通る最短経路問題 + 爆弾を買う個数をDP

    point hulk = {0, 0};
    vector<vector<char>> tbl(N, vector<char>(N));
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            tbl[r][c] = TBL_INIT[r][c];
        }
    }
    int cost = 0;
    int m = route.size();
    const int BUYMAX = 5;
    vector<vector<int>> dp(BUYMAX, vector<int>(route.size(), inf));
    vector<vector<pii>> frm(BUYMAX, vector<pii>(route.size()));
    vector<vector<point>> midshops(BUYMAX, vector<point>(route.size()));
    dp[0][0] = 0;
    for (int r = 1; r < int(route.size()) - 1; r++) {
        int bpid = bomb_places[route[r]];
        point bombpt = bpid2point(bpid);
        auto cost_hulk = dij_cost(hulk, tbl);
        auto cost_bomb = dij_cost(bombpt, tbl);

        {
            // 爆弾持ってないので、途中で店に寄る
            for (int buy = 1; buy <= BUYMAX; buy++) {
                int now_mincost = inf;
                point bestshop = {-1, -1};
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        if (tbl[r][c] == '@') {
                            int curcost = cost_hulk[r][c] + cost_bomb[r][c] * (buy + 1) * (buy + 1);
                            if (now_mincost > curcost) {
                                now_mincost = curcost;
                                bestshop = {r, c};
                            }
                        }
                    }
                }
                midshops[buy - 1][r] = bestshop;
                int dptrans = dp[0][r - 1] + now_mincost;
                if (dp[buy - 1][r] > dptrans) {
                    dp[buy - 1][r] = dptrans;
                    frm[buy - 1][r] = {0, r - 1};
                }
            }
        }
        {
            // 爆弾持ってるので直接移動
            for (int hasbomb = 1; hasbomb <= BUYMAX - 1; hasbomb++) {
                int dptrans = dp[hasbomb][r - 1] + cost_hulk[bombpt.r][bombpt.c] * (hasbomb + 1) * (hasbomb + 1);
                if (dp[hasbomb - 1][r] > dptrans) {
                    dp[hasbomb - 1][r] = dptrans;
                    frm[hasbomb - 1][r] = {hasbomb, r - 1};
                }
            }
        }

        for (auto drc : BOMBS[bpid2bombid(bpid)].ranges) {
            point pt = bombpt + drc;
            if (!ingrid(pt)) continue;
            tbl[pt.r][pt.c] = '.';
        }
        hulk = bombpt;
    }
    if (do_restore) {
        // 復元を実施する
        dprestore(route, bomb_places, frm, midshops, ops, ops_tbl, ops_hulk);
    }
    return dp[0][int(route.size()) - 2];
}
vector<int> bomb_places_tsp(vector<int> bomb_places) {
    vector<operation_t> dummy_ops;
    vector<vector<char>> dummy_ops_tbl;
    point dummy_ops_hulk = {0, 0};

    int m = bomb_places.size() + 2;

    int start = m - 2;
    int goal = m - 1;
    vector<int> best_route;
    double best_score = -1e18;
    int route_search_iter = 0;
    while (marathon::now() < 2400) {
        route_search_iter++;

        point ini = {0, 0};
        vector<vector<int>> costtbl(m, vector<int>(m));
        vector<point> all_shops;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (TBL_INIT[r][c] == '@') all_shops.push_back({r, c});
            }
        }

        {
            vector<point> shops = all_shops;
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < m - 1; j++) {
                    point src = i == start ? ini : bpid2point(bomb_places[i]);
                    point dest = j == start ? ini : bpid2point(bomb_places[j]);

                    int mincost = inf;
                    for (auto shop : shops) {
                        int cost = abs(src.r - shop.r) + abs(src.c - shop.c) + abs(dest.r - shop.r) + abs(dest.c - shop.c);
                        mincost = min(mincost, cost);
                    }
                    costtbl[i][j] = mincost;
                }
            }
        }
        vector<vector<int>> shoperase(m);
        {
            map<point, int> shopid_map;
            for (int s = 0; s < int(all_shops.size()); s++) {
                shopid_map[all_shops[s]] = s;
            }
            for (int i = 0; i < m - 2; i++) {
                int bid = bpid2bombid(bomb_places[i]);
                point place = bpid2point(bomb_places[i]);
                for (auto drc : BOMBS[bid].ranges) {
                    point pt = place + drc;
                    if (!ingrid(pt)) continue;
                    if (TBL_INIT[pt.r][pt.c] == '@') {
                        assert(shopid_map.count(pt));
                        shoperase[i].push_back(shopid_map[pt]);
                    }
                }
            }
        }

        double begin_temp = 5;
        double end_temp = 0.5;

        auto route_evaluate = [&](vector<int> &route_) {
            vector<bool> shoperased(all_shops.size());
            int total_cost = 0;
            for (int r = 1; r < int(route_.size()) - 1; r++) {
                point pre = bpid2point(bomb_places[route_[r - 1]]);
                point cur = bpid2point(bomb_places[route_[r]]);
                int cost = 1e6;
                for (int s = 0; s < int(all_shops.size()); s++) {
                    if (shoperased[s]) continue;
                    // 爆弾を1個だけ買うと仮定。建物はないと仮定。
                    auto shop = all_shops[s];
                    int scost = (abs(shop.r - pre.r) + abs(shop.c - pre.c)) + 4 * (abs(shop.r - cur.r) + abs(shop.c - cur.c));
                    cost = min(cost, scost);
                }
                total_cost += cost;
                for (auto s : shoperase[route_[r]]) {
                    shoperased[s] = true;
                }
            }
            return -total_cost;
        };

        // コストを雑推定するTSP
        vector<int> route;
        route.push_back(start);
        {
            vector<int> perm(m - 2);
            iota(perm.begin(), perm.end(), 0);
            shuffle(perm.begin(), perm.end(), marathon::engine);
            for (auto r : perm) {
                route.push_back(r);
            }
        }
        route.push_back(goal);

        int anneal_accepted = 0;
        int anneal_iter = 0;
        double old_score = 0;
        for (int r = 1; r < int(route.size()); r++) {
            old_score -= costtbl[route[r - 1]][route[r]];
        }
        while (anneal_iter < 100000) {
            anneal_iter++;
            vector<int> new_route = route;
            int x = 0;
            int y = 0;
            while (x == y) {
                x = 1 + marathon::engine() % (int(new_route.size()) - 2);
                y = 1 + marathon::engine() % (int(new_route.size()) - 2);
            }
            if (x > y) {
                swap(x, y);
            }
            for (int i = x + 1; i <= y - 1; i++) {
                int j = y - 1 - (i - (x + 1));
                if (i > j) break;
                swap(new_route[i], new_route[j]);
            }

            double new_score = 0;
            for (int r = 1; r < int(new_route.size()); r++) {
                new_score -= costtbl[new_route[r - 1]][new_route[r]];
            }
            if (marathon::anneal_accept(new_score, old_score, anneal_iter, 0, 50000, begin_temp, end_temp)) {
                route = new_route;
                old_score = new_score;
                anneal_accepted++;
            }
        }

        begin_temp = 0.1;
        end_temp = 0.01;
        anneal_accepted = 0;
        anneal_iter = 0;
        old_score = route_evaluate(route);
        while (anneal_iter < 5000) {
            anneal_iter++;
            vector<int> new_route = route;
            int x = 0;
            int y = 0;
            while (x == y) {
                x = 1 + marathon::engine() % (int(new_route.size()) - 2);
                y = 1 + marathon::engine() % (int(new_route.size()) - 2);
            }
            if (x > y) {
                swap(x, y);
            }
            for (int i = x + 1; i <= y - 1; i++) {
                int j = y - 1 - (i - (x + 1));
                if (i > j) break;
                swap(new_route[i], new_route[j]);
            }

            double new_score = route_evaluate(new_route);
            if (marathon::anneal_accept(new_score, old_score, anneal_iter, 0, 5000, begin_temp, end_temp)) {
                route = new_route;
                old_score = new_score;
                anneal_accepted++;
            }
        }

        // 正しいコストで評価
        double now_score = -route_move(route, bomb_places, false, dummy_ops, dummy_ops_tbl, dummy_ops_hulk);
        if (best_score < now_score) {
            best_route = route;
            best_score = now_score;
            debug1(best_score);
        }
    }
    debug2(route_search_iter, best_score);
    return best_route;
}
void solve() {
    // 爆弾位置と爆弾IDからなる「爆弾配置」 の集合を山登りにより作る。
    // 爆弾配置は N*N*M 種類存在し、そこから全ての建物を破壊しつつ爆弾コストが小さい集合を選ぶ。
    vector<int> bomb_places = bomb_place_ns::make_bomb_places();

    vector<operation_t> ops;
    {
        point hulk = {0, 0};
        vector<vector<char>> tbl(N, vector<char>(N));
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                tbl[r][c] = TBL_INIT[r][c];
            }
        }
        {
            // 爆弾配置が決まったら、コストが動的に変化するTSP的な問題を解く。 
            vector<int> route = bomb_places_tsp(bomb_places);
            route_move(route, bomb_places, true, ops, tbl, hulk);
        }

        // 残った店を貪欲に破壊
        while (true) {
            vector<point> shops;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (tbl[r][c] == '@') shops.push_back({r, c});
                }
            }
            if (shops.size() == 0) break;

            pair<double, int> bestop = {1e18, -1};
            auto hulk_cost = dij_cost(hulk, tbl);
            vector<vector<point>> midshop(N, vector<point>(N, {-1, -1}));
            vector<vector<int>> move_cost(N, vector<int>(N, inf));
            for (auto shop : shops) {
                auto shop_cost = dij_cost(shop, tbl);
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        int cost = shop_cost[r][c] * 4 + hulk_cost[shop.r][shop.c];
                        if (move_cost[r][c] > cost) {
                            move_cost[r][c] = cost;
                            midshop[r][c] = shop;
                        }
                    }
                }
            }
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    point place = {r, c};
                    for (int bid = 0; bid < M; bid++) {
                        int break_shop = 0;
                        int break_hub_shop = 0;
                        for (auto drc : BOMBS[bid].ranges) {
                            point pt = place + drc;
                            if (!ingrid(pt)) continue;
                            if (tbl[pt.r][pt.c] == '@') break_shop++;
                        }
                        // (移動コスト+爆弾コスト)/破壊する店数  が最小の爆弾配置を選ぶ
                        double score = 1.0 * (move_cost[r][c] + BOMBS[bid].cost) / break_shop;
                        bestop = min(bestop, {score, bomb_place_id(place, bid)});
                    }
                }
            }
            {
                int bpid = bestop.second;
                int bombid = bpid / N2;
                point bombpt = bpid2point(bpid);
                dij_goto_ops(hulk, midshop[bombpt.r][bombpt.c], ops, tbl);
                ops.push_back({2, bombid});
                dij_goto_ops(hulk, bombpt, ops, tbl);
                ops.push_back({3, bombid});
                for (auto drc : BOMBS[bombid].ranges) {
                    point pt = hulk + drc;
                    if (!ingrid(pt)) continue;
                    tbl[pt.r][pt.c] = '.';
                }
            }
        }
    }
    {
        cout << ops.size() << endl;
        for (auto op : ops) {
            if (op.kind == 1) {
                char d = '.';
                if (op.xyz == _L_) d = 'L';
                if (op.xyz == _R_) d = 'R';
                if (op.xyz == _U_) d = 'U';
                if (op.xyz == _D_) d = 'D';
                cout << op.kind << " " << d << endl;
            } else {
                cout << op.kind << " " << op.xyz + 1 << endl;
            }
        }
    }
    {
        int move_cost, bomb_cost;
        tie(move_cost, bomb_cost) = evaluate_ops(ops);
        int totalcost = move_cost + bomb_cost;
        int score = 1e12 / (1e4 + totalcost);
        cerr << "score==" << score << " move_cost==" << move_cost << " bomb_cost==" << bomb_cost << " time==" << marathon::now() << endl;
    }
}
int main() {
    marathon::marathon_init();
    int n, m;
    cin >> n >> m;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            cin >> TBL_INIT[r][c];
        }
    }
    for (int b = 0; b < M; b++) {
        int c, l;
        cin >> c >> l;
        bomb_t bomb;
        bomb.cost = c;
        for (int i = 0; i < l; i++) {
            int dr, dc;
            cin >> dr >> dc;
            bomb.ranges.push_back({dr, dc});
        }
        BOMBS[b] = bomb;
    }
    init_data();
    solve();
}
0