三角形算法

Question

3

我需要解决这个问题：

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

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

这个数字是三角形的行数。

我必须打印最大的“三角形面积”——由-组成的最大三角形。对于这个问题，答案是9。

三角形也可以倒过来：

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

对于这个问题，输出是4。

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

- MichalH

1

要求关于作业帮助的问题必须包括您已经完成的解决问题的工作摘要，以及您在解决问题时遇到的困难的描述([help], [ask]). - Zabuzard

好的，抱歉，我没有要求作业，所以我不知道这一点。 - MichalH

没关系，如果你能和我们分享一些想法就更好了。但是既然你只是要求提示而不是完整的解决方案，我认为这样也可以。 - Zabuzard

这是来自编程竞赛的问题吗？你能提供一个链接吗？我想在在线评测系统上验证我的答案。 - fjardon

@fjardon 不好意思，这是一个有密码保护的评测机。 - MichalH

3个回答

0

如果效率并不那么重要：有一个循环用于搜索候选项(从左到右遍历每一行)。如果你发现了一个“-”，就中断搜索并尝试计算这个候选项。

因此，首先向右移动，查看它在哪里结束("#")。然后，你就知道三角形的基础(指数)，并直接知道它在下一行必须继续的位置，在检查它之前，重复这个过程，直到完全探索完该候选者。如果行的左指标是li，右指标是ri，则三角形必须在下一行* row +1处继续，指标为li+1和ri-1。

存储其大小，并再次进行搜索部分。一旦搜索访问了所有行，就终止。

你可以通过忽略已发现三角形中的 - 来稍微提高其效率。但前提是它们必须是三角形底部行的一部分。

- Zabuzard

0

我不是算法专家，但由于你只是请求帮助而不是答案，我相信我可以提供一个答案。

你需要找出一种方法来测试一个空间是否在三角形内。一旦你有了这个，我会设计一个蛮力方法（对每个空间运行“三角形测试”）。

然后，当你有了一个蛮力解决方案（这不是最优的方法），尝试使其更有效率。例如，在你有一个可行的解决方案之前，不要担心效率或聪明才智。希望这能帮到你。

- acroynon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fjardon · Accepted Answer

提示

我假设所有的三角形都是这种形式:

--- 
 -

而不是：

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

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

下面的图示是一个由三个2单位三角形组成的3单位三角形，每个2单位三角形又由三个1单位三角形组成。

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

剧透：完整算法如下，不要阅读

（注：该段文字为提示，非翻译内容）

 /!\ spoiler alert /!\

 /!\ spoiler alert /!\

 /!\ spoiler alert /!\

主要算法 首先，可以进行第一次计算以得出所有仅包含一个 - 的单元三角形。维护一个表格，其中 T[x,y] 表示三角形的大小（其边长）。在此步骤中，将每个单元格的初始值设为 1。

然后可以从上到下依次考虑构建更复杂的三角形。

当到达位置 [x,y] 时，应该考虑下顶点为以下位置的三角形：

新三角形的大小为上述三角形的最小大小加 1。之后更新表格中的值 T[x,y]。

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

最后，在您的表格 T 中找到最大的三角形，并计算相应的三角形面积。（公式留给读者作为练习）

复杂度为 O(n²)。