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

• 問題: No.3738 Right Hamiltonian
• ユーザー: 👑 kencho
• 提出日時: 2026-08-04 11:19:29
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 10,155 bytes
• コンパイル時間: 2,968 ms
• コンパイル使用メモリ: 366,876 KB
• 実行使用メモリ: 49,740 KB
• 最終ジャッジ日時: 2026-09-19 12:38:19
• 合計ジャッジ時間: 17,748 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

サブタスク	配点	結果
部分点	80 %	AC * 38
満点	20 %	AC * 56 TLE * 1 -- * 3
合計	4 * 80% = 320 点

ソースコード

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

// 部分点 2
// 外周全体が床なら、使わない外周辺を 1 本決めることで内部を 2 長方形に分割できる。
// 各候補について 2 本の渦を 1 マスずつ実際に辿るため、計算量は O(HW(H+W))。

int H, W, floor_count;
int top_row, bottom_row, left_col, right_col;
vector<string> grid_data;
vector<unsigned char> used;

constexpr int DR[4] = {-1, 0, 1, 0};
constexpr int DC[4] = {0, 1, 0, -1};
constexpr char DIR_NAME[5] = "URDL";

struct Rect {
    int top, bottom, left, right;
};

int cell_id(int r, int c) {
    return r * W + c;
}

int row_of(int p) {
    return p / W;
}

int col_of(int p) {
    return p % W;
}

int move_to(int p, int direction) {
    int r = row_of(p) + DR[direction];
    int c = col_of(p) + DC[direction];
    if (r < 0 || r >= H || c < 0 || c >= W) return -1;
    return cell_id(r, c);
}

int direction_of(int from, int to) {
    for (int d = 0; d < 4; ++d) {
        if (move_to(from, d) == to) return d;
    }
    return -1;
}

bool is_floor(int p) {
    return p >= 0 && grid_data[row_of(p)][col_of(p)] == '.';
}

bool inside(const Rect &rect, int p) {
    if (p < 0) return false;
    int r = row_of(p), c = col_of(p);
    return rect.top <= r && r <= rect.bottom &&
           rect.left <= c && c <= rect.right;
}

vector<int> bounding_perimeter() {
    vector<int> result;
    for (int c = left_col; c < right_col; ++c)
        result.push_back(cell_id(top_row, c));
    for (int r = top_row; r < bottom_row; ++r)
        result.push_back(cell_id(r, right_col));
    for (int c = right_col; c > left_col; --c)
        result.push_back(cell_id(bottom_row, c));
    for (int r = bottom_row; r > top_row; --r)
        result.push_back(cell_id(r, left_col));
    return result;
}

vector<int> trace_spiral(int start, int direction, int turn, const Rect *rect) {
    vector<int> result;
    int current = start;

    while (true) {
        int next = move_to(current, direction);
        bool can_go = is_floor(next) && !used[next] &&
                      (rect == nullptr || inside(*rect, next));

        if (!can_go) {
            int next_direction = (direction + turn + 4) % 4;
            next = move_to(current, next_direction);
            can_go = is_floor(next) && !used[next] &&
                     (rect == nullptr || inside(*rect, next));
            if (!can_go) break;
            direction = next_direction;
        }

        used[next] = 1;
        result.push_back(next);
        current = next;
    }

    return result;
}

bool valid_path(const vector<int> &path) {
    if (static_cast<int>(path.size()) != floor_count) return false;

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

    for (int i = 0; i < floor_count; ++i) {
        int p = path[i];
        if (!is_floor(p) || used[p]) return false;
        used[p] = 1;

        if (i > 0) {
            int direction = direction_of(path[i - 1], p);
            if (direction < 0) return false;
            if (previous_direction >= 0 &&
                direction != previous_direction &&
                direction != (previous_direction + 1) % 4) {
                return false;
            }
            previous_direction = direction;
        }
    }

    return true;
}

bool try_boundary_arc(const vector<int> &arc, int order, vector<int> &answer) {
    fill(used.begin(), used.end(), 0);
    for (int p : arc) used[p] = 1;

    int first_direction = direction_of(arc[0], arc[1]);
    int last_direction = direction_of(arc[arc.size() - 2], arc.back());
    vector<int> prefix, suffix;

    if (order == 0) {
        prefix = trace_spiral(arc.front(), (first_direction + 2) % 4, -1, nullptr);
        suffix = trace_spiral(arc.back(), last_direction, +1, nullptr);
    } else {
        suffix = trace_spiral(arc.back(), last_direction, +1, nullptr);
        prefix = trace_spiral(arc.front(), (first_direction + 2) % 4, -1, nullptr);
    }

    if (prefix.size() + arc.size() + suffix.size() !=
        static_cast<size_t>(floor_count)) {
        return false;
    }

    answer.clear();
    for (auto it = prefix.rbegin(); it != prefix.rend(); ++it)
        answer.push_back(*it);
    answer.insert(answer.end(), arc.begin(), arc.end());
    answer.insert(answer.end(), suffix.begin(), suffix.end());
    return valid_path(answer);
}

