记录

代码：

#include <cstdio>
#include <algorithm>
#define rep(i, a, b) for(int i=(a);i<=(b);i++)
#define pre(i, a, b) for(int i=(a);i>=(b);i--)
#define INF 0x7fffffff
#define nINF 0x80000000
#define it(i, a, x) for(int i=(x);i!=x;i=a[i])
using namespace std;

const int N = 6e3 + 10;
int n, m, ans[N];
struct dlx
{
    int n, m, tot, head[N], siz[N];
    int U[N], D[N], L[N], R[N];
    int col[N], row[N];
    void build(int r, int c)
    {
        n = r; m = c;
        rep(i, 0, c)
        {
            L[i] = i - 1; R[i] = i + 1;
            U[i] = D[i] = i;
        }
        L[0] = c; R[c] = 0; tot = c;
    }
    void insert(int r, int c)
    {
        col[++ tot] = c; row[tot] = r; siz[c] ++;
        D[tot] = D[c]; U[D[c]] = tot; U[tot] = c; D[c] = tot;
        if (!head[r]) head[r] = L[tot] = R[tot] = tot;
        else
        {
            R[tot] = R[head[r]]; L[R[head[r]]] = tot;
            L[tot] = head[r]; R[head[r]] = tot;
        }
    }
    void remove(int c)
    {
        L[R[c]] = L[c]; R[L[c]] = R[c];
        it(i, U, c) it(j, L, i) U[D[j]] = U[j], D[U[j]] = D[j], siz[col[j]] --;
    }
    void recover(int c)
    {
        L[R[c]] = R[L[c]] = c;
        it(i, U, c) it(j, L, i) U[D[j]] = D[U[j]] = j, siz[col[j]] ++;
    }
    int dance(int d)
    {
        if (!R[0])
            return d;
        int c = R[0];
        it(i, R, 0) if (siz[i] < siz[c]) c = i;
        remove(c);
        it(i, D, c)
        {
            ans[d] = row[i];
            it(j, L, i) remove(col[j]);
            int t = dance(d + 1);
            if (t) return t;
            it(j, L, i) recover(col[j]);
        }
        recover(c);
        return 0;
    }
} a;
int main()
{
    scanf("%d%d", &n, &m);
    a.build(n, m);
    rep(i, 1, n)
        rep(j, 1, m)
        {
            int x;
            scanf("%d", &x);
            if (x) a.insert(i, j);
        }
    int t = a.dance(1);
    if (t)
        rep(i, 1, t)
            printf("%d ", ans[i]);
    else
        puts("No Solution!");
    return 0;
}