跳至正文
题库4273
#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。

来源

蓝桥杯 算法训练