题解 P1444 【[USACO1.3]虫洞wormhole】

「QQ红包」 · 2017-07-07 12:28:31 · 题解

先枚举所有的匹配方式，然后匹配完之后dfs搜找环，具体见代码

/*
ID: ylx14271
PROG: wormhole 
LANG: C++
 */
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct node
{
    int x;int y;
} a[30];
int b[30];
int ans;
bool cmp(node aa,node bb)//排序 
{
    if (aa.y==bb.y) return aa.x<bb.x;
    return aa.y<bb.y;
}
int f(int num,int d,int begin,int p1)//检查，num只是用来标记的 
{ //begin,记录开始位置，用来判断是否回到原点了，
//p1=1：走的方式到达点d 的，p1=0：从某虫洞到达d 的 
    if (num!=1&&d==begin&&p1==1) return 1; // 回到原点了，而且是用走的方式 
    if (p1==0)//从虫洞d出来，就往前走，如果前面有虫洞，就走过去，没有就返回0 
    {
        if (a[d].y==a[d+1].y) return f(num+1,d+1,begin,1);
        else return 0;//没有形成环就返回0 
    }
    if (p1==1) return f(num+1,b[d],begin,0);//走到虫洞口了就跳进去 
}
bool check()
{
    for (int j=1;j<=n;j++)//尝试从每个点出发，看会不会形成环 
        if (f(1,j,j,1)==1) return 1;//有一个会形成环就返回1 
    return 0;
}
void dfs(int x)//配对
{
    if (x==n+1)    {if (check()==1) ans++;return;}//n个点都匹配完了，就检查 
    if (b[x]==0)//如果x没有匹配 
    {
        for (int i=x+1;i<=n;i++)//一个点一个点的匹配 
            if (b[i]==0)
            {
                b[i]=x;b[x]=i;//标记，i匹配x，x匹配i 
                dfs(x+1);//往后搜 
                b[i]=0;b[x]=0;//还原 
            }

    }
    if (b[x]!=0) dfs(x+1);//x匹配过了就继续往后搜 
    return;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);//这里的x是横坐标，y是纵坐标 
    }
    sort(a+1,a+n+1,cmp);//排序按照纵坐标排，纵坐标相同按横坐标 
    dfs(1);//一个点一个点的去匹配 
    printf("%d\n",ans);
    return 0;
}

还是比较简洁的