2014
03-09

Guess the Pattern

Given a 01 string, you can group consecutive 1’s into blocks and write down their lengths. This is called the ‘block length sequence (BLS)’ for that string. For example, the BLS for 011100110100011 is 3, 2, 1, 2.

Similarly, given a 01 matrix, you can write down the BLS for each row and each column. Given these BLS’s, your task is to restore the 01 matrix.

Rows are read from left to right, while columns are read from top to bottom. Each test case is guaranteed to be solvable, and you’re free to output any (but only one!) solution you like.

The input contains at most 10 test cases. Each test case begins with two integers n and m (1 <= n, m <= 15), the number of rows and the number of columns. The next n lines contain the BLS’s for each row, from top to bottom, and the next m lines contains the BLS’s for each column, from left to right. Each BLS ends with zero. The input ends with n = m = 0.

The input contains at most 10 test cases. Each test case begins with two integers n and m (1 <= n, m <= 15), the number of rows and the number of columns. The next n lines contain the BLS’s for each row, from top to bottom, and the next m lines contains the BLS’s for each column, from left to right. Each BLS ends with zero. The input ends with n = m = 0.

4 4
2 1 0
3 0
3 0
1 1 0
4 0
3 0
3 0
1 0
0 0

**.*
***.
***.
*.*.

1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。