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

• 問題: No.3738 Right Hamiltonian
• ユーザー: 👑 kencho
• 提出日時: 2026-07-24 11:01:09
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 5,820 bytes
• コンパイル時間: 3,045 ms
• コンパイル使用メモリ: 365,776 KB
• 実行使用メモリ: 13,980 KB
• 最終ジャッジ日時: 2026-09-19 12:37:04
• 合計ジャッジ時間: 20,379 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_0

サブタスク	配点	結果
部分点	80 %	AC * 33 WA * 3 TLE * 2
満点	20 %	AC * 33 WA * 3 TLE * 3 -- * 21
合計	4 * 0% = 0 点

ソースコード

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

struct Solver {
    int h, w, cells, floors;
    vector<string> grid;
    vector<int> seen;
    int stamp = 0;
    const int dr[4] = {-1, 0, 1, 0};
    const int dc[4] = {0, 1, 0, -1};
    const string dir_char = "URDL";

    bool is_floor(int r, int c) const {
        return 0 <= r && r < h && 0 <= c && c < w && grid[r][c] == '.';
    }

    bool try_start(int start, int initial_direction, bool print_answer) {
        ++stamp;
        int position = start;
        int direction = initial_direction;
        int visited = 1;
        seen[position] = stamp;
        string commands;
        if (print_answer) commands.reserve(floors - 1);

        while (visited < floors) {
            int r = position / w, c = position % w;
            bool moved = false;
            for (int turn = 0; turn <= 1; ++turn) {
                int next_direction = (direction + turn) & 3;
                int nr = r + dr[next_direction], nc = c + dc[next_direction];
                if (!is_floor(nr, nc)) continue;
                int next = nr * w + nc;
                if (seen[next] == stamp) continue;
                position = next;
                direction = next_direction;
                seen[position] = stamp;
                ++visited;
                if (print_answer) commands.push_back(turn == 0 ? 'F' : 'R');
                moved = true;
                break;
            }
            if (!moved) break;
        }
        if (visited != floors) return false;
        if (print_answer) {
            cout << start / w + 1 << ' ' << start % w + 1 << ' '
                 << dir_char[initial_direction] << '\n';
            cout << commands.size() << '\n';
            cout << commands << '\n';
        }
        return true;
    }

    bool basic_impossibility() const {
        int first = -1;
        int leaves = 0;
        for (int r = 0; r < h; ++r) {
            for (int c = 0; c < w; ++c) {
                if (grid[r][c] == '#') continue;
                if (first == -1) first = r * w + c;
                int degree = 0;
                for (int d = 0; d < 4; ++d) degree += is_floor(r + dr[d], c + dc[d]);
                leaves += degree == 1;
            }
        }
        if (leaves >= 3) return true;

        vector<unsigned char> reached(cells, 0);
        queue<int> que;
        que.push(first);
        reached[first] = 1;
        int count = 0;
        while (!que.empty()) {
            int id = que.front();
            que.pop();
            ++count;
            int r = id / w, c = id % w;
            for (int d = 0; d < 4; ++d) {
                int nr = r + dr[d], nc = c + dc[d];
                if (!is_floor(nr, nc)) continue;
                int next = nr * w + nc;
                if (!reached[next]) {
                    reached[next] = 1;
                    que.push(next);
                }
            }
        }
        return count != floors;
    }

    vector<int> make_candidates(int walls) const {
        vector<unsigned char> added(cells, 0);
        vector<int> result;
        auto add = [&](int r, int c) {
            if (!is_floor(r, c)) return;
            int id = r * w + c;
            if (!added[id]) {
                added[id] = 1;
                result.push_back(id);
            }
        };

        if ((cells <= 50000 && walls > 2) || min(h, w) <= 5) {
            for (int id = 0; id < cells; ++id) {
                if (grid[id / w][id % w] == '.') add(id / w, id % w);
            }
            return result;
        }

        for (int r = 0; r < h; ++r) {
            for (int c = 0; c < w; ++c) {
                if (r <= 1 || r >= h - 2 || c <= 1 || c >= w - 2) add(r, c);
            }
        }
        for (int r = 0; r < h; ++r) {
            for (int c = 0; c < w; ++c) {
                if (grid[r][c] != '#') continue;
                for (int nr = max(0, r - 2); nr <= min(h - 1, r + 2); ++nr) {
                    for (int nc = max(0, c - 2); nc <= min(w - 1, c + 2); ++nc) {
                        add(nr, nc);
                    }
                }
            }
        }

        if (walls > 2) {
            for (int r = 0; r < h; ++r) {
                for (int c = 0; c < w; ++c) {
                    if (grid[r][c] != '.') continue;
                    int degree = 0;
                    for (int d = 0; d < 4; ++d) degree += is_floor(r + dr[d], c + dc[d]);
                    if (degree <= 2) add(r, c);
                }
            }
        }
        return result;
    }

    void run() {
        cells = h * w;
        floors = 0;
        int walls = 0;
        for (const string& row : grid) {
            floors += count(row.begin(), row.end(), '.');
            walls += count(row.begin(), row.end(), '#');
        }
        if (floors == 1) {
            for (int r = 0; r < h; ++r) for (int c = 0; c < w; ++c) {
                if (grid[r][c] == '.') {
                    cout << r + 1 << ' ' << c + 1 << " U\n0\n\n";
                    return;
                }
            }
        }
        if (basic_impossibility()) {
            cout << -1 << '\n';
            return;
        }

        seen.assign(cells, 0);
        vector<int> candidates = make_candidates(walls);
        for (int start : candidates) {
            for (int direction = 0; direction < 4; ++direction) {
                if (try_start(start, direction, false)) {
                    try_start(start, direction, true);
                    return;
                }
            }
        }
        cout << -1 << '\n';
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solver solver;
    if (!(cin >> solver.h >> solver.w)) return 0;
    solver.grid.resize(solver.h);
    for (string& row : solver.grid) cin >> row;
    solver.run();
    return 0;
}