algorithm - 三角形算法

Question

我有这个问题要解决:

输入是一个数字和一个三角形，例如:

5
#-##----#
 -----#-
  ---#-
   -#-
    -

数字是三角形的行数。

而且我必须打印最大的“三角形区域”——由- 组成的最大三角形。对于这个，答案是 9。

三角形也可以倒过来:

4
#-#-#--
 #---#
  ##-
   -

为此，输出为 4。

我需要一些算法方面的帮助。请给我一点帮助，而不是整个算法，因为我想尝试自己解决它，我只需要一个方向。

Answer 1

提示

我假设所有的三角形都是以下形式:

--- 
 - 

而不是像:

 -    or  -    or    -
---       --        --
          -          -

请注意，2 个单位的三角形由三个 1 个单位的三角形组成。一个三元三角形由三个重叠的二元三角形组成，依此类推。

下图是一个 3 单位三角形的例子，它由三个 2 单位三角形组成，它们本身又由三个 1 单位三角形组成

  - -+ -+* +* *            --- +++ ***
     -  +  *      ==>       -   +   *
        o                       o

剧透:完整算法，请勿阅读

 /!\ spoiler alert /!\

 /!\ spoiler alert /!\

 /!\ spoiler alert /!\

主要算法

您可以进行第一次计算以计算所有单位大小的三角形(内部恰好有 1 个 -)。维护一个表，其中 T[x,y] 是三角形的大小(边长)。在此过程中，您将每个带有 - 的单元格初始化为 1。

然后你可以从上到下尝试构建更复杂的三角形。

当在位置 [x,y] 时，你应该考虑三角形的下头位于:

• [x-1,y-1]
• [x ,y-1]
• [x+1,y-1]

新三角形的大小将为 1 加上上述 3 个三角形中任意一个的最小大小。然后更新表 T[x,y]

T[x,y+1] = 1 + min(T[x-1,y], T[x,y], T[x+1,y])

最后，只需在表 T 中找到最大尺寸的三角形并计算相应的三角形面积。 (公式留给读者练习)

复杂度为 O(n²)。