USACO Wormholes 【DFS】

묘사

 
농부 존은 주말에 고에너지 물리 실험을 좋아하는 결과가 반대로 N개의 벌레구멍이 농장(2<=N<=12, n은 짝수)에 있고 농장 2차원 지도마다 다른 점이 있다.
그의 계산에 의하면, 존은 그의 벌레구멍이 N/2 연결 배합을 형성할 것이라는 것을 안다.예를 들어 A와 B의 벌레구멍이 한 쌍으로 연결되면 벌레구멍 A에 들어간 모든 대상체는 벌레구멍 B에서 같은 방향으로 나가고, 벌레구멍 B에 들어간 모든 대상은 벌레구멍 A에서 똑같은 방향으로 나간다.이것은 상당히 불쾌한 결과가 발생할 수 있다.
예를 들어 두 쌍의 벌레구멍 A(1, 1)과 B(3, 1)가 있다고 가정하면 베시는 (2, 1)부터 +x 방향(오른쪽)의 위치로 이동한다.베시는 벌레구멍 B(3,1)에 들어가 A에서 나가(1,1) 다시 B에 들어가 무한순환에 갇힌다!

| . . . .

| A > B .       B，A，

+ . . . .       B

농부 존은 그의 농장 안의 모든 벌레 구멍의 정확한 위치를 안다.그는 베시가 항상 +x 방향으로 들어오는 것을 알았다. 비록 그는 베시의 현재 위치를 기억하지 못하지만.농부 존이 다른 벌레 구멍의 배합(상황)을 계산해서 베시가 불행한 위치에서 시작할 수 있도록 도와주세요.

편제

PROGRAM NAME: wormhole
INPUT FORMAT:
(file wormhole.in)
1행: N, 벌레구멍의 수
2부터 N+1줄: 줄마다 두 개의 빈칸으로 구분된 정수를 포함하고 (x, y)를 좌표로 하는 단일한 벌레구멍을 설명한다.각 좌표는 범위 0...1000000000.
OUTPUT FORMAT:
(file wormhole.out)
첫 번째 줄: 베시가 어떤 시작점에서 +x 방향으로 카드가 순환 중인 다른 짝수를 이동하게 한다.

[ 편집자 ]SAMPLE INPUT

4

0 0

1 0

1 1

0 1

[ 편집자 ]SAMPLE OUTPUT

2

[ 편집자 ]HINTS

[편제자] 상세 정보 입력

정사각형 모서리에 벌레 구멍이 네 개 있다.

[편제자] 출력 상세 정보

만약 우리가 벌레 구멍을 1에서 4로 번호를 매칭한 후에 1과 2와 3과 4를 매칭하면, 베시는 (0, 0) 에서 (1, 0) 사이의 임의의 위치에서 시작하거나 (0, 1) 과 (1, 1) 사이에 끼게 될 것이다.

| . . . .

4 3 . . .       B，A，

1-2-.-.-.       B

비슷하게 같은 시작점에서 베시도 1-3과 2-4의 짝을 이루면 순환에 빠진다.
1-4와 2-3의 짝짓기만 있으면 베시가 어떠한 2차원 평면의 점에서 +x 방향으로 순환하지 않게 할 수 있다.
 
할 줄 모르다 = = 공식 코드:

/*

ID: wushuai2

PROG: wormhole

LANG: C++

*/

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <fstream>

#include <cstring>

#include <cmath>

#include <stack>

#include <string>

#include <map>

#include <set>

#include <list>

#include <queue>

#include <vector>

#include <algorithm>

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))

#define MOD 1000000007

#define pi acos(-1.0)



using namespace std;



typedef long long           ll      ;

typedef unsigned long long  ull     ;

typedef unsigned int        uint    ;

typedef unsigned char       uchar   ;



template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}

template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;}



const double eps = 1e-7      ;

const int M = 200000         ;

const ll P = 10000000097ll   ;

const int INF = 0x3f3f3f3f   ;

const int MAX_N = 20         ;



int N, X[MAX_N + 1], Y[MAX_N + 1];

int partner[MAX_N + 1];

int next_on_right[MAX_N + 1];



bool cycle_exists(void){

    for (int start = 1; start <= N; ++start){

        int pos = start;

        for (int count = 0; count < N; ++count){

            pos = next_on_right[partner[pos]];

        }

        if (pos != 0) return true;  // does there exist a cylce starting from start

    }

    return false;

}



int solve(){                        // count all solutions

    int i, ans = 0;

    for (i = 1; i <= N; ++i)

        if (partner[i] == 0) break;  // find first unpaired wormhole

    if (i > N) {                     // everyone paired?

        if (cycle_exists()) return 1;

        else return 0;

    }

    for (int j = i + 1; j <= N; ++j) // try pairing i with all possible other wormholes j

        if (partner[j] == 0){

            partner[i] = j;  // try pairing i & j, let recursion continue to

            partner[j] = i;  // generate the rest of the solution

            ans += solve();

            partner[i] = partner[j] = 0;

        }

    return ans;

}



int main() {

    ofstream fout ("wormhole.out");

    ifstream fin ("wormhole.in");

    int i, j, k, t, m, s, c, w, q;

    memset(next_on_right, 0, sizeof(next_on_right));

    memset(partner, 0, sizeof(partner));

    fin >> N;

    for (i = 1; i <= N; ++i){

        fin >> X[i] >> Y[i];

    }

    for (i = 1; i <= N; ++i){ // set next_on_right[i]...

        for (j = 1; j <= N; ++j){

            if (X[j] > X[i] && Y[i] == Y[j]){ // j right of i...

                if (next_on_right[i] == 0 || X[j] - X[i] < X[next_on_right[i]] - X[i]){ //find next_on_right[i]

                    next_on_right[i] = j;

                }

            }

        }

    }

    fout << solve() << endl;

    //cout << solve() << endl;



    fin.close();

    fout.close();

    return 0;

}