Dancing LinksX精确覆盖问题模版

 #include <bits/stdc++.h>
#define ed "\n"
#define fi first
#define se second
#define SZ size()
#define ll long long
#define V(a) vector <a>
#define P pair <int,int>
#define PB(a) push_back(a)
#define MK(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define each(a,b) for(auto (a):(b))
#define MSET(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rep2(i,a,b) for(int i=(a);i>=(b);i--)
#define debug(x) cout << "debug:" << x << endl;
#define close ios::sync_with_stdio(false),cin.tie(NULL);
using namespace std;
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b){ return a*b/gcd(a,b); }
ll ksm(ll a,ll b,ll mod){ll ans=1;while(b){if(b&1)ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return (ans)%mod;}
template <typename _tp> inline _tp read(_tp&x){
    char ch=getchar(),sgn=0;x=0;
    while(ch^'-'&&!isdigit(ch))ch=getchar();if(ch=='-')ch=getchar(),sgn=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();if(sgn)x=-x;return x;
}
//head

const int maxn = 1005;
const int maxnode = maxn*maxn;

struct DLX{
    int n,m;//矩阵大小
    //上，下，左，右，列，行
    int U[maxnode],D[maxnode],L[maxnode],R[maxnode],col[maxnode],row[maxnode];
    int Head[maxn];//每一行的头节点
    int ansed,ans[maxn],cnt;//选了几行，记录选择的行，总共多少个节点

    //初始化    
    void init(int n,int m){
        this->n = n; this->m = m;
        //第0行，每一列的头节点
        rep(i,0,m){
            U[i] = i; D[i] = i;
            L[i] = i-1; R[i] = i+1;
            col[i] = i; row[i] = 0;
        }
        L[0] = m; R[m] = 0; cnt = m;
        MSET(Head,-1); MSET(ans,0);
        return ;
    }

    //添加节点
    void push(int x,int y){
        //模拟十字链表
        D[++cnt] = D[y]; U[cnt] = y;
        U[D[y]] = cnt; D[y] = cnt;
        row[cnt] = x; col[cnt] = y;
        if(Head[x] < 0){//该行没有元素，即当前元素是行首元素
            Head[x] = cnt;
            R[cnt] = cnt; L[cnt] = cnt;
        }
        else{
            L[cnt] = Head[x]; R[cnt] = R[Head[x]];
            L[R[Head[x]]] = cnt; R[Head[x]] = cnt;
        }
    }

    //删除当前列为1的那些行
    void del(int y){
        R[L[y]] = R[y]; L[R[y]] = L[y];
        for(int i = D[y];i != y;i = D[i])
            for(int j = R[i];j != i;j = R[j])
                D[U[j]] = D[j], U[D[j]] = U[j];
        return ;
    }

    //回溯，将之前删除的节点连接回来
    void reback(int y){
        for(int i = U[y];i != y;i = U[i])
            for(int j = L[i];j != i;j = L[j])
                D[U[j]] = j, U[D[j]] = j;
        R[L[y]] = y; L[R[y]] = y;
        return ;
    }

    //递归进行跳跃操作
    bool dancing(int dep){
        if(!R[0]){//矩阵空了，结束
            ansed = dep;
            return true;
        }
        int c = R[0];
        del(c);
        for(int i = D[c];i != c;i = D[i]){
            ans[dep] = row[i];
            for(int j = R[i];j != i;j = R[j])
                del(col[j]);
            if(dancing(dep+1)) return true;
            for(int j = L[i];j != i;j = L[j])
                reback(col[j]);
        }
        return false;
    }
}dlx;

int main(){
    int n,m;cin >> n >> m;
    dlx.init(n,m);
    rep(i,1,n) rep(j,1,m){
        int x;cin >> x;
        if(x) dlx.push(i,j);
    }
    if(!dlx.dancing(0)) cout << "NO" << ed;
    else{
        rep(i,0,dlx.ansed-1) cout << dlx.ans[i] << " ";
        cout << ed; 
    }
}