学步园

Farmer John's hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2 <= N <= 12, N even) to materialize on his farm, each located at a distinct point on the 2D map
of his farm (the x,y coordinates are both integers).

According to his calculations, Farmer John knows that his wormholes will form N/2 connected pairs. For example, if wormholes A and B are connected as a pair, then any object entering wormhole A will exit wormhole
B moving in the same direction, and any object entering wormhole B will similarly exit from wormhole A moving in the same direction. This can have rather unpleasant consequences.

For example, suppose there are two paired wormholes A at (1,1) and B at (3,1), and that Bessie the cow starts from position (2,1) moving in the +x direction. Bessie will enter wormhole B [at (3,1)], exit from A
[at (1,1)], then enter B again, and so on, getting trapped in an infinite cycle!

   | . . . .
   | A > B .      Bessie will travel to B then
   + . . . .      A then across to B again

Farmer John knows the exact location of each wormhole on his farm. He knows that Bessie the cow always walks in the +x direction, although he does not remember where Bessie is currently located.

Please help Farmer John count the number of distinct pairings of the wormholes such that Bessie could possibly get trapped in an infinite cycle if she starts from an unlucky position. FJ doesn't know which wormhole
pairs with any other wormhole, so find all the possibilities.

PROGRAM NAME: wormhole

INPUT FORMAT:

SAMPLE INPUT (file wormhole.in):

4
0 0
1 0
1 1
0 1

INPUT DETAILS:

There are 4 wormholes, forming the corners of a square.

OUTPUT FORMAT:

SAMPLE OUTPUT (file wormhole.out):

2

OUTPUT DETAILS:

If we number the wormholes 1..4 as we read them from the input, then if wormhole 1 pairs with wormhole 2 and wormhole 3 pairs with wormhole 4, Bessie can get stuck if she starts anywhere between (0,0) and (1,0)
or between (0,1) and (1,1).

   | . . . .
   4 3 . . .      Bessie will travel to B then
   1-2-.-.-.      A then across to B again

Similarly, with the same starting points, Bessie can get stuck in a cycle if the pairings are 1-3 and 2-4 (if Bessie enters WH#3 and comes out at WH#1, she then walks to WH#2 which transports here to WH#4 which
directs her towards WH#3 again for a cycle).

Only the pairings 1-4 and 2-3 allow Bessie to walk in the +x direction from any point in the 2D plane with no danger of cycling. 

题目大意：

大概就是说，输入N个点的坐标，然后判断这N个点两两能不能构成题目中所谓的虫洞，如果可以的话，这样的组合共有多少种，每次有N/2个虫洞。

解题思路：

这题其实读起来很容易理解，你只要按着题目的意思来理解，不要添加自己的主观色彩，比如说A > B,表示的是A和B构成一个虫洞，这样的话，从A开始走到B，然后又从B回退到了A，那么，我们就可以说A，B是我们所需要的一个组合。那么我们通过定义一些状态来更加清楚的理解题目的意思吧。

比如说c[i]=j，表示的是第i个点最右边的点是j。

b[i] = j,b[j] = i, 表示第i个点和第j个点构成所谓的虫洞，就是一个死循环.

好了，有了这些概念后，就可以开这道题了，我这道题是先枚举出距离第i个点最右边的点j，将这一系列的状态存放在c[MAX,这个数组中，

然后用dfs枚举出任意可以配对的点，也就是可以构成虫洞的组合，然后用check去判断是否能构成死循环，，，在写check的时候，自己没有写出来，

参考了别人的代码...其实，回过头来想想，还是不简单的，比如说，让当前走的点为temp，temp;1->N，temp = c[b[temp]],进行最少N次的迭代，然后如果temp的值不是0，表示该过程并没有离开死循环，如果为0，就表示已经走出了死循环。。。

代码：

 /*
 ID:wikioi_2
 PROG: wormhole
 LANG: C++
 */
# include<cstdio>
# include<iostream>

using namespace std;

int N;
int a[13][2];
int b[13];//find pair b[i]==j，b[j] = i，
int c[13];//c[i]=j,表示i最右边的那个节点是j.

bool check()
{
    for ( int i = 1;i <= N;i++ )
    {
        int temp = i;

        for ( int j = 1;j <= N;j++ )
        {
            temp = c[b[temp]];
        }
        if ( temp!=0 )
            return true;
    }
    return false;

}

int dfs()
{
    int i = 0;
    int sum = 0;
    for ( i = 1;i <= N;i++ )
    {
        if ( b[i] == 0 )
        {
            break;
        }
    }

    if ( i > N )
    {
        if ( check() )
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }

    for ( int j = i+1;j <= N;j++ )
    {
        if ( b[j]==0 )
        {
            b[i] = j;
            b[j] = i;
            sum+=dfs();
            b[i] = 0;
            b[j] = 0;
        }
    }
    return sum;

}


int main(void)
{
    freopen("wormhole.in","r",stdin);
    freopen("wormhole.out","w",stdout);
    cin>>N;

    for ( int i = 1;i <= N;i++ )
    {
        cin>>a[i][0]>>a[i][1];
    }

    for ( int i = 1;i <= N;i++ )
    {
        for ( int j = 1;j <= N;j++ )
        {
            if ( a[j][0] > a[i][0]&&a[j][1]==a[i][1] )
            {
                if ( c[i]==0||a[j][0]-a[i][0]<a[c[i]][0]-a[i][0] )
                {
                    c[i] = j;
                }
            }
        }
    }

    cout<<dfs()<<endl;



    return 0;
}