题解：UVA10503 The dominoes solitaire

题目大意

给你

m

个两面都有数字的木块，定义一串合法的木块序列为两个木块间相对的两面的数字相同。如

(1,2),(2,4)(4,4),(4,7)

为合法序列。

(1,2),(1,3),(3,4)

等则为不合法序列。问是否有方案使得从

m

个木块中选出

n

个经过任意的旋转重排后使得有

n+2

个木块的整个序列合法。其中

m\le14

。

思路

暴力搜索需要从头到尾扫一遍，很明显超时了，所以要加上优化。要注意的是两端的骨牌是不可以翻转的，但是中间的那

n

个骨牌可以翻转，首先看有没有找到答案，找到了直接结束程序，然后判断有没有选那么多数量的骨牌，达到一定数量就判断最后一个骨牌能不能和另一端的骨牌链接，否则就继续搜，搜索时判断这个骨牌上的两个数是否相同，相同只需搜一遍即可。

代码实现

CPP

#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;
}

题解：UVA10503 The dominoes solitaire

文章操作

题目大意

思路

代码实现

相关推荐

评论

题解：UVA10503 The dominoes solitaire