首页 > 代码库 > 【USACO 1.3】Wormholes

【USACO 1.3】Wormholes

 

/*LANG: C++TASK: wormholen个洞,n<=12,如果两洞配对,则它们之间有地下路径(无向)牛在地上只会往+x方向问多少种两两配对的方案,牛从地上某位置出发,会陷入无限循环。SOLVE: 枚举所有配对方案,判断是否会进入无限循环。*/#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define N 15int n,to[N],v[N],ans,vis[N];struct node{	int x,y,id;}a[N];int cmp(node a,node b){	return a.x<b.x;}void dfs(int x){	if(x>n){		for(int i=1;i<=n;i++){//枚举每个洞进去			x=i;			memset(vis,0,sizeof vis);			while(x){//还能走				vis[x]=1;				if(vis[to[v[x]]]){//下一个要进去的洞进去过					ans++;					return;				}				x=to[v[x]];			}		}	}	if(v[x]){		dfs(x+1);		return;	}	for(int i=x+1;i<=n;i++)	if(!v[i]){		v[i]=x;		v[x]=i;		dfs(x+1);		v[i]=v[x]=0;	}}int main(){	freopen("wormhole.in","r",stdin);	freopen("wormhole.out","w",stdout);	scanf("%d",&n);	for(int i=1;i<=n;i++)		scanf("%d%d",&a[i].x,&a[i].y);	sort(a+1,a+1+n,cmp);	for(int i=1;i<=n;i++)	for(int j=i+1;j<=n;j++)		if(a[i].y==a[j].y){			to[i]=j;			break;		}	dfs(1);	printf("%d\n",ans);}

  

【USACO 1.3】Wormholes