题解：UVA10503 The dominoes solitaire

_WHX985_ · 2025-02-11 15:36:30 · 题解

题目大意

给你 m 个两面都有数字的木块，定义一串合法的木块序列为两个木块间相对的两面的数字相同。如 (1,2),(2,4)(4,4),(4,7) 为合法序列。(1,2),(1,3),(3,4) 等则为不合法序列。问是否有方案使得从 m 个木块中选出 n 个经过任意的旋转重排后使得有 n+2 个木块的整个序列合法。其中 m\le14。

思路

暴力搜索需要从头到尾扫一遍，很明显超时了，所以要加上优化。要注意的是两端的骨牌是不可以翻转的，但是中间的那 n 个骨牌可以翻转，首先看有没有找到答案，找到了直接结束程序，然后判断有没有选那么多数量的骨牌，达到一定数量就判断最后一个骨牌能不能和另一端的骨牌链接，否则就继续搜，搜索时判断这个骨牌上的两个数是否相同，相同只需搜一遍即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool as[100005],ans_whike;
struct s__w{
    int number_x;
    int number_y;
}f,smd,a[100005];
void dfs(int number_x1,int ans){
    if(ans_whike){
        return;
    }
    if(ans==n){
        ans_whike=(number_x1==smd.number_x?1:0);
        return;
    }
    for(int i=1;i<=m;i++){
        if(!as[i]){
            if(a[i].number_x==number_x1){
                as[i]=true;
                dfs(a[i].number_y,ans+1);
                as[i]=false;
            }
            if(a[i].number_x!=a[i].number_y){
                if(a[i].number_y==number_x1){
                    as[i]=true;
                    dfs(a[i].number_x,ans+1);
                    as[i]=false;
                }
            }
        }
    }
}
int main(){
    memset(as,0,sizeof(as));
    ans_whike=false;
    while(cin>>n){
        memset(as,0,sizeof(as));
        ans_whike=false;
        if(n<=0){
            return 0;
        }
        cin>>m>>f.number_x>>f.number_y>>smd.number_x>>smd.number_y;
        for(int i=1;i<=m;i++){
            cin>>a[i].number_x>>a[i].number_y;
        }
        dfs(f.number_y,0);
        cout<<(ans_whike?"YES":"NO")<<endl;
    }
    return 0;
}