#4273
排列问题
排列问题
题目描述
求数字 0 到 N−1 的一个排列,每个数字恰好出现一次。给定 N×N 的相邻限制表:第 i 行第 j 列为 1,表示数字 j−1 可以紧跟在数字 i−1 后面;为 0 表示不可以。对角线均为 0。
将所有合法排列按字典序从小到大排列,输出第 K 个。所有排列长度相同,即使开头为 0,也保留该数字参与排列。
输入格式
第一行 N 和 K。接下来 N 行,每行 N 个 0 或 1。1 ≤ N ≤ 10,1 ≤ K ≤ 500000,保证至少有 K 个合法排列。
输出格式
按顺序输出所求排列的 N 个数字,用空格分隔。
样例
3 2
0 1 1
1 0 0
0 1 0
1 0 2
样例说明
表格禁止 2 紧跟 1、0 紧跟 2。三个合法排列依次是 0 2 1、1 0 2、2 1 0,所以第 2 个为 1 0 2。