#1173339 (C++23(gcc16)) No.3738 Right Hamiltonian

• 問題: No.3738 Right Hamiltonian
• ユーザー: 👑 kencho
• 提出日時: 2026-07-24 23:07:30
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 764 ms / 2,000 ms
• コード長: 13,070 bytes
• コンパイル時間: 3,790 ms
• コンパイル使用メモリ: 366,292 KB
• 実行使用メモリ: 61,824 KB
• 最終ジャッジ日時: 2026-09-19 12:37:14
• 合計ジャッジ時間: 10,275 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

サブタスク	配点	結果
部分点	80 %	AC * 38
満点	20 %	AC * 60
合計	4 * 100% = 400 点

ソースコード

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

int H, W, N, r0, r1, c0, c1;
vector<string> G;
vector<array<uint16_t, 4>> runlen;
vector<unsigned char> used;

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

inline int id(int r, int c) { return r * W + c; }
inline int row(int p) { return p / W; }
inline int col(int p) { return p % W; }

inline int go(int p, int d) {
    int r = row(p) + dr[d], c = col(p) + dc[d];
    return 0 <= r && r < H && 0 <= c && c < W ? id(r, c) : -1;
}

int dir(int a, int b) {
    int x = row(b) - row(a), y = col(b) - col(a);
    for (int d = 0; d < 4; d++)
        if (x == dr[d] && y == dc[d]) return d;
    return -1;
}

// 外接長方形の外周を時計回りに列挙する
vector<int> perimeter() {
    vector<int> p;
    for (int c = c0; c < c1; c++) p.push_back(id(r0, c));
    for (int r = r0; r < r1; r++) p.push_back(id(r, c1));
    for (int c = c1; c > c0; c--) p.push_back(id(r1, c));
    for (int r = r1; r > r0; r--) p.push_back(id(r, c0));
    return p;
}

// turn=-1: 左折, turn=+1: 右折
vector<int> trace(int st, int d, int turn,
                  unsigned char tag, int &cnt) {
    vector<int> ret;
    int p = st;

    while (true) {
        int q = go(p, d);

        if (q != -1 && G[row(q)][col(q)] == '.' && used[q] != tag) {
            used[q] = tag;
            ++cnt;
            ret.push_back(q);
            p = q;
            continue;
        }

        int nd = (d + turn + 4) % 4;
        q = go(p, nd);

        if (q != -1 && G[row(q)][col(q)] == '.' && used[q] != tag) {
            d = nd;
            used[q] = tag;
            ++cnt;
            ret.push_back(q);
            p = q;
        } else {
            break;
        }
    }

    return ret;
}

bool valid(const vector<int> &p) {
    if ((int)p.size() != N) return false;

    fill(used.begin(), used.end(), 0);
    int last = -1;

    for (int i = 0; i < N; i++) {
        int x = p[i];

        if (x < 0 || G[row(x)][col(x)] != '.' || used[x])
            return false;

        used[x] = 1;

        if (i) {
            int d = dir(p[i - 1], x);

            if (d < 0 ||
                (last != -1 && d != last && d != (last + 1) % 4))
                return false;

            last = d;
        }
    }

    return true;
}

// 外周が真の部分区間 arc である場合
bool try_arc(const vector<int> &arc, int order, vector<int> &ans) {
    unsigned char tag = order + 1;
    int cnt = 0;

    for (int x : arc) {
        used[x] = tag;
        ++cnt;
    }

    int A = arc.front(), B = arc.back();
    int first_dir = dir(arc[0], arc[1]);
    int last_dir = dir(arc[arc.size() - 2], arc.back());

    vector<int> pre, suf;

    if (order == 0) {
        pre = trace(A, (first_dir + 2) % 4, -1, tag, cnt);
        suf = trace(B, last_dir, +1, tag, cnt);
    } else {
        suf = trace(B, last_dir, +1, tag, cnt);
        pre = trace(A, (first_dir + 2) % 4, -1, tag, cnt);
    }

    if (cnt != N) return false;

    ans.clear();
    ans.reserve(N);

    for (auto it = pre.rbegin(); it != pre.rend(); ++it)
        ans.push_back(*it);

    ans.insert(ans.end(), arc.begin(), arc.end());
    ans.insert(ans.end(), suf.begin(), suf.end());

    return valid(ans);
}

struct Rect {
    int u, d, l, r;
};

struct Seg {
    int sr, sc, er, ec, dir, len;
};

inline bool inside(const Rect &z, int r, int c) {
    return z.u <= r && r <= z.d && z.l <= c && c <= z.r;
}

