Hướng giải của Sắp xếp quân bài Domino

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Chúng ta mô hình hóa bài toán Domino thành bài toán tìm đường đi/chu trình Euler. Mỗi số từ 1 đến 6 là một đỉnh trên đồ thị vô hướng. Mỗi quân Domino thứ \(i\) là một cạnh vô hướng kết nối hai mặt \(u\) và \(v\). Sau đó ta dùng thuật toán Hierholzer để tìm chu trình/đường đi Euler trên đồ thị vô hướng này, đồng thời lưu trữ chỉ số cạnh và hướng đi qua cạnh.

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int to, id;
    bool reversed;
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<Edge>> adj(7);
    vector<int> deg(7, 0);
    for (int i = 1; i <= n; i++) {
        int u, v;
        if (cin >> u >> v) {
            adj[u].push_back({v, i, false});
            adj[v].push_back({u, i, true});
            deg[u]++; deg[v]++;
        }
    }
    int start = -1;
    int odd_cnt = 0;
    for (int i = 1; i <= 6; i++) {
        if (deg[i] % 2 != 0) {
            odd_cnt++;
            start = i;
        }
    }
    if (odd_cnt != 0 && odd_cnt != 2) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    if (start == -1) {
        for (int i = 1; i <= 6; i++) {
            if (deg[i] > 0) {
                start = i;
                break;
            }
        }
    }
    if (start == -1) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    vector<bool> visited_edge(n + 1, false);
    vector<int> ptr(7, 0);

    vector<pair<int, int>> path;
    stack<int> stk;
    stk.push(start);
    vector<pair<int, int>> stk_edges;

    while (!stk.empty()) {
        int u = stk.top();
        bool found = false;
        while (ptr[u] < (int)adj[u].size()) {
            auto edge = adj[u][ptr[u]++];
            if (!visited_edge[edge.id]) {
                visited_edge[edge.id] = true;
                stk.push(edge.to);
                stk_edges.push_back({edge.id, edge.reversed ? 1 : 0});
                found = true;
                break;
            }
        }
        if (!found) {
            if (!stk_edges.empty()) {
                path.push_back(stk_edges.back());
                stk_edges.pop_back();
            }
            stk.pop();
        }
    }

    if ((int)path.size() != n) {
        cout << "IMPOSSIBLE\n";
    } else {
        reverse(path.begin(), path.end());
        for (int i = 0; i < n; i++) {
            cout << path[i].first << " " << (path[i].second ? "-" : "+") << "\n";
        }
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.