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

• 問題: No.3738 Right Hamiltonian
• ユーザー: 👑 kencho
• 提出日時: 2026-08-04 11:32:09
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 10,989 bytes
• コンパイル時間: 3,724 ms
• コンパイル使用メモリ: 356,948 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-19 12:38:20
• 合計ジャッジ時間: 9,886 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

サブタスク	配点	結果
部分点	80 %	AC * 10 TLE * 1 -- * 27
満点	20 %	AC * 10 TLE * 1 -- * 49
合計	4 * 0% = 0 点

ソースコード

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

// 迷路固有の構造は使わず、通る順番を DFS で全探索する。
// 未訪問部分の連結性と次数による一般的な Hamilton 路の枝刈りだけを行う。

int H, W, floor_count;
vector<string> grid_data;
vector<unsigned char> used;
vector<unsigned char> floor_cell;
vector<unsigned char> cell_color;
vector<int> path;
vector<int> floor_cells;
vector<array<int, 4>> next_cell;
vector<int> bfs_queue;
vector<unsigned int> reached;
unsigned int reach_stamp;
int unused_color_count[2];
long long searched_nodes;
long long node_limit;

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

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);
}

bool is_unused_floor(int p) {
    return p >= 0 && floor_cell[p] && !used[p];
}

void visit(int p) {
    used[p] = 1;
    --unused_color_count[cell_color[p]];
}

void unvisit(int p) {
    used[p] = 0;
    ++unused_color_count[cell_color[p]];
}

// 現在地から次に使える辺を allowed_next に入れたとき、残りに
// Hamilton 路が存在するための必要条件を確認する。
bool can_finish(int current, int direction, bool direction_fixed, int visited_count) {
    int remaining = floor_count - visited_count;
    if (remaining == 0) return true;

    // グリッドは二部グラフなので、残りの路でも白黒のマス数は交互になる。
    int current_color = cell_color[current];
    int color_count[2] = {
        unused_color_count[0] + (current_color == 0),
        unused_color_count[1] + (current_color == 1),
    };
    if (remaining % 2 == 1) {
        if (color_count[0] != color_count[1]) return false;
    } else {
        if (color_count[current_color] != color_count[current_color ^ 1] + 1)
            return false;
    }

    array<int, 4> allowed_next{};
    int allowed_count = 0;

    if (direction_fixed) {
        for (int next_direction : {direction, (direction + 1) % 4}) {
            int q = next_cell[current][next_direction];
            if (is_unused_floor(q)) allowed_next[allowed_count++] = q;
        }
    } else {
        for (int next_direction = 0; next_direction < 4; ++next_direction) {
            int q = next_cell[current][next_direction];
            if (is_unused_floor(q)) allowed_next[allowed_count++] = q;
        }
    }

    if (allowed_count == 0) return false;

    // 現在地を離れた後に戻ることはできないため、未訪問部分だけで連結である必要がある。
    if (++reach_stamp == 0) {
        fill(reached.begin(), reached.end(), 0);
        ++reach_stamp;
    }
    int head = 0, tail = 0;
    bfs_queue[tail++] = allowed_next[0];
    reached[allowed_next[0]] = reach_stamp;
    int degree_one = 0;

    while (head < tail) {
        int p = bfs_queue[head++];
        int degree = 0;
        for (int d = 0; d < 4; ++d) {
            int q = next_cell[p][d];
            if (is_unused_floor(q)) {
                ++degree;
                if (reached[q] != reach_stamp) {
                    reached[q] = reach_stamp;
                    bfs_queue[tail++] = q;
                }
            }
        }
        for (int i = 0; i < allowed_count; ++i) {
            if (allowed_next[i] == p) {
                ++degree;
                break;
            }
        }
        if (degree == 0) return false;
        if (degree == 1 && ++degree_one >= 2) return false;
    }

    if (tail != remaining) return false;

    return true;
}

enum class SearchResult {
    found,
    impossible,
    interrupted,
};

SearchResult dfs(int current, int direction, int visited_count) {
    if (visited_count == floor_count) return SearchResult::found;
    if (++searched_nodes > node_limit) return SearchResult::interrupted;
    if (!can_finish(current, direction, true, visited_count))
        return SearchResult::impossible;

    // 同じ方向へ進む部分を 1 区間として扱う。
    // 「何マス直進してから右折するか」を長い方から全探索するので、
    // 1 マスごとの F/R の DFS と探索範囲は同じである。
    vector<int> straight_cells;
    int p = current;
    while (true) {
        int q = next_cell[p][direction];
        if (!is_unused_floor(q)) break;
        straight_cells.push_back(q);
        visit(q);
        path.push_back(q);
        p = q;
    }

    int right_direction = (direction + 1) % 4;
    bool interrupted = false;
    for (int straight_count = straight_cells.size(); straight_count >= 0;
         --straight_count) {
        int endpoint = straight_count == 0
                     ? current
                     : straight_cells[straight_count - 1];
        int count = visited_count + straight_count;

        if (count == floor_count) return SearchResult::found;

        int q = next_cell[endpoint][right_direction];
        if (!interrupted && is_unused_floor(q)) {
            visit(q);
            path.push_back(q);

            SearchResult result = dfs(q, right_direction, count + 1);
            if (result == SearchResult::found) return SearchResult::found;
            if (result == SearchResult::interrupted) interrupted = true;

            path.pop_back();
            unvisit(q);
        }

        if (straight_count > 0) {
            path.pop_back();
            unvisit(straight_cells[straight_count - 1]);
        }
    }

    return interrupted ? SearchResult::interrupted : SearchResult::impossible;
}

