1067

1067. 精确覆盖问题

题目

给定一个 $N \times M$ 的数字矩阵 $A$，矩阵中的元素 $A_{i,j} \in \lbrace 0,1 \rbrace$。

请问，你能否在矩阵中找到一个行的集合，使得这些行中，每一列都有且仅有一个数字 $1$。

输入格式

第一行包含两个整数 $N$ 和 $M$。

接下来 $N$ 行，每行包含 $M$ 个整数（$0$ 或 $1$），表示完整的数字矩阵。

输出格式

如果能找到满足条件的行的集合，则在一行中依次输出这些行的编号（行编号 $1 \sim N$)。

如果方案不唯一，则以任意顺序输出任意方案即可。

否则，输出 No Solution!。

数据范围

$1 \le N,M \le 500$,

数据保证矩阵中 $1$ 的数量不超过 $5000$。

输入样例1：

3 3
0 1 0
0 0 1
1 0 0

输出样例1：

1 2 3

输入样例2：

4 4
0 0 0 1
1 0 0 0
1 1 0 1
0 1 0 0

输出样例2：

No Solution!

题解