学步园

/* 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4026
 题目来源：上海区域赛Unlock the Cell Phone
报告人：SpringWater
题目类型：状态压缩
题目大意为：在一个存在跨越点和坏死点和正常点的矩阵中，求出遍历所有正常点且仅一次的哈密顿通路的数量总数 思路：这跟哈密顿图的解法差不多，其实就是求哈密顿通路个数吧。DP[i][s], 表示以结点i为最后一个连接点路径状态为s时的图像个数。转移式为DP[i][s] = DP[１][s ^ (1 << i)]　+　DP[2][s ^ (1 << i)] + ...DP[n][s ^ (1 << i)]。最后所有的DP[k][(1 << n + 1) - 1]求和为解。

 解题感悟：此题是一个状态压缩类型的题，这类题型一般属于较难题，因为他不仅设计到图论的知识，还涵盖了数 论和数学建模的理论，以前从没做过类似的题目，所以这题的解题思路基本都是借鉴了别人的解题报告， 本想将他 处理没状态可达的方法优化一下的，即：我不罗列所有中间序号的点，而是从正常点向八个方向扩展， 但是后来发现虽然时间复杂度虽然有改观，但是编程复杂度 就大大加强了，所以 除了判断可达那里我做了 一些空间上的优化以外 其他的都没怎么改动，因为感觉别人的代码确实很精致美妙,！

 通过这初次对状态压缩，感觉它是一个非常实用的思想，并且是很灵活，比起纯的dp要难与理解很多，因为关 键它涉及了很多二进制数论的运用！使得学起来比较吃力，但是我相信通过长时间多的磨练我会把它拿下的！目 前接算是对二维的状态压缩给解决了，接下来就深入到三维的状态压缩，尽管可能会有点难！ */

#include<stdio.h>
#include<string.h>
int G[30],ordinary[17];
int SA[17][17],Hash[30];
__int64dp[17][1<<17];
int n,m,label;
int inputdata()//录入数据
{
    inti,j=n*m;
    for(i=0;i<j;i++)
    {
            scanf("%d",&G[i]);
            if(!G[i])
            {
                Hash[i]=label;     ///用于快速找出当前被接入点的状态位置
                ordinary[label++]=i;///用于后面将两个点中间的所有点罗列出来
            }
        }
        return0;
}
int online(int x1,inty1,int x2,int y2,intmidx,int midy)
{
    return(y1-midy)*(x2-midx)==(y2-midy)*(x1-midx);    //判断三点是否构成一条直线
}
int prepare()
{
    int i,j,k,x1,y1,x2,y2,midx,midy;
    memset(SA,0,sizeof(SA));
    for(i=0;i<label-1;i++)
        for(j=i+1;j<label;j++)
        {
            x1=ordinary[i]%m;
            y1=ordinary[i]/m;
              
            x2=ordinary[j]%m;
            y2=ordinary[j]/m;
  
            for(k=ordinary[i]+1;k<ordinary[j];k++)
            {
                midx=k%m;
                midy=k/m;
                if(G[k]==1||!G[k])
                {
                    if(online(x1,y1,x2,y2,midx,midy))
                    {
                        if(G[k]==1)//被坏死点阻隔
                        {
                            SA[i][j]=SA[j][i]=-1;
                            break;
                        }
                        if((G[k]==0))//将所有的中间正常点记录下来
                        {
                            SA[i][j] |= (1<<Hash[k]);
                            SA[j][i] |= (1<<Hash[k]);
                        }
                    }
                }
            }
        }
        return0;
}
int canreach(int i,int j,ints)//判断i，j点在当前s状态能否可达
{
    if(SA[i][j]==-1)
        return0;
    if(!SA[i][j])
        return1;
    returnSA[i][j]==(SA[i][j]&s);
}
int work()
{
    intsum=1<<label;
    inti,j,k;
    for(i=1;i<sum;i++)
    {
        for(j=0;j<label;j++)
        {
            if(i==1<<j)//当前状态是第一次接入点
            {
                dp[j][i]=1;
                continue;
            }
            else    
                dp[j][i]=0;
            if(i&(1<<j))
            {
                for(k=0;k<label;k++)//罗列出当前点j可能接入的所有入口点k
                {
                    if((k!=j)&&(i&(1<<k))&&canreach(j,k,i))
                        dp[j][i]+=dp[k][i-(1<<j)];
                }
            }
        }
    }
    return0;
}
int main()
{
    intsum,i;
    __int64ans;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        label=0;
        inputdata();
        prepare();
        work();
        ans=0;
        sum=(1<<label)-1;
        for(i=0;i<label;i++)//将所有接入点的最后都接入的状态累加起来
            ans+=dp[i][sum];
        printf("%I64dn",ans);
    }
    return0;
}