【模板】舞蹈链(DLX)
题目背景
本题是舞蹈链模板——精确覆盖问题
题目描述
给定一个 $N$ 行 $M$ 列的矩阵,矩阵中每个元素要么是 $1$,要么是 $0$。
你需要在矩阵中挑选出若干行,使得对于矩阵的每一列 $j$,在你挑选的这些行中,有且仅有一行的第 $j$ 个元素为 $1$。
输入输出格式
输入格式
第一行两个数 $N,M$。
接下来 $N$ 行,每行 $M$ 个数字 $0$ 或 $1$,表示这个矩阵。
输出格式
一行输出若干个数表示答案,两个数之间用空格隔开,输出任一可行方案均可,顺序随意。
若无解,输出 `No Solution!`。
输入输出样例
输入样例 #1
3 3
0 0 1
1 0 0
0 1 0
输出样例 #1
2 1 3
输入样例 #2
3 3
1 0 1
1 1 0
0 1 1
输出样例 #2
No Solution!
说明
对于 $100\%$ 的数据,$N,M\leq 500$,保证矩阵中 $1$ 的数量不超过 $5000$ 个。