Cross Logic
测试数据来自 system/1247
描述
这是一个非常有趣的智力游戏,它规则简单而又变化多端。
游戏在一个m*n的方格里进行。游戏开始时所有的格子都是白色。游戏的目标是通过给出的线索按要求选择一些方格涂黑。这些线索是写在每一行和每一列前面的一些数字,它告诉了你该行或者该列应该出现的几组黑色方格各有多少个。
下面是一个简单的例子。在某一行中,线索给出了“2 1 4”三个数字,那么从这一行的某个位置起将依次出现两个相邻的黑色方格、若干白色方格、一个黑色方格、若干白色方格、四个连续的黑色方格,并且不再有其它的黑色方格。一种可能的情况如下图所示。
214□■■□□□■□■■■■
你需要选择一些方格涂成黑色,使得这些黑色方格满足所有行和所有列的要求。
例如,下图给出了某个谜题的一个可能的解(第二列没有数字表示这一列没有黑色方格)。
1
\2 12
1□□■□
11■□□■
12■□■■
给出这样一个谜题,请打印出该问题的解。
格式
输入格式
第一行有两个用空格隔开的正整数m,n,他们分别表示该谜题的方格列数和行数。
接下来m行从左至右描述了谜题的纵向信息。每一行有若干个数字,这些数字表示该列从上至下将会出现的连续黑色方格数。每一行用一个数字0作为结束。
接下来n行从上至下描述了谜题的横向信息。每一行有若干个数字,这些数字表示该行从左至右将会出现的连续黑色方格数。每一行用一个数字0作为结束。
对于30%的数据,m,n<=3;
对于50%的数据,m,n<=10;
对于100%的数据,m,n<=20。
输出格式
将谜题的解打印出来。
每一个方格用两个字符表示。其中,一个白色方格用“ ”(两个空格)表示,一个黑色方格用“##”表示。因此,输出数据一共有n行,每行2m个字符。
我们保证输入数据有唯一解。
样例1
样例输入1
4 3
2 0
0
1 1 0
2 0
1 0
1 1 0
1 2 0
样例输出1
##
## ##
## ####
限制
各个测试点5s
来源
Matrix67原创