【Codewars】7×7 摩天大楼

v2-b02ba5440139b21ee6a2ceba5158c0ed_1200x500

介绍

链接:7×7 Skyscrapers

C#答案(原因:懒,但是完全可以转成C++):bajdcc/learnstl

题目(机翻):

在7乘7格的网格中,你只想在每个广场上放置一个摩天大楼,只有一些线索:

  • 摩天大楼的高度在1到7之间
  • 一行或一列中的所有摩天大楼楼层数量各不相同
  • 你只知道从外面的一行或一列中看到的摩天大楼的数量
  • 高层摩天大楼阻挡了后面的下层摩天大楼,导致你看不到后面的大楼了

你能写一个能解决这个难题的程序吗?

举个例子,6x6的:

v2-a45496bad9d0aadfb3e2361ac5b8ad49_hd

6x6 摩天大楼 例

(有人说看不懂规则3和4,我就以图来说明一下)

我根据上图制作了一个假城市(bajdcc/UnityTest),如下:

v2-9a35e16413c8e62d9ec55abd6c0a5d3d_r虚拟城市

我们看线索中的左侧(3,4,4):

v2-489542dd990bc52f26c035d8b8b58398_r规则3和4的说明

要求

输入:int[]

v2-587af0b069f7696a90049be18391f65c_hd

输入的数组下标

输出:int[][]

分析

花了两天思考这个系列的问题,最终当然是写出来了(光想没用)。

这个题目感觉跟数独很像,我最先想的思路就是一步步推理,直到解决问题,然而,4x4大小的推理规则在6x6大小的问题中,可能需要补充一些东西或有些东西不实用了,这就麻烦了。

老实说,做数独题的时候,我不怎么用穷举法,我是对当前局面进行推理,利用排除法一步步确定答案,但用代码实现推理就变得困难了,虽然这样做是最优的(因为根据不做多余计算)。
推理不能用,那就老老实实用穷举法吧,虽然穷举法有点low,但只要能过就行。

题目中透露了一些可供优化的信息:各行各列中数是唯一的。这就意味着复杂度从O(n^n)下降到O(n!)。这跟八皇后有点像,但又有所不同,因此我就用回溯法做。

进一步思考

确定用回溯做,也感觉可以借鉴八皇后的思路,还不能马上开工,有几个问题:

  1. 全排列的生成,这个嘛拿之前的代码粘贴下
  2. 回溯遍历的顺序,这个顺序大有文章

先解决全排列问题:抄了下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,这样可以极大降低可能性。事实证明这样做有一点效果。

思路有了:

  1. 将规则排好序(数大,对位匹配优先),回溯规则
  2. 保存现场,查看是否冲突,一是当前的测试值是否与该行/列冲突,二是测试值是否满足各行/列数唯一的原则
  3. 如果失败,回溯
  4. 如果成功,level+=1,再测试下一个规则
  5. 如果level==规则总数,意味着通过了所有规则,此时还不能确定解是否正确
  6. 规则有覆盖不到的行/列,此时要将值是零的格子进行填空
  7. 填空的办法是用排除法,然后不断遍历填空,如果最后填空失败,则解不正确,如果填空成功,则解正确

注意点:

  1. 坐标系问题,方向问题
  2. 判断条件是否完备
  3. 尽量用数组做(用list<>竟然比int[]快。。)
  4. 等等细节问题

代码比较啰嗦,460行,不贴了(别人写得都很短简直了)。

https://zhuanlan.zhihu.com/p/30713476备份。

原文地址:https://www.cnblogs.com/bajdcc/p/8972994.html