USACO Wormholes

开始刷USACO了，开始的题还是比较easy的吧，但是还有不足，主要是旗神说的把代码写简单这方面。其实想想，把暴力题写得优雅也是需要功力的事情，而且也不光是娱乐性质的。代码能力这东西，直接影响速度和准度，兑换到比赛上就是题数和罚时，不可谓不重要。所以多写多学大牛的代码还是很有意义的。
以上废话。

题意：给N个点，两两配对成wormhole，完成blink操作，不改变方向。每头牛都向右走，由于wormholes的存在，可能形成无限循环。问这样配对的方案数，使得存在循环路径。其中N<=12。

做法：暴力枚举所有的配对方案再判是否有循环。

trick点：1.枚举方案用dfs，每次取最小的未使用点和剩余一点。这个做法的好处在于避免重复。因为这就相当于每次的方案排序后的情况，避免了枚举所有情况再除去(n/2)!消序的情况(那个T在7了)
2.建立一个pic[n][2]。pic[i][0]表示从该点出去向右走到的点，即是该点y坐标相同，而正好在i点右边的点（这个只要把点按Y,X排个序就ok了）。pic[i][1]表示从该点左边进去blink到的点，即为该点配
对的点，通过上面的dfs获得。判断是否有环n^2跑一边即可。

多的思考:其实这题和点坐标没啥关系,把图按行分类即可得出一组数（每行的点的个数）{Pi}，直接决定了结果。肯定是有组合数学上的计数方法的，我暂时还没想好，找个时间深入研究下吧。

代码：

/*
ID: jlw44671
PROG: wormhole
LANG: C++
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
struct point{
    int x,y;
}rec[20];
bool cmp(point a,point b)
{
    if(a.y!=b.y)
        return a.y<b.y;
    return a.x<b.x;
}
int pic[20][2];
bool vis[20];
int cnt=0;

void judge()
{
    bool ok=false;
    for(int i=1;i<=n;i++)
    {
        int pos=pic[i][1];
        pos=pic[pos][0];
        while(pos!=i&&pos!=-1)
        {
            pos=pic[pos][1];
            pos=pic[pos][0];
        }
        if(pos==i){ok=true;break;}
    }
    if(ok)cnt++;
    return ;
}

void dfs(int flor)
{
    if(flor==n/2)
    {
        judge();
        //printf("haha\n");
        return ;
    }
    int p=-1,q=-1;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]){p=i;break;}
    }
    if(p==-1)return;
    for(int i=p+1;i<=n;i++)
    {
        if(!vis[i])
        {
            q=i;
            vis[p]=true;
            vis[q]=true;
            pic[p][1]=q;
            pic[q][1]=p;
            dfs(flor+1);
            pic[p][1]=-1;
            pic[q][1]=-1;
            vis[q]=false;
            vis[p]=false;
        }
    }
    return ;
}

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",&rec[i].x,&rec[i].y);
    }
    memset(vis,false,sizeof(vis));
    memset(pic,-1,sizeof(pic));
    sort(rec+1,rec+1+n,cmp);
    for(int i=1;i<n;i++)
    {
        if(rec[i].y==rec[i+1].y){
            pic[i][0]=i+1;
        }
    }
    cnt=0;
    dfs(0);
    printf("%d\n",cnt);
    return 0;
}