java - 动态规划 : Find largest diamond (rhombus)

Question

我有一个用 Java 编写的小程序。我有一个用 0 和 1 填充的二维数组，我必须找到最大的菱形(如旋转 45 度的正方形)及其编号。

例子:

0 1 0 0 0 11 0 1 1 1 01 0 1 1 1 10 1 1 1 1 10 0 1 1 1 11 1 1 1 1 1

结果:

      1        1 1 1    1 1 1 1 1    1 1 1        1    

问题类似于this SO question .

如果您有任何想法，请在此处发布。

Answer 1

评论太长了。如果您无法解决问题，我稍后会发布我的解决方案，但这是我如何完成的(不到 15 行代码):我首先创建了第二个数组(稍微大一点 [n+2][ n+2]) 并且 n/2 次通过了:

0 0 0 0 0 0 0 0 
0 0 1 0 0 0 1 0 
0 1 0 1 1 1 0 0 
0 1 0 1 2 2 1 0 
0 0 1 2 2 2 1 0 
0 0 0 1 2 2 1 0 
0 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 
0 0 1 0 0 0 1 0 
0 1 0 1 1 1 0 0 
0 1 0 1 2 2 1 0 
0 0 1 2 3 2 1 0 
0 0 0 1 2 2 1 0 
0 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0

非零数 x 表示“我是大小为 x 的菱形的中心”(我表示大小与对角线长度的关系 [在您的情况下它们都相等]菱形)。您可以通过检查 {top,right,down,left} 是否都是大小为 k 的菱形的中心来确定是否有大小为 (k+1) 的菱形的中心。

首先创建一个更大的数组的优点是它确实简化了你的逻辑，但我可以通过修改原始数组或使用与输入大小相同的第二个数组来使用更复杂的逻辑来完成它(再一次，简单地在您的输入周围放置一个全零的安全“栅栏”要容易得多)。

如果您不使用栅栏“包围”您的数组，您将有很多额外的 if/else 检查:这很容易出错，导致更大的代码和更难看的代码。