介绍
C#答案(原因:懒,但是完全可以转成C++):bajdcc/learnstl
题目(机翻):
在7乘7格的网格中,你只想在每个广场上放置一个摩天大楼,只有一些线索:
- 摩天大楼的高度在1到7之间
- 一行或一列中的所有摩天大楼楼层数量各不相同
- 你只知道从外面的一行或一列中看到的摩天大楼的数量
- 高层摩天大楼阻挡了后面的下层摩天大楼,导致你看不到后面的大楼了
你能写一个能解决这个难题的程序吗?
举个例子,6x6的:
6x6 摩天大楼 例
(有人说看不懂规则3和4,我就以图来说明一下)
我根据上图制作了一个假城市(bajdcc/UnityTest),如下:
虚拟城市
我们看线索中的左侧(3,4,4):
规则3和4的说明
要求
输入:int[]
输入的数组下标
输出:int[][]
分析
花了两天思考这个系列的问题,最终当然是写出来了(光想没用)。
这个题目感觉跟数独很像,我最先想的思路就是一步步推理,直到解决问题,然而,4x4大小的推理规则在6x6大小的问题中,可能需要补充一些东西或有些东西不实用了,这就麻烦了。
老实说,做数独题的时候,我不怎么用穷举法,我是对当前局面进行推理,利用排除法一步步确定答案,但用代码实现推理就变得困难了,虽然这样做是最优的(因为根据不做多余计算)。
推理不能用,那就老老实实用穷举法吧,虽然穷举法有点low,但只要能过就行。
题目中透露了一些可供优化的信息:各行各列中数是唯一的。这就意味着复杂度从O(n^n)下降到O(n!)。这跟八皇后有点像,但又有所不同,因此我就用回溯法做。
进一步思考
确定用回溯做,也感觉可以借鉴八皇后的思路,还不能马上开工,有几个问题:
- 全排列的生成,这个嘛拿之前的代码粘贴下
- 回溯遍历的顺序,这个顺序大有文章
先解决全排列问题:抄了下https://github.com/bajdcc/jProlog/blob/master/src/com/bajdcc/rt/gen/array/RtNorepArray.java#L43 哈哈。
回溯的顺序应该是怎样呢?自己试喽。
先生成全排列,然后计算从左边向右看到的楼层数(假设为Sky函数,Sky:=int->int),将结果存到字典中。
会发现,当n=7时,sky(7)=1,可能性最低,都算出来后,排序。
sky(7)<sky(6)<sky(5)<sky(1)<sky(4)<sky(3)<sky(2)
展开顺序的话,我肯定先找n=7的情况的,因为这时的不确定性最低(解只有一个),相当于可以确定一个格子的值了。
目前的思路是:找到值=7的数,就直接敲定一排解(1~7);再找值=6的数,这时答案不唯一,回溯;继续找……
这样运行程序的话,肯定是耗时很长的,原因是什么?
再想一想
我们优化程序的目标是回溯时尽可以减少回溯次数,那就必须在决定一个展开顺序:先展开不确定性小的,再展开不确定性较大的。
有一种情况,可以减少不确定性:如果一排格子的两侧都有数字(都不是零),那其实可以将它们放到一起回溯。例: 5 | x x x x x x x | 2,这样可以极大降低可能性。事实证明这样做有一点效果。
思路有了:
- 将规则排好序(数大,对位匹配优先),回溯规则
- 保存现场,查看是否冲突,一是当前的测试值是否与该行/列冲突,二是测试值是否满足各行/列数唯一的原则
- 如果失败,回溯
- 如果成功,level+=1,再测试下一个规则
- 如果level==规则总数,意味着通过了所有规则,此时还不能确定解是否正确
- 规则有覆盖不到的行/列,此时要将值是零的格子进行填空
- 填空的办法是用排除法,然后不断遍历填空,如果最后填空失败,则解不正确,如果填空成功,则解正确
注意点:
- 坐标系问题,方向问题
- 判断条件是否完备
- 尽量用数组做(用list<>竟然比int[]快。。)
- 等等细节问题
代码比较啰嗦,460行,不贴了(别人写得都很短简直了)。