#P2790. Consecutive ones

Consecutive ones

描述描述

00000000000000000011

11111111000000000000

00000000000000001111

00000000000011000000

00000000000000111100

00000000000001110000

00111000000000000000

00000000000111000000

00000000111100000000

00000000000000000001

11000000000000000000

00001111111000000000

00000111111111111111

00000000011111100000

00000000001111111110

00000000000000011110

00000001111100000000

00000011111111110000

00011110000000000000

01111111111100000000

00000000000000000111 一个时间表由一个nnmm列的0-1矩阵表示。每行代表一个人,每列代表一个事件。参加某事件的人,其对应行的该列位置为1;未参加的人,该位置为0。事件按顺序连续发生。

问题
编写程序,找出事件的一种巧妙排列方式,使得每个人的所有事件均连续出现。换言之,对矩阵的列进行重排,使每行中的所有1均连续排列。

输入
输入首行包含行数nnn400n \leq 400),第二行包含列数mmm400m \leq 400),接下来nn行为矩阵内容,每行由mm个字符'0'或'1'组成。

输入矩阵满足:仅存在唯一的巧妙排列,且第0列必须保留在0号位置。为简化问题,任意两列的共同1的位置极少。

输出
输出mm个数字,表示列的巧妙排列顺序。第一个数字必须为0(因第0列位置不变),第二个数字为输入矩阵中第二列的索引,依此类推。

输入数据

3
4
0110
0001
1101

输出数据

0
3
1
2

Hint Sample input2

6

5

01010

01000

10101

10100

00011

00101

Sample output2

0

2

4

3

1

Sample input3

21

20

00101000000000000000

10010010010110010100

00101101000000000000

01000000000000001000

00000101100000100000

01000000100000100000

00000010000110000000

01000000000001001000

00000000001001000011

00001000000000000000

10000000000000000100

00010010011000010011

01111101111001111011

01000000000001101011

01100101100001101001

00100101100000000000

00010000001001000011

01010000101001111011

00000010010010010000

00010010011111010111

00101001000000000000

Sample output3

0

17

11

12

6

9

15

3

10

18

19

13

16

1

14

8

5

7

2

4