USACO-wormhole「建议收藏」

参考：大佬 http://www.itdaan.com/blog/2017/12/24/bfe98fc214c07d61e76dbe9743aa3700.html
USACO遇到的第一道磕脑袋题；

/* ID: xiao TASK: wormhole LANG: C++ */

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

ofstream fout("wormhole.out");
ifstream fin("wormhole.in");

int N;
int x_cord[13]={ 
   0};
int y_cord[13]={ 
   0};
int next_cord[13]={ 
   0};
int pair_cord[13]={ 
   0};

bool pd(){ 
   
    for(int i=1; i<=N; i++){ 
   
        int pos = i;
        for(int t=0; t<N; t++)
            pos = next_cord[pair_cord[pos]];
        if(pos!=0)
            return true;
    }
    return false;
}

int dfs(){ 
   
    int ans=0,i;
    for(i=1; i<=N; i++)
        if(pair_cord[i]==0)
            break;
    
    if(i>N){ 
   
        if(pd())
            return 1;
        else 
            return 0;
    }

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

int main(){ 
   
    fin >> N;
    for (int i=1; i<=N; i++)
        fin >> x_cord[i] >> y_cord[i];
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            if (x_cord[j]>x_cord[i]&&y_cord[j]==y_cord[i])
                if(next_cord[i]==0 || x_cord[j] - x_cord[i] < x_cord[next_cord[i]] - x_cord[i])
                    next_cord[i] = j;
    fout << dfs() << endl;    
}

今天的文章USACO-wormhole「建议收藏」分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。