// 現在位置から方向 d へ進める極大長。
// 過去の経路で当たり得るのは 3 区間前だけ。
int getlen(int r, int c, int d,
           const Rect &z, const vector<Seg> &seg) {
    int x = r + dr[d], y = c + dc[d];

    if (!inside(z, x, y) || G[x][y] == '#')
        return 0;

    int cap;

    if (d == 0) cap = x - z.u + 1;
    else if (d == 1) cap = z.r - y + 1;
    else if (d == 2) cap = z.d - x + 1;
    else cap = y - z.l + 1;

    int len = min<int>(runlen[id(x, y)][d], cap);
    int j = seg.size();

    if (j >= 3) {
        const Seg &old = seg[j - 3];

        if (d & 1) {
            // 今回は横、old は縦
            if (old.sc != old.ec) return -1;

            if (min(old.sr, old.er) <= r &&
                r <= max(old.sr, old.er)) {
                int dist = (old.sc - c) * dc[d];

                if (dist == 0) return -1;
                if (dist > 0) len = min(len, dist - 1);
            }
        } else {
            // 今回は縦、old は横
            if (old.sr != old.er) return -1;

            if (min(old.sc, old.ec) <= c &&
                c <= max(old.sc, old.ec)) {
                int dist = (old.sr - r) * dr[d];

                if (dist == 0) return -1;
                if (dist > 0) len = min(len, dist - 1);
            }
        }
    }

    return len;
}

// 長方形 z 内の全床マスを、内向きスパイラルで被覆できるか
bool arm(const Rect &z, int st, int heading, int turn,
         int need, vector<Seg> &seg) {
    seg.clear();

    int r = row(st), c = col(st);
    int d = heading, got = 0;
    bool first = true;

    while (true) {
        int len = getlen(r, c, d, z, seg);

        // 最初だけ、直進できなければ 1 回曲がってよい
        if (first && len == 0) {
            d = (d + turn + 4) % 4;
            len = getlen(r, c, d, z, seg);
        }
        first = false;

        if (len < 0) return false;
        if (len == 0) break;

        int j = seg.size();

        // 内向きスパイラルの必要条件
        if (j >= 2 && len >= seg[j - 2].len)
            return false;

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

        seg.push_back({r, c, nr, nc, d, len});

        got += len;
        if (got > need) return false;

        r = nr;
        c = nc;
        d = (d + turn + 4) % 4;
    }

    return got == need;
}

void append_reverse(vector<int> &ans, const vector<Seg> &seg) {
    for (int i = (int)seg.size() - 1; i >= 0; i--) {
        int r = seg[i].er, c = seg[i].ec;
        int d = seg[i].dir;

        for (int k = 0; k < seg[i].len; k++) {
            ans.push_back(id(r, c));
            r -= dr[d];
            c -= dc[d];
        }
    }
}

void append_forward(vector<int> &ans, const vector<Seg> &seg) {
    for (const Seg &s : seg) {
        int r = s.sr, c = s.sc;

        for (int k = 0; k < s.len; k++) {
            r += dr[s.dir];
            c += dc[s.dir];
            ans.push_back(id(r, c));
        }
    }
}

// 外周全体が床の場合
bool solve_full(const vector<int> &per, vector<int> &ans) {
    int P = per.size();

    int iu = r0 + 1, idn = r1 - 1;
    int il = c0 + 1, ir = c1 - 1;

    vector<int> colsum(W + 1), rowsum(H + 1);
    int inner = 0;

    if (iu <= idn && il <= ir) {
        for (int r = iu; r <= idn; r++) {
            for (int c = il; c <= ir; c++) {
                if (G[r][c] == '.') {
                    ++colsum[c + 1];
                    ++rowsum[r + 1];
                    ++inner;
                }
            }
        }
    }

    for (int c = 0; c < W; c++)
        colsum[c + 1] += colsum[c];

    for (int r = 0; r < H; r++)
        rowsum[r + 1] += rowsum[r];

    vector<Seg> sa, sb;
    sa.reserve(H + W + 5);
    sb.reserve(H + W + 5);

    // per[cut] -> per[cut+1] を使わない辺とする
    for (int cut = 0; cut < P; cut++) {
        int A = per[(cut + 1) % P];
        int B = per[cut];

        int ar = row(A), ac = col(A);
        int br = row(B), bc = col(B);

        Rect RA, RB;
        int needA, needB;

        if (ar == br) {
            // 水平な切れ目。内側を左右に分割
            int x = max(ac, bc);

            Rect L{iu, idn, il, x - 1};
            Rect R{iu, idn, x, ir};

            int cntL = (iu <= idn && il <= x - 1)
                         ? colsum[x] - colsum[il]
                         : 0;
            int cntR = inner - cntL;

            if (ac >= x) {
                RA = R; RB = L;
                needA = cntR; needB = cntL;
            } else {
                RA = L; RB = R;
                needA = cntL; needB = cntR;
            }
        } else {
            // 垂直な切れ目。内側を上下に分割
            int x = max(ar, br);

            Rect U{iu, x - 1, il, ir};
            Rect D{x, idn, il, ir};

            int cntU = (il <= ir && iu <= x - 1)
                         ? rowsum[x] - rowsum[iu]
                         : 0;
            int cntD = inner - cntU;

            if (ar >= x) {
                RA = D; RB = U;
                needA = cntD; needB = cntU;
            } else {
                RA = U; RB = D;
                needA = cntU; needB = cntD;
            }
        }

        int first_dir = dir(A, per[(cut + 2) % P]);
        int last_dir = dir(per[(cut - 1 + P) % P], B);

        if (!arm(RA, A, (first_dir + 2) % 4, -1, needA, sa))
            continue;

        if (!arm(RB, B, last_dir, +1, needB, sb))
            continue;

        ans.clear();
        ans.reserve(N);

        append_reverse(ans, sa);

        for (int j = 0; j < P; j++)
            ans.push_back(per[(cut + 1 + j) % P]);

        append_forward(ans, sb);

        if (valid(ans))
            return true;
    }

    return false;
}

