专栏文章

题解：UVA10503 The dominoes solitaire

ffurina_yyds
UVA10503题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqiyvyw
此快照首次捕获于
2025/12/04 05:34
3 个月前
此快照最后确认于
2025/12/04 05:34
3 个月前
查看原文

题意

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

思路

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

注意

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

代码

CPP
#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 账号，代码仅供参考。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...