bool solve_full_perimeter(const vector<int> &perimeter, vector<int> &answer) {
    int perimeter_size = perimeter.size();
    int inner_top = top_row + 1;
    int inner_bottom = bottom_row - 1;
    int inner_left = left_col + 1;
    int inner_right = right_col - 1;

    // perimeter[cut] -> perimeter[cut+1] を使わない外周辺とする。
    for (int cut = 0; cut < perimeter_size; ++cut) {
        int a = perimeter[(cut + 1) % perimeter_size];
        int b = perimeter[cut];
        int ar = row_of(a), ac = col_of(a);
        int br = row_of(b), bc = col_of(b);

        Rect rect_a, rect_b;
        if (ar == br) {
            int split = max(ac, bc);
            Rect left{inner_top, inner_bottom, inner_left, split - 1};
            Rect right{inner_top, inner_bottom, split, inner_right};
            if (ac >= split) {
                rect_a = right;
                rect_b = left;
            } else {
                rect_a = left;
                rect_b = right;
            }
        } else {
            int split = max(ar, br);
            Rect upper{inner_top, split - 1, inner_left, inner_right};
            Rect lower{split, inner_bottom, inner_left, inner_right};
            if (ar >= split) {
                rect_a = lower;
                rect_b = upper;
            } else {
                rect_a = upper;
                rect_b = lower;
            }
        }

        fill(used.begin(), used.end(), 0);
        for (int p : perimeter) used[p] = 1;

        int first_direction = direction_of(a, perimeter[(cut + 2) % perimeter_size]);
        int last_direction = direction_of(
            perimeter[(cut - 1 + perimeter_size) % perimeter_size], b);

        vector<int> prefix = trace_spiral(
            a, (first_direction + 2) % 4, -1, &rect_a);
        vector<int> suffix = trace_spiral(b, last_direction, +1, &rect_b);

        if (prefix.size() + perimeter.size() + suffix.size() !=
            static_cast<size_t>(floor_count)) {
            continue;
        }

        answer.clear();
        for (auto it = prefix.rbegin(); it != prefix.rend(); ++it)
            answer.push_back(*it);
        for (int i = 0; i < perimeter_size; ++i)
            answer.push_back(perimeter[(cut + 1 + i) % perimeter_size]);
        answer.insert(answer.end(), suffix.begin(), suffix.end());

        if (valid_path(answer)) return true;
    }

    return false;
}

void print_answer(const vector<int> &path) {
    int initial_direction = 0;
    if (floor_count >= 2)
        initial_direction = direction_of(path[0], path[1]);

    string commands;
    commands.reserve(max(0, floor_count - 1));
    int direction = initial_direction;

    for (int i = 1; i < floor_count; ++i) {
        int next_direction = direction_of(path[i - 1], path[i]);
        commands.push_back(next_direction == direction ? 'F' : 'R');
        direction = next_direction;
    }

    cout << row_of(path[0]) + 1 << ' ' << col_of(path[0]) + 1 << ' '
         << DIR_NAME[initial_direction] << '\n';
    cout << commands.size() << '\n' << commands << '\n';
}

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

    cin >> H >> W;
    grid_data.resize(H);
    for (string &row : grid_data) cin >> row;

    top_row = H;
    bottom_row = -1;
    left_col = W;
    right_col = -1;
    floor_count = 0;

    for (int r = 0; r < H; ++r) {
        for (int c = 0; c < W; ++c) {
            if (grid_data[r][c] == '.') {
                ++floor_count;
                top_row = min(top_row, r);
                bottom_row = max(bottom_row, r);
                left_col = min(left_col, c);
                right_col = max(right_col, c);
            }
        }
    }

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

    if (top_row == bottom_row) {
        if (floor_count != right_col - left_col + 1) {
            cout << -1 << '\n';
            return 0;
        }
        for (int c = left_col; c <= right_col; ++c)
            answer.push_back(cell_id(top_row, c));
        print_answer(answer);
        return 0;
    }

    if (left_col == right_col) {
        if (floor_count != bottom_row - top_row + 1) {
            cout << -1 << '\n';
            return 0;
        }
        for (int r = top_row; r <= bottom_row; ++r)
            answer.push_back(cell_id(r, left_col));
        print_answer(answer);
        return 0;
    }

    vector<int> perimeter = bounding_perimeter();
    vector<unsigned char> on_perimeter(perimeter.size(), 0);
    int perimeter_floor_count = 0;

    for (int i = 0; i < static_cast<int>(perimeter.size()); ++i) {
        on_perimeter[i] = is_floor(perimeter[i]);
        perimeter_floor_count += on_perimeter[i];
    }

    if (perimeter_floor_count < static_cast<int>(perimeter.size())) {
        int start = -1;
        int intervals = 0;
        for (int i = 0; i < static_cast<int>(perimeter.size()); ++i) {
            int previous = (i - 1 + perimeter.size()) % perimeter.size();
            if (on_perimeter[i] && !on_perimeter[previous]) {
                start = i;
                ++intervals;
            }
        }

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

        vector<int> arc;
        for (int i = start; on_perimeter[i]; i = (i + 1) % perimeter.size())
            arc.push_back(perimeter[i]);

        if (arc.size() < 2 ||
            static_cast<int>(arc.size()) != perimeter_floor_count ||
            (!try_boundary_arc(arc, 0, answer) &&
             !try_boundary_arc(arc, 1, answer))) {
            cout << -1 << '\n';
            return 0;
        }

        print_answer(answer);
        return 0;
    }

    if (solve_full_perimeter(perimeter, answer)) {
        print_answer(answer);
    } else {
        cout << -1 << '\n';
    }
    return 0;
}