[搜索]AHOI2009：飛行棋 fly 解題報告

Description

給出圓週上的若干個點，已知點與點之間的弧長，其值均爲正整數，並依圓周順序排列。

請找出這些點中有沒有可以圍成矩形的，並希望在最短時間內找出所有不重複矩形。

Input

第一行爲正整數N，表示點的個數，接下來N行分別爲這N個點所分割的各個圓弧長度

Output

所構成不重複矩形的個數

Sample Input

8 1 2 2 3 1 1 3 3

Sample Output

3

Hint

N<= 20

Source 

HAOI2009-2    2009年安徽NOI省選 第二試 第一題

【分析】 

省選中的水題，直接爆搜即可。

根據平面幾何的知識，構成矩形的充分條件是對邊相等。

由於數據量不大，深度優先搜索、廣度優先搜索均可，連開四層循環暴力枚舉都可以。

【我的代碼】
#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
int N;
int Q[5];
int S[21]={0};
int C[21];
int ans=0;

void init()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>C[i];
        S[i]=S[i-1]+C[i];
    }
}

void dfs(int deep,int num)
{
    if(deep==5)
    {
        if((S[N]-Q[2]-Q[3]-Q[4])==Q[3] && Q[2]==Q[4])
            ans++;
        return;
    }
    for (int i=num+1;i<=N;i++)
    {
        Q[deep]=S[i]-S[num];
        dfs(deep+1,i);
    }
}

int main()
{
    freopen("fly.in","r",stdin);
    freopen("fly.out","w",stdout);
    init();
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}