提出 #73741401

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

struct RobotPlan {
    int si, sj;
    char dir;
    vector<char> cmd;
};

static constexpr int di[4] = {-1, 0, 1, 0};
static constexpr int dj[4] = {0, 1, 0, -1};

int main() {

    if (fopen("./inC/0000.txt", "r") != nullptr) {
        freopen("./inC/0004.txt", "r", stdin);
        freopen("./output.txt", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, AK, AM, AW;
    cin >> N >> AK >> AM >> AW;
    vector<string> v(N), h(N - 1);
    for (auto &s : v) cin >> s;
    for (auto &s : h) cin >> s;

    auto inside = [&](int x, int y) { return 0 <= x && x < N && 0 <= y && y < N; };
    auto passable = [&](int x, int y, int nd) {
        int nx = x + di[nd], ny = y + dj[nd];
        if (!inside(nx, ny)) return false;
        if (nd == 0) return h[x - 1][y] == '0';
        if (nd == 1) return v[x][y] == '0';
        if (nd == 2) return h[x][y] == '0';
        return v[x][y - 1] == '0';
    };
    auto cell_id = [&](int x, int y) { return x * N + y; };

    auto build_plan = [&](const vector<pair<int,int>> &roots, int node_cap) {
        vector<int> used(N * N, 0);
        vector<RobotPlan> plans;

        for (auto [si, sj] : roots) {
            if (used[cell_id(si, sj)]) continue;
            vector<pair<int,int>> nodes;
            queue<pair<int,int>> q;
            q.push({si, sj});
            used[cell_id(si, sj)] = 2; // queued
            while (!q.empty() && (int)nodes.size() < node_cap) {
                auto [x, y] = q.front(); q.pop();
                nodes.push_back({x, y});
                for (int d = 0; d < 4; ++d) {
                    if (!passable(x, y, d)) continue;
                    int nx = x + di[d], ny = y + dj[d], nid = cell_id(nx, ny);
                    if (used[nid] == 0) {
                        used[nid] = 2;
                        q.push({nx, ny});
                    }
                }
            }

            vector<int> in_nodes(N * N, 0), par(N * N, -1);
            for (auto [x, y] : nodes) in_nodes[cell_id(x, y)] = 1;
            stack<pair<int,int>> st;
            st.push({si, sj});
            par[cell_id(si, sj)] = cell_id(si, sj);
            vector<pair<int,int>> ord;
            while (!st.empty()) {
                auto [x, y] = st.top(); st.pop();
                ord.push_back({x, y});
                for (int d = 3; d >= 0; --d) {
                    if (!passable(x, y, d)) continue;
                    int nx = x + di[d], ny = y + dj[d], nid = cell_id(nx, ny);
                    if (!in_nodes[nid] || par[nid] != -1) continue;
                    par[nid] = cell_id(x, y);
                    st.push({nx, ny});
                }
            }

            vector<vector<pair<int,int>>> ch(N * N);
            for (auto [x, y] : ord) {
                int u = cell_id(x, y);
                if (u == par[u]) continue;
                ch[par[u]].push_back({x, y});
            }
            vector<pair<int,int>> walk;
            function<void(int,int)> dfs = [&](int x, int y) {
                walk.push_back({x, y});
                for (auto [nx, ny] : ch[cell_id(x, y)]) {
                    dfs(nx, ny);
                    walk.push_back({x, y});
                }
            };
            dfs(si, sj);
            if (walk.empty()) continue;

            int curd = 0;
            vector<char> cmd;
            auto wdir = [&](int x1,int y1,int x2,int y2){
                if (x2 == x1 - 1) return 0;
                if (y2 == y1 + 1) return 1;
                if (x2 == x1 + 1) return 2;
                return 3;
            };
            for (int i = 0; i + 1 < (int)walk.size(); ++i) {
                auto [x1, y1] = walk[i];
                auto [x2, y2] = walk[i + 1];
                int nd = wdir(x1, y1, x2, y2);
                int diff = (nd - curd + 4) % 4;
                if (diff == 1) cmd.push_back('R');
                else if (diff == 2) cmd.push_back('R'), cmd.push_back('R');
                else if (diff == 3) cmd.push_back('L');
                cmd.push_back('F');
                curd = nd;
            }
            int back = (0 - curd + 4) % 4;
            if (back == 1) cmd.push_back('R');
            else if (back == 2) cmd.push_back('R'), cmd.push_back('R');
            else if (back == 3) cmd.push_back('L');

            if (cmd.empty()) cmd.push_back('R');
            if ((int)cmd.size() > 1600) continue;

            for (auto [x, y] : walk) used[cell_id(x, y)] = 1;
            plans.push_back({si, sj, 'U', cmd});
        }

        // 处理遗漏格子（理论上较少）：用静态机器人补齐可行性。
        for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
            if (used[cell_id(i, j)] != 1) plans.push_back({i, j, 'U', {'R'}});
        }
        return plans;
    };

    // 子问题 C：K 和 W 很贵，优先少机器人 + 多状态。
    // 先尝试 1 机器人；若超状态限制则退化到 2~3 机器人分块。
    vector<RobotPlan> plans = build_plan({{0, 0}}, 400);
    int heavy = 0;
    for (auto &p : plans) if ((int)p.cmd.size() > 1) ++heavy;
    if ((int)plans.size() > 1 || heavy == 0) {
        plans = build_plan({{0, 0}, {N - 1, N - 1}}, 230);
        if ((int)plans.size() > 3) {
            plans = build_plan({{0, 0}, {0, N - 1}, {N - 1, 0}}, 170);
        }
    }

    cout << plans.size() << '\n';
    for (auto &p : plans) {
        int m = (int)p.cmd.size();
        cout << m << ' ' << p.si << ' ' << p.sj << ' ' << p.dir << '\n';
        for (int s = 0; s < m; ++s) {
            char a0 = p.cmd[s];
            int b0 = (s + 1) % m;
            char a1 = (a0 == 'F' ? 'R' : a0);
            int b1 = (s + 1) % m;
            cout << a0 << ' ' << b0 << ' ' << a1 << ' ' << b1 << '\n';
        }
    }

    for (int i = 0; i < N; ++i) cout << string(N - 1, '0') << '\n';
    for (int i = 0; i < N - 1; ++i) cout << string(N, '0') << '\n';
    return 0;
}

提出情報

ジャッジ結果