#1187910 (C++23) No.3738 Right Hamiltonian

• 問題: No.3738 Right Hamiltonian
• ユーザー: uruzunyaa
• 提出日時: 2026-09-19 07:08:16
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 9,741 bytes
• コンパイル時間: 2,367 ms
• コンパイル使用メモリ: 361,644 KB
• 実行使用メモリ: 58,916 KB
• 最終ジャッジ日時: 2026-09-19 13:27:02
• 合計ジャッジ時間: 14,922 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

サブタスク	配点	結果
部分点	80 %	AC * 33 WA * 5
満点	20 %	AC * 44 WA * 6 TLE * 1 -- * 9
合計	4 * 0% = 0 点

ソースコード

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

struct Seg {
    int d;
    int r1, c1, r2, c2;
    int len;
};

int H, W;
vector<string> S;

// 各マスから U,R,D,L に、壁に当たるまで何歩進めるか
vector<array<unsigned short, 4>> go_len;

// 各候補のシミュレーションで使い回す
vector<Seg> buf;

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};
const char DCH[4] = {'U', 'R', 'D', 'L'};

const int INF = 1e9;


// (r,c) から d 方向に進んだとき、
// segment s のマスに初めてぶつかるまでの距離。
// ぶつからないなら INF。
int hitDist(int r, int c, int d, const Seg& s) {
    int rlo = min(s.r1, s.r2);
    int rhi = max(s.r1, s.r2);
    int clo = min(s.c1, s.c2);
    int chi = max(s.c1, s.c2);

    if (d == 0) { // U
        if (s.r1 == s.r2) {
            if (clo <= c && c <= chi && s.r1 < r) {
                return r - s.r1;
            }
        }
        else if (s.c1 == c) {
            int rr = min(rhi, r - 1);

            if (rlo <= rr) {
                return r - rr;
            }
        }
    }

    else if (d == 1) { // R
        if (s.c1 == s.c2) {
            if (rlo <= r && r <= rhi && s.c1 > c) {
                return s.c1 - c;
            }
        }
        else if (s.r1 == r) {
            int cc = max(clo, c + 1);

            if (cc <= chi) {
                return cc - c;
            }
        }
    }

    else if (d == 2) { // D
        if (s.r1 == s.r2) {
            if (clo <= c && c <= chi && s.r1 > r) {
                return s.r1 - r;
            }
        }
        else if (s.c1 == c) {
            int rr = max(rlo, r + 1);

            if (rr <= rhi) {
                return rr - r;
            }
        }
    }

    else { // L
        if (s.c1 == s.c2) {
            if (rlo <= r && r <= rhi && s.c1 < c) {
                return c - s.c1;
            }
        }
        else if (s.r1 == r) {
            int cc = min(chi, c - 1);

            if (clo <= cc) {
                return c - cc;
            }
        }
    }

    return INF;
}


