这个题目我首先考虑的是如何配对的问题。 我的想法是，先给所有点按输入次序编号。然后开一个数组来记录配对问题。利用深搜枚举出所有情况。 之后就是，对每一组配对结果的测试。我的想法就是，粗暴的模拟一下他的行走过程，设定一个阈值。当你经过各个虫洞点的数量已经超过阈值时，就算你卡住了。阈值的设定就是根据感觉来的。。。。
/* ID: 13913351 LANG: C++ TASK:wormhole */ #include<iostream> #include<fstream> #include<cstring> #define cin fin #define cout fout using namespace std; ifstream fin("wormhole.in"); ofstream fout("wormhole.out"); const int N=15; int n; int a[N+1][2]; int pa[N+1];//pa[i] 表示与i与pa[i]是一对 bool flag[N+1]; int sum=0; int route[N*4]; bool tag=false; void search(int cur,int k) { //cout<<pa[cur]; k++; long long int min=9999999999; int next=0; int i; for(i=1;i<=n;i++) { if(i!=pa[cur]&&a[i][1]==a[pa[cur]][1]&&a[i][0]>a[pa[cur]][0]) { if(min>a[i][0]-a[pa[cur]][0]) { min=a[i][0]-a[pa[cur]][0]; next=i; } } } if(next!=0) { k++; if(k>50) { tag=true; return ; } search(next,k); } } bool test() { int i; for(i=1;i<=n;i++) { tag=false; search(i,1); if(tag) return true; } return false; } void dfs(int step) { if(step==n+1) { if(test()) { sum++; // cout<<endl; } return ; } if(flag[step]) { dfs(step+1); return ; } for(int i=1;i<=n;i++) { if(!flag[i]&&i!=step) { pa[step]=i; pa[i]=step; flag[i]=true; flag[step]=true; dfs(step+1); flag[step]=false; flag[i]=false; } } } int main() { cin>>n; int i; for(i=1;i<=n;i++) { cin>>a[i][0]>>a[i][1]; } memset(flag,false,sizeof(flag)); dfs(1); cout<<sum<<endl; }代码写的不怎么规范，我会慢慢成长的。
