You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

分书问题是指：已知 $n$ 个人对 $m$ 本书的喜好（$n \le m$），现要将 $m$ 本书分给 $n$ 个人，每个人只能分到 $1$ 本书，每本书也最多只能分给 $1$ 个人，并且还要求每个人都能分到自己喜欢的书。列出所有满足要求的方案。

本题请你对任意 $n$ 和 $m$ 尝试列出全部的解。

输入格式： 输入第一行给出两个正整数 $n$ 和 $m$ $(n \le m \le 8)$，即分书问题中的人数和书的数量。 随后 $n$ 行，每行给出 $m$ 个关系矩阵元素。其中第 $i$ 行第 $j$ 个元素为 $1$ 表示第 $i$ 个人喜欢第 $j$ 本书，为 $0$ 则表示不喜欢。

输出格式：

按升序列出所有满足要求的方案 每行输出 $n$ 个数 $s_1,s_2 \ldots s_n$ 其中 $s_i$ 表示第 $i$ 个人分到了第 $s_i$ 本书。

注：方案 $(a_1 , \ldots ,a_n​ )$ < $(b_1​,⋯,b_n)$是指存在 $1 \le k \le n$ ，使得 $a_i = b_i$ 对所有 $1 \le i \le k$ 成立，并且有 $a_k \lt b_k$。

输入样例：

4 5
0 1 0 0 1
1 1 0 1 0
1 0 1 1 0
0 0 0 1 1

输出样例：

2 1 3 4
2 1 3 5
2 1 4 5
2 4 1 5
2 4 3 5
5 1 3 4
5 2 1 4
5 2 3 4

限制与约定

对于 $50\%$ 的数据，$2 \le n \le m \le 5$

对于 $100\%$ 的数据，$2 \le n \le m \le 8$, 保证每一行至少存在一个 $1$

• 时间限制: $1 s$
• 空间限制: $256 MB$