首页 > 代码库 > 【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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。