题解：UVA10503 The dominoes solitaire

furina_yyds · 2025-01-13 15:16:22 · 题解

题意

给你 m 个木牌，选 n 个木牌，要求两个木牌间的数字要相等，算出能否满足要求。

思路

依照题目暴力枚举即可，但要进行一些优化。先看是否找到答案，找到了就不搜了，不然就继续搜，当搜索到某一种状态时，判断是否合法，合法就继续搜，否则就回溯。

注意

要注意的是两端的骨牌是不可以翻转的。

代码

#include <iostream>
#include <vector>
#define int long long
using namespace std;

const int MAXN = 1.4 * 1e1 + 5;
const int mod = 1e9 + 7;
int n, m, be, en, flag;
vector<pair<int, int>> dominoes;

// 深度优先搜索函数
void dfs(int begin, int cur) {
    if (cur == n) {
        for (const auto& domino : dominoes) {
            if ((domino.first == begin && domino.second == en) || (domino.second == begin && domino.first == en)) {
                flag = 1;
                break;
            }
        }
    } else {
        for (size_t i = 0; i < dominoes.size(); ++i) {
            if (flag) {
                break;
            }
            const auto& domino = dominoes[i];
            if (domino.first == begin) {
                // 标记为已访问
                auto temp = dominoes[i];
                dominoes.erase(dominoes.begin() + i);
                dfs(temp.second, cur + 1);
                // 回溯，将其添加回去
                dominoes.insert(dominoes.begin() + i, temp);
            } else if (domino.second == begin) {
                // 标记为已访问
                auto temp = dominoes[i];
                dominoes.erase(dominoes.begin() + i);
                dfs(temp.first, cur + 1);
                // 回溯，将其添加回去
                dominoes.insert(dominoes.begin() + i, temp);
            }
        }
    }
}

int main() {
    while (true) {
        cin >> n;
        if (n == 0) {
            break;
        }
        cin >> m;
        int X, Y;
        cin >> X >> Y;
        be = Y;
        cin >> X >> Y;
        en = X;
        flag = 0;
        dominoes.clear();
        for (int i = 0; i < m; ++i) {
            int x, y;
            cin >> x >> y;
            dominoes.emplace_back(x, y);
        }
        for (size_t i = 0; i < dominoes.size(); ++i) {
            if (dominoes[i].first == be) {
                auto temp = dominoes[i];
                dominoes.erase(dominoes.begin() + i);
                dfs(temp.second, 2);
                dominoes.insert(dominoes.begin() + i, temp);
            } else if (dominoes[i].second == be) {
                auto temp = dominoes[i];
                dominoes.erase(dominoes.begin() + i);
                dfs(temp.first, 2);
                dominoes.insert(dominoes.begin() + i, temp);
            }
            if (flag) {
                cout << "YES" << endl;
                break;
            }
        }
        if (!flag) {
            cout << "NO" << endl;
        }
    }
    return 0;
}

由于本人未绑定 UVA 账号，代码仅供参考。