SearchResult search_from(int start) {
    visit(start);
    path.clear();
    path.push_back(start);

    if (!can_finish(start, 0, false, 1)) {
        unvisit(start);
        return SearchResult::impossible;
    }

    for (int direction = 0; direction < 4; ++direction) {
        int q = next_cell[start][direction];
        if (!is_unused_floor(q)) continue;

        visit(q);
        path.push_back(q);
        SearchResult result = dfs(q, direction, 2);
        if (result == SearchResult::found) return SearchResult::found;
        path.pop_back();
        unvisit(q);

        if (result == SearchResult::interrupted) {
            unvisit(start);
            return SearchResult::interrupted;
        }
    }

    unvisit(start);
    return SearchResult::impossible;
}

void print_answer() {
    if (floor_count == 1) {
        cout << row_of(path[0]) + 1 << ' ' << col_of(path[0]) + 1 << " U\n";
        cout << "0\n\n";
        return;
    }

    int initial_direction = -1;
    for (int d = 0; d < 4; ++d) {
        if (move_to(path[0], d) == path[1]) initial_direction = d;
    }

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

    for (int i = 1; i < floor_count; ++i) {
        int next_direction = -1;
        for (int d = 0; d < 4; ++d) {
            if (move_to(path[i - 1], d) == path[i]) next_direction = d;
        }
        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;

    floor_count = 0;
    int color_count[2] = {0, 0};
    for (int r = 0; r < H; ++r) {
        for (int c = 0; c < W; ++c) {
            if (grid_data[r][c] == '.') {
                ++floor_count;
                ++color_count[(r + c) & 1];
                floor_cells.push_back(cell_id(r, c));
            }
        }
    }

    if (abs(color_count[0] - color_count[1]) > 1) {
        cout << -1 << '\n';
        return 0;
    }

    used.assign(H * W, 0);
    floor_cell.assign(H * W, 0);
    cell_color.resize(H * W);
    for (int p = 0; p < H * W; ++p) {
        floor_cell[p] = grid_data[row_of(p)][col_of(p)] == '.';
        cell_color[p] = (row_of(p) + col_of(p)) & 1;
    }
    next_cell.resize(H * W);
    for (int p = 0; p < H * W; ++p) {
        for (int d = 0; d < 4; ++d)
            next_cell[p][d] = move_to(p, d);
    }
    bfs_queue.resize(H * W);
    reached.assign(H * W, 0);
    unused_color_count[0] = color_count[0];
    unused_color_count[1] = color_count[1];
    path.reserve(floor_count);

    if (floor_count == 1) {
        path.push_back(floor_cells[0]);
        print_answer();
        return 0;
    }

    // 一般の Hamilton 路でも必要な、入力全体に対する簡単な次数判定。
    int degree_one = 0;
    for (int p : floor_cells) {
        int degree = 0;
        for (int d = 0; d < 4; ++d) {
            int q = next_cell[p][d];
            if (q >= 0 && floor_cell[q]) ++degree;
        }
        if (degree == 0) {
            cout << -1 << '\n';
            return 0;
        }
        if (degree == 1) ++degree_one;
    }
    if (degree_one > 2) {
        cout << -1 << '\n';
        return 0;
    }

    vector<int> starts = floor_cells;
    stable_sort(starts.begin(), starts.end(), [](int a, int b) {
        auto degree = [](int p) {
            int result = 0;
            for (int d = 0; d < 4; ++d) {
                int q = next_cell[p][d];
                if (q >= 0 && floor_cell[q]) ++result;
            }
            return result;
        };
        return degree(a) < degree(b);
    });

    // 1 つの開始マスだけに長時間を使わないよう、探索ノード上限を
    // 段階的に増やす。解なしと証明できた開始マスは次回以降省く。
    vector<unsigned char> exhausted(starts.size(), 0);
    node_limit = 256;

    while (true) {
        bool all_exhausted = true;

        for (int i = 0; i < static_cast<int>(starts.size()); ++i) {
            if (exhausted[i]) continue;

            searched_nodes = 0;
            SearchResult result = search_from(starts[i]);
            if (result == SearchResult::found) {
#ifdef LOCAL
                cerr << "start=" << row_of(starts[i]) + 1 << ','
                     << col_of(starts[i]) + 1
                     << " limit=" << node_limit
                     << " nodes=" << searched_nodes << '\n';
#endif
                print_answer();
                return 0;
            }
            if (result == SearchResult::impossible) {
                exhausted[i] = 1;
            } else {
                all_exhausted = false;
            }
        }

        if (all_exhausted) break;
        if (node_limit <= numeric_limits<long long>::max() / 4)
            node_limit *= 4;
        else
            node_limit = numeric_limits<long long>::max();
    }

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