/ Vijos / 题库 /

Cross Logic

Cross Logic

描述

这是一个非常有趣的智力游戏,它规则简单而又变化多端。

游戏在一个m*n的方格里进行。游戏开始时所有的格子都是白色。游戏的目标是通过给出的线索按要求选择一些方格涂黑。这些线索是写在每一行和每一列前面的一些数字,它告诉了你该行或者该列应该出现的几组黑色方格各有多少个。

下面是一个简单的例子。在某一行中,线索给出了“2 1 4”三个数字,那么从这一行的某个位置起将依次出现两个相邻的黑色方格、若干白色方格、一个黑色方格、若干白色方格、四个连续的黑色方格,并且不再有其它的黑色方格。一种可能的情况如下图所示。

214□■■□□□■□■■■■

你需要选择一些方格涂成黑色,使得这些黑色方格满足所有行和所有列的要求。

例如,下图给出了某个谜题的一个可能的解(第二列没有数字表示这一列没有黑色方格)。


\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原创

信息

ID
1247
难度
7
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
296
已通过
48
通过率
16%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Matrix67 NOIP提高组第二次模拟赛