void output(const vector<int> &path) {
    int initial_dir = 0;
    string command;
    command.reserve(max(0, N - 1));

    if (N >= 2) {
        initial_dir = dir(path[0], path[1]);
        int current = initial_dir;

        for (int i = 1; i < N; i++) {
            int nd = dir(path[i - 1], path[i]);

            if (nd == current)
                command.push_back('F');
            else
                command.push_back('R');

            current = nd;
        }
    }

    static const char name[] = "URDL";

    cout << row(path[0]) + 1 << ' '
         << col(path[0]) + 1 << ' '
         << name[initial_dir] << '\n';

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

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

    cin >> H >> W;
    G.resize(H);

    for (string &s : G)
        cin >> s;

    r0 = H;
    r1 = -1;
    c0 = W;
    c1 = -1;
    N = 0;

    for (int r = 0; r < H; r++) {
        for (int c = 0; c < W; c++) {
            if (G[r][c] == '.') {
                ++N;
                r0 = min(r0, r);
                r1 = max(r1, r);
                c0 = min(c0, c);
                c1 = max(c1, c);
            }
        }
    }

    used.assign(H * W, 0);
    vector<int> answer;

    // 全床マスが 1 行上
    if (r0 == r1) {
        if (N != c1 - c0 + 1) {
            cout << -1 << '\n';
            return 0;
        }

        for (int c = c0; c <= c1; c++)
            answer.push_back(id(r0, c));

        output(answer);
        return 0;
    }

    // 全床マスが 1 列上
    if (c0 == c1) {
        if (N != r1 - r0 + 1) {
            cout << -1 << '\n';
            return 0;
        }

        for (int r = r0; r <= r1; r++)
            answer.push_back(id(r, c0));

        output(answer);
        return 0;
    }

    vector<int> per = perimeter();
    int P = per.size();

    vector<char> on(P);
    int boundary_count = 0;

    for (int i = 0; i < P; i++) {
        on[i] = (G[row(per[i])][col(per[i])] == '.');
        boundary_count += on[i];
    }

    // 外周が全部ではない
    if (boundary_count < P) {
        int start = -1, starts = 0;

        for (int i = 0; i < P; i++) {
            if (on[i] && !on[(i + P - 1) % P]) {
                start = i;
                ++starts;
            }
        }

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

        vector<int> arc;

        for (int i = start; on[i]; i = (i + 1) % P)
            arc.push_back(per[i]);

        if ((int)arc.size() != boundary_count || arc.size() < 2) {
            cout << -1 << '\n';
            return 0;
        }

        if (try_arc(arc, 0, answer) ||
            try_arc(arc, 1, answer)) {
            output(answer);
            return 0;
        }

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

    // 4 方向の連続床マス数
    runlen.assign(H * W, {});

    for (int r = 0; r < H; r++)
        for (int c = 0; c < W; c++)
            if (G[r][c] == '.')
                runlen[id(r, c)][0]
                    = 1 + (r ? runlen[id(r - 1, c)][0] : 0);

    for (int r = 0; r < H; r++)
        for (int c = W - 1; c >= 0; c--)
            if (G[r][c] == '.')
                runlen[id(r, c)][1]
                    = 1 + (c + 1 < W ? runlen[id(r, c + 1)][1] : 0);

    for (int r = H - 1; r >= 0; r--)
        for (int c = 0; c < W; c++)
            if (G[r][c] == '.')
                runlen[id(r, c)][2]
                    = 1 + (r + 1 < H ? runlen[id(r + 1, c)][2] : 0);

    for (int r = 0; r < H; r++)
        for (int c = 0; c < W; c++)
            if (G[r][c] == '.')
                runlen[id(r, c)][3]
                    = 1 + (c ? runlen[id(r, c - 1)][3] : 0);

    if (solve_full(per, answer)) {
        output(answer);
        return 0;
    }

    cout << -1 << '\n';
}