PolygonTraversal2

题意 ：

给你一个n个节点的正n边形，然后你有已经走了几步，你要接着走下去，每一步是连接两个节点，你走的每一步都要和之前的走过的线相交，最后一步回到起点。。。问有几种方案。。。

分析 ：

因为n小于13，所以直接状压一下，然后枚举最后一步走到的点，然后枚举一个可以到达的点走下去。如何判断两个点的连线会和之前的线相交呢，我们只要满足这两个点把图形分成的两部分都有走过的点就好啦。。。

代码 ：

int dp[1<<14][15];
vector <int> show[15];
void init(int now, const vector<int> & vec)
{
    for(int i=0;i<=now;i++)
        show[i].clear();
    for(int i=0;i<(1<<now);i++)
        show[__builtin_popcount(i)].push_back(i);
    memset(dp,0,sizeof(dp));
    int start=0;
    for(int i=0;i<vec.size();i++)
        start|=(1<<(vec[i]-1));
    show[vec.size()].clear();
    show[vec.size()].push_back(start);
    dp[start][vec[vec.size()-1]-1]=1;
}
int PolygonTraversal2::count(int N, vector <int> points) 
{
    init(N,points);
    for(int i=points.size();i<=N;i++)
    {       
        int siz=show[i].size();
        for(int j=0;j<siz;j++)
        {
            int now=show[i][j];
            for(int k=0;k<N;k++)
            {
                if(now&(1<<k)==0||!dp[now][k])
                    continue;
                for(int l=0;l<N;l++)
                {
                    if(now&(1<<l))
                        continue;
                    int flag1 = 0, flag2 = 0;
                    int lb = min(k, l) + 1, ub = max(k, l) - 1;
                    for (int ri = 0; ri < N; ri++)
                        if (now >> ri & 1) {
                            if (lb <= ri && ri <= ub) flag1 = 1;
                            else if (ri < lb - 1 || ri > ub + 1) flag2 = 1;
                        }
                    int flag = flag1 & flag2;
                    if(flag==1)
                        dp[now|(1<<l)][l]+=dp[now][k];
                }
            }
        }
    }
    int ans=0,zz=points[0]-1;
    for(int i=0;i<N;i++)
    {
        if(i==(zz+N-1)%N||i==(zz+N+1)%N||i==zz)
            continue;
        ans+=dp[(1<<N)-1][i];
    }
    return ans;
}