Skip to content

Latest commit

 

History

History
 
 

1591.Strange-Printer-II

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

1591.Strange-Printer-II

首先,我们解决一个问题:如果矩形里有色彩1,那么我们能知道选种色彩1的色块的形状和位置吗?这个不难做到,我们只要把所有呈现色彩1的格子都找出来,找到能覆盖它的最小的矩形框即可。举个例子:

1 2 1
2 1 3
2 4 4

我们把所有1的格子都找出来,就可以确定这个色块的上边界、下边界、左边界、右边界。由此我们可以发现色彩1的范围应该就是2x3。同理我们可以确定色块2的范围是左边3x2。

这里可能会有一个疑问,为什么色块2的范围不能更大一些?其余部分可不可能被其他色彩覆盖了?诚然确实有这个可能,在超过左边3x2的部分,可能还会有被遮住的2。但是那些“多余的”2对我们来说并没有影响。我们可以认为它存在,也可以认为它不存在。因为它从来没有真正显现过,它的存在与否无从考证。如果它的存在影响了我们其他的结论,那么我们索性就认为它不存在。从后面的分析可知,索性认为它“不存在”会给我们带来更方便的分析。

通过这样的分析,我们可以确定每一个色块的大小和位置。因此也就是说,对于每个格子而言,它被哪些色块覆盖过就都知道了。比如说(0,0)就被1,2填色过;(0,0)就被1,2填色过;(1,2)就被1,3填色过;(2,1)就被1,2,4填色过...

由此,我们还可以有一个重要的发现。(0,0)就被1,2填色过,但最终显示的是颜色1,因此说明色块1应该出现在色块2之后(才能将其覆盖);(1,2)就被1,3填色过,但最终显示的是颜色3,因此说明色块3应该出现在色块2之后(才能将其覆盖);(1,2)就被1,2,4填色过,但最终显示的是颜色4,因此说明色块4应该出现在色块1和色块2之后(才能将其覆盖)...

由此我们可以知道部分的色块填充顺序要求。如果我们能找到一种所有色块的填充顺序,满足这些要求,那就意味着这些格子都能被顺利填色,并且最终显示的的色彩一定就是我们看到的色彩。

这样的色彩填充顺序有很多,我们不一定要真正写出来。我们只要判断是否存在即可。那么如果不存在的原因是什么呢?那就仅有一种:色彩的覆盖顺序出现了循环。比如说对于某个格子,我们发现要求色彩1覆盖色彩2;但是对于另外一个格子,我们发现要求色彩2覆盖色彩1。这样的话,我们是无法确定一种所有色彩的填充顺序的。其他任何情况,我们都可以设计出一种不与要求矛盾的色彩填充顺序。

如果我们能够有这样的色彩填充顺序,那么就一定能实现最终呈现的色彩分布吗?是的,就是这样。我们可以想象堆砌房子,一个个不同颜色的矩形往上堆,从天空俯视到的每个格子的色彩,就是最终覆盖这个格子的色彩。只要堆砌顺序设计出来、并且满足最后堆砌的色彩就是现实的色彩,那么就说明实现了题目的要求。

所以本题就是转化为了:构建一个有向图、判断是否有环。有环的话输出false,无环的话输出true。