求解部分,这个流程图,我至少设计了十几分钟,然后从开始着手写算法到最终debug完成,花了大概有前两部分几倍的时间。
![](http://tiebapic.baidu.com/forum/w%3D580/sign=cd338567802bd40742c7d3f54b889e9c/21018dd3fd1f4134531d1e31321f95cad1c85e72.jpg?tbpicau=2024-09-13-05_bfc9a2e85a47c7c6b3cd37ca1fd4d76d)
要想确定一个区域需要填什么色,首先要做的就是知道它周围的区域填色有哪些。
通过穷举获取区域周围的填色,并进行一定的加工处理即可得到结果。
不过需要特别提出的是,在假定区域1,3都与区域2相邻的前提下,如果我正在对区域2进行填充,那么即使区域3和区域2相邻,也不考虑区域3的填色,而仅考虑区域1的填色。因为在对区域2进行填色时,区域3并没有填色,因此考虑区域3以及编号更大的区域的填色没有意义。(这里需要指出,即便因为某些原因填了区域3的颜色后需要返回来修改区域2的颜色,此时也不考虑区域3的颜色。具体原因后面会讨论。)
我的处理方式是,首先通过函数穷举将该区域的相邻区域复制入Temp,然后使用另一个函数对Temp进行穷举,获取需要的区域的颜色填充并转移至NearbyFill这个nbt中(这个nbt会以Byte List的格式储存附近区域的填色,蓝色为1b,绿色为2b,黄色为3b,红色为4b。一个例子是 NearbyFill:[1b,2b,1b],说明这个区域与两个蓝色填色的区域和一个绿色填色的区域相邻)。
当然,对于第一个区域来说,这个nbt获取不到任何东西,因为没有任何区域的编号比它更小。
通过对NearbyFill的解析处理,即可得到一个区域的(可能)可用填色。
这里我建立了一个PossibleSolutionThis的nbt。这个nbt用于记录当前区域的所有填色的可行性。
首先要对这个nbt进行初始化,设置所有颜色均存在填色可能(四种填色方式均使用1b标记)。
随后调用一个递归函数,检测NearbyFill中的nbt,判断哪种颜色已经被使用,并将对应的颜色设置为0b。这样递归后,PossibleSolutionThis中就会有一部分颜色可用(标记为1b),而另一部分颜色不可用(标记为0b)的结果出现了(对区域1来说,所有四种颜色都会是1b。而后续的填色过程中,可能会出现所有颜色都不可用的现象,此时认定结果“出错”,需要通过改变之前区域的填充来解决,会在后面详细说明)。
现在我们获得了一个区域的可能填充,那么得到答案的最简单的方法就是一个个试。我的策略是先从1(蓝色)开始,1不行就用2(绿色),再不行就3(黄色)或4(红色)。
通过函数穷举判断PossibleSolutionThis的第一个可用颜色,并保存到FinalSolutionThis这个nbt中。这个nbt即表示当前这个区域正在使用的填色。同时,使用穷举函数将PossibleSolutionThis和FinalSolutionThis保存到PossibleSolution和FinalSolution下对应编号的nbt内。这样FinalSolution里就保存了所有区域正在使用的填色,而PossibleSolution里保存了所有区域的可用填色。结果如下图所示:
![](http://tiebapic.baidu.com/forum/w%3D580/sign=6e0fb954c30735fa91f04eb1ae500f9f/2fccd81f4134970af5590b6082cad1c8a7865d72.jpg?tbpicau=2024-09-13-05_76a55fa647f01cdae02aa56728b60873)
这里的各个NBT的作用:
PossibleSolution 用于保存所有区域的填色可能
PossibleSolutionThis 用于保存当前正在分析的区域的填色可能
FinalSolution 用于保存所有区域的正在使用的填色
FinalSolutionThis 用于保存当前正在分析的区域正在使用的填色
除此之外,PossibleSolution也用于出错时能够方便地进行修正,而FinalSolution则用于生成最终解
回到刚刚抛出的一个问题。如果在分析可用填色时发现无可用填色,说明附近的一个已有填色的区域的填色出错了。由于不知道具体是哪个区域出错,还是只能一个个试。我的选择是为附近的编号比当前编号小的编号最大的区域重新填色。
首先通过穷举函数获取附近的编号最大但又比当前区域编号小的区域,保存至NearestId中,并转移至记分板。通过穷举函数获取该编号的区域记录下的PossibleSolution和FinalSolution,分别保存至PossibleSolutionThis和FinalSolutionThis中。再通过穷举在PossibleSolutionThis中将FinalSolutionThis的解标记为不可用(0b)。随后复制好其他信息,重新分析PossibleSolutionThis中是否有可用解。
重新分析的过程中,PossibleSolutionThis是直接从之前的记录中获取的,因此不再需要初始化(甚至因为做过标记,而不能进行初始化)。
这里讨论一下之前留下的一个问题。如果区域x填充后,区域y被认定无解,而区域x又恰好是编号比y小的区域中编号最大的一个,那么重新填充的x是否要依据其他有填充而编号又比x大的区域进行填充?(比如,区域4和区域5,6相邻,区域5,6互相不相邻,而区域6被认定无解,此时区域4的填充是否需要考虑区域5的填充)
我的观点是,此处区域4的填充不应参考区域5的填充。因为首先区域5的填充是参考了区域4的,如果区域4有变,那么区域5的填充也会有变化。那么,在之前情形下得到的结论在这种情形下不再适用,所以不应直接使用。因此,区域4的可用填充可以直接从记录中获取,而区域5的填充则需要重新初始化,并重新讨论分析。