题解：UVA10503 The dominoes solitaire

zhangmuning1016 · 2025-01-22 10:07:03 · 题解

题目大意

思路

• 搜索的时间复杂度是 14 的阶乘，肯定超时，所以需要剪枝。
• 题目中注意两端的骨牌不可以翻转，可是中间的 n 个骨牌可以翻转。
• 首先看有没有找到答案，如果找到就直接返回。
• 如果没找到就要判断有没有达到数量，达到了就判断最后的骨牌能不能和另一端的骨牌链接，没达到数量就继续搜。
• 搜索时记得判断这个骨牌上的两个数是否相同。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
};
node f,e,a[15]; 
bool vl[15],f2;
int n,m;
void dfs(int x1,int sum) {
    if(f2){//找到了答案，返回 
        return;
    }
    if(sum==n) {//有没有达到数量 
        if(x1==e.x){//能不能和另一端的骨牌链接 
            f2=1;//搜到答案了
        } 
        return;
    }
    for(int i=0; i<m; i++) {
        if(vl[i]){//这个骨牌是否被用过
            continue;
        } 
        if(a[i].x==x1) {
            vl[i]=1;
            dfs(a[i].y,sum+1);
            vl[i]=0;
        }
        if(a[i].x==a[i].y){
            continue;//两个数相同搜一遍就行
        } 
        if(a[i].y==x1) {
            vl[i]=1;
            dfs(a[i].x,sum+1);
            vl[i]=0;
        }
    }
}
signed main() {
    while(cin>>n&&n) {//更方便的输入判断 
        cin>>m>>f.x>>f.y>>e.x>>e.y;
        memset(vl,0,sizeof vl);//记得初始化
        f2=0;
        for(int i=0; i<m; i++) {//输入 
            cin>>a[i].x>>a[i].y;
        }
        dfs(f.y,0);//调用 
        if(f2){
            cout<<"Yes"<<endl;//找到了答案 
        } 
        else{
            cout<<"No"<<endl;
        } 
    }
    return 0;
}