Dancing Links学习：http://www.cnblogs.com/steady/archive/2011/03/15/1984791.html

以及图文学习：http://www.cnblogs.com/grenet/p/3145800.html

思路：这题是Dancing Links即DLX的最简单题目了吧，看懂了这个知识点之后。也不想自己敲了。然后搜索了好多个代码模板。认为这个我比較好理解也比較好掌握。然后就用这个模板了。

#include<iostream>

#include<cstring>

#include<string>

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

#define MAXN  350*30+30

#define INF 0xFFFFFF

int head,sz;

int U[MAXN],D[MAXN],L[MAXN],R[MAXN];//上下左右链表指针

int H[MAXN],ROW[MAXN],C[MAXN],S[MAXN],O[MAXN];

void remove(int c)

{

    L[R[c]]=L[c];

    R[L[c]]=R[c];

    for(int i=D[c]; i!=c; i=D[i])

    {

        for(int j=R[i]; j!=i; j=R[j])

        {

            U[D[j]]=U[j];

            D[U[j]]=D[j];

            --S[C[j]];

        }

    }

}

void resume(int c)

{

    for(int i=U[c]; i!=c; i=U[i])

    {

        for(int j=L[i]; j!=i; j=L[j])

        {

            ++S[C[j]];

            U[D[j]]=j;

            D[U[j]]=j;

        }

    }

    L[R[c]]=c;

    R[L[c]]=c;

}

bool dfs(int k)

{

    if(R[head]==head)

        return  true;

    int s=INF,c;

    for (int t=R[head]; t!=head; t=R[t])

        if (S[t]<s) s=S[t],c=t;

    remove(c);

    for(int i=D[c]; i!=c; i=D[i])

    {

        O[k]=ROW[i];

        for(int j=R[i]; j!=i; j=R[j])

            remove(C[j]);

        if(dfs(k+1)) return  true;

        for(int j=L[i]; j!=i; j=L[j])

            resume(C[j]);

    }

    resume(c);

    return  false;

}

void init(int m)//m是列

{

    head=0;//头指针为0

    for(int i=0; i<=m; i++)

    {

        U[i]=i;

        D[i]=i;//建立双向十字链表

        L[i]=i-1;

        R[i]=i+1;

        S[i]=0;

    }

    R[m]=0;

    L[0]=m;

    S[0]=INF+1;

    sz=m+1;

    memset(H,0,sizeof(H));

}

void insert(int i, int j)

{

    if(H[i])

    {

        L[sz] = L[H[i]];

        R[sz] = H[i];

        L[R[sz]] = sz;

        R[L[sz]] = sz;

    }

    else

    {

        L[sz] = sz;

        R[sz] = sz;

        H[i] = sz;

    }

    U[sz] = U[j];

    D[sz] = j;

    U[D[sz]] = sz;

    D[U[sz]] = sz;

    C[sz] = j;

    ROW[sz] = i;

    ++S[j];

    ++sz;

}

int main()

{

    //freopen("1.txt","r",stdin);

    int n,m,x;

    while(~scanf("%d%d",&n,&m))

    {

        init(m);

        for(int i=1;i<=n;i++)

            for(int j=1;j<=m;j++)

            {

                scanf("%d",&x);

                if(x) insert(i,j);

            }

        if(dfs(0)) //从头指针0開始遍历

            puts("Yes, I found it");

        else puts("It is impossible");

    }

    return 0;

}