// sign = +1:
//     直進できる限り直進 → 右折
//
// sign = -1:
//     直進できる限り直進 → 左折
//
// 左折版が完成した場合は最後に経路を逆転する。
bool simulate(
    int sr,
    int sc,
    int first_dir,
    int sign,
    int N,
    int& seg_cnt
) {
    int r = sr;
    int c = sc;
    int d = first_dir;

    int cnt = 1;
    int m = 0;

    // 同じ向きに曲がり続ける単純な螺旋では
    // 線分数は O(H+W)。
    int seg_limit = 4 * (H + W) + 20;

    while (cnt < N && m < seg_limit) {
        int L = go_len[r * W + c][d];

        // 螺旋では、次に衝突し得る既訪問部分は
        // 直近5本の線分のどれか。
        for (int j = max(0, m - 5); j < m; j++) {
            int k = hitDist(r, c, d, buf[j]);

            if (k <= L) {
                L = k - 1;
            }
        }

        if (L <= 0) {
            return false;
        }

        int nr = r + dr[d] * L;
        int nc = c + dc[d] * L;

        buf[m++] = {
            d,
            r,
            c,
            nr,
            nc,
            L
        };

        cnt += L;

        if (cnt > N) {
            return false;
        }

        r = nr;
        c = nc;

        if (cnt == N) {
            seg_cnt = m;
            return true;
        }

        d = (d + sign + 4) % 4;
    }

    return false;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> H >> W;

    S.resize(H);

    for (auto& s : S) {
        cin >> s;
    }


    vector<int> floor_cells;

    int N = 0;
    int color[2] = {};

    for (int r = 0; r < H; r++) {
        for (int c = 0; c < W; c++) {
            if (S[r][c] == '.') {
                floor_cells.push_back(r * W + c);

                N++;

                color[(r + c) & 1]++;
            }
        }
    }


    // 床が1マスだけ
    if (N == 1) {
        int v = floor_cells[0];

        cout << v / W + 1 << ' '
             << v % W + 1 << " U\n";

        cout << 0 << '\n';
        cout << '\n';

        return 0;
    }


    // 普通の Hamilton path としても必要な条件
    if (abs(color[0] - color[1]) > 1) {
        cout << -1 << '\n';
        return 0;
    }


    int leaves = 0;

    for (int v : floor_cells) {
        int r = v / W;
        int c = v % W;

        int deg = 0;

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (0 <= nr && nr < H &&
                0 <= nc && nc < W &&
                S[nr][nc] == '.') {

                deg++;
            }
        }

        if (deg == 0) {
            cout << -1 << '\n';
            return 0;
        }

        if (deg == 1) {
            leaves++;
        }
    }

    if (leaves > 2) {
        cout << -1 << '\n';
        return 0;
    }


    // 連結判定
    {
        vector<char> seen(H * W, false);

        queue<int> q;

        q.push(floor_cells[0]);
        seen[floor_cells[0]] = true;

        int cnt = 0;

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            cnt++;

            int r = v / W;
            int c = v % W;

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                if (nr < 0 || nr >= H ||
                    nc < 0 || nc >= W) {

                    continue;
                }

                int u = nr * W + nc;

                if (S[nr][nc] == '.' && !seen[u]) {
                    seen[u] = true;
                    q.push(u);
                }
            }
        }

        if (cnt != N) {
            cout << -1 << '\n';
            return 0;
        }
    }


    // -----------------------------------------
    // 壁まで何歩直進できるか前計算
    // -----------------------------------------

    go_len.assign(H * W, {0, 0, 0, 0});


    // U, L
    for (int r = 0; r < H; r++) {
        for (int c = 0; c < W; c++) {
            if (S[r][c] == '#') {
                continue;
            }

            int v = r * W + c;

            if (r > 0 && S[r - 1][c] == '.') {
                go_len[v][0]
                    = go_len[(r - 1) * W + c][0] + 1;
            }

            if (c > 0 && S[r][c - 1] == '.') {
                go_len[v][3]
                    = go_len[r * W + c - 1][3] + 1;
            }
        }
    }


    // D, R
    for (int r = H - 1; r >= 0; r--) {
        for (int c = W - 1; c >= 0; c--) {
            if (S[r][c] == '#') {
                continue;
            }

            int v = r * W + c;

            if (r + 1 < H && S[r + 1][c] == '.') {
                go_len[v][2]
                    = go_len[(r + 1) * W + c][2] + 1;
            }

            if (c + 1 < W && S[r][c + 1] == '.') {
                go_len[v][1]
                    = go_len[r * W + c + 1][1] + 1;
            }
        }
    }


    buf.resize(4 * (H + W) + 25);


    vector<Seg> answer;

    int ans_sign = 0;


    // N が奇数なら始点・終点は市松模様の多数派色
    int need_color = -1;

    if (N & 1) {
        need_color =
            (color[0] > color[1] ? 0 : 1);
    }


    // -----------------------------------------
    // 開始マス × 最初の方向 × 回転方向を全探索
    // -----------------------------------------

    for (int sign : {1, -1}) {
        for (int v : floor_cells) {
            int sr = v / W;
            int sc = v % W;

            if (need_color != -1 &&
                ((sr + sc) & 1) != need_color) {

                continue;
            }

            for (int d = 0; d < 4; d++) {
                // 最初の実移動を F にしてよい。
                //
                // 本来最初が R だったとしても、
                // 初期方向をその1つ右にしておけば
                // 同じ経路を F から開始できる。
                if (go_len[v][d] == 0) {
                    continue;
                }

                int m = 0;

                if (simulate(
                    sr,
                    sc,
                    d,
                    sign,
                    N,
                    m
                )) {
                    answer.assign(
                        buf.begin(),
                        buf.begin() + m
                    );

                    ans_sign = sign;

                    goto FOUND;
                }
            }
        }
    }


    cout << -1 << '\n';
    return 0;


FOUND:

    vector<Seg> out;


    if (ans_sign == 1) {
        // 最初から右折 spiral
        out = answer;
    }

    else {
        // 左折 spiral を逆向きにすると
        // 右折 spiral になる
        for (int i = (int)answer.size() - 1;
             i >= 0;
             i--) {

            Seg s = answer[i];

            out.push_back({
                (s.d + 2) % 4,

                s.r2,
                s.c2,

                s.r1,
                s.c1,

                s.len
            });
        }
    }


    int sr = out[0].r1;
    int sc = out[0].c1;
    int sd = out[0].d;


    string X;

    X.reserve(N - 1);


    for (int i = 0; i < (int)out.size(); i++) {
        if (i == 0) {
            X.append(out[i].len, 'F');
        }

        else {
            // 新しい線分へ移る最初の1歩だけ R
            X.push_back('R');

            // 残りは直進
            X.append(out[i].len - 1, 'F');
        }
    }


    cout << sr + 1 << ' '
         << sc + 1 << ' '
         << DCH[sd] << '\n';

    cout << X.size() << '\n';
    cout << X << '\n';
}