algorithm - 在二维阵列中找到菱形的最快方法是什么？

Question

以下是我的问题的可视化：
我需要找到最有价值的菱形存储在一个广场。
我想了好几天，但直到现在，我还没有找到其他东西，除了使用“for loop”和检查每一个可能的菱形。你们觉得怎么样？这是我唯一的办法吗：p谢谢：）

Answer 1

我的想法是：
第一次迭代，你遍历矩阵，但是是对角的。你从最左上角开始，在那里你可以适合你的菱形（或菱形的一侧），你看菱形的大小所覆盖的元素。
首先检查elems（0,1）和（1,0）（a）
接下来检查（0,2）和（1,1）（b）
（1,1），（2,0）（b）
（0,3），（1,2）（c）
（1,2），（2,1）（c）
…
我希望你拿到考试命令。对这些元素做的就是求和：e（0,1）+e（1,0）=11，e（0,2）+e（1,1）=3等等。您必须注意，当您使用同一行上的元素（上面用相同字母标记的元素）时，您不必重新计算总和：有一个元素输出，一个元素输入，因此您只访问两个元素来获得新的总和。
第二次迭代，你对角遍历矩阵，但从另一个侧面。从右上角开始计算之前计算的和所以，你要检查的第一对是（0,3），（1,4）。你做的和你以前做的完全一样：你重新计算总和。
现在，在第二次迭代结束时，每个处理过的字段实际上包含稀疏菱形的和，该菱形在该字段中有一个上角。3x3菱形的示例如下图所示：
第三步，可以看到一个大小为n的稀疏菱形“丢失”了另一个稀疏菱形——大小为n-1的菱形。迭代1和迭代2正是为图像中所有大小为n的稀疏菱形求和的过程因此，作为第三步，我们再次运行第一次和第二次迭代，但不是使用我们要搜索的大小（n），而是使用大小（n-1）。注意，对大小1的“搜索”等于输入矩阵（例如，如果n=2，对于第三步，您不必计算任何东西）。
最后，对于顶部位置（0,2）的3x3菱形，您感兴趣的和是前两次迭代的（0,2）和，以及第三步的（1,2）和。可以将这两个元素相加：对于前两个过程的结果矩阵中位于位置（x，y）的每个元素，可以将第三步结果矩阵中位于位置（x，y+1）的元素相加。
现在你只需要找到最大值，你就可以得到菱形的最大值和位置的答案。
你在4遍中完成这一切（当你计算第二遍时，你可以跟踪最大值）——所以这将给出O(4*n^2) = O(n^2)的复杂性，其中n是正方形大小的大小。
希望很清楚，如果我的回答有问题，请澄清。
2x2菱形示例
第1遍

 -1 11  3  7  5     * / * * * 
 -1  9 14 12  3     / * * * *
 -1 12 18  4  6     * * * * * 
 -1 11  3  6  2    * * * * * 
 -1 -1 -1 -1 -1     * * * * *

第二遍

 -1 25 15 10 -1    * * * \ *
 -1 27 18 18 -1    * * * * \
 -1 15 24  6 -1    * * * * *
 -1 -1 -1 -1 -1    * * * * *
 -1 -1 -1 -1 -1    * * * * *

第三步
因为n=1，所以第三遍不需要计算任何东西，第三遍的输出是输入矩阵

 1  2  2  2  2
 9  1  5  3  1
 8  9  9  2  3
 3  9  2  3  1
 2  1  3  1  1

现在，我们只需要将第二次迭代的输出和第三步的输出（向上移动一个位置）相加。我们得到：

 -1 26 20 13 -1    
 -1 36 27 20 -1    
 -1 24 26  9 -1    
 -1 -1 -1 -1 -1    
 -1 -1 -1 -1 -1    

回答
上角在（1，1）处的菱形是最有价值的，其和为31。
注： -1是菱形边不适合的地方——未定义和。你可以在你的程序中以任何你想要的方式标记它（特别是如果你的矩阵中有负数的话）。在第二个过程中，可以将任何具有未定义元素的总和设置为未定义。
注2：无论菱形大小如何，当你在矩阵中滑动菱形边时，一个数字总是进来，而另一个从和中出来（除非你输入了一个新行）。
注3：菱形在第2次扫描和第2次扫描中的第一个位置在数组中用 /或 \标记
示例3x3菱形
让我在同一个矩阵上做一个3x3菱形，以表明在一般情况下，复杂度是 O(n^2)（其中 n是正方形大小的大小），而不仅仅是2x2菱形。
让我们调用输入矩阵，第一次传递后的矩阵，第二次传递后的矩阵。
第1遍
z[][]（甲）
f[][]（b）
s[][]（b）
f[0][2] = z[0][2] + z[1][1] + z[2][0] == 11（丙）
f[0][3] = z[0][3] + z[1][2] + z[2][1] == 16（丙）
f[1][2] = f[0][3] - z[0][3] + z[3][0] == 17（丙）
f[0][4] = z[0][4] + z[1][3] + z[2][2] == 14（四）
f[1][3] = f[0][4] - z[0][4] + z[3][1] == 21（四）
f[2][2] = f[1][3] - z[1][3] + z[4][0] == 20（英）
你最多一次访问每个元素。用不同字母标记的是同一行上的和。在这一行的第一个和中，你必须和菱形的边上有多少元素求和，我们称之为菱形。在该行的每一个和中，您始终必须访问3个元素：前一个和、要出去的元素（带有 f[1][4] = z[1][4] + z[2][3] + z[3][2] == 5符号的元素）和要进去的元素（带有 f[2][3] = f[1][4] - z[1][4] + z[4][1] == 5符号的元素）。

 -1 -1 11 16 14 
 -1 -1 17 21  5 
 -1 -1 20  5  9 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 

第二遍
然后在第二个步骤中做类似的事情（我不打算写出来），只需要少一些元素。

 -1 -1 41 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 

第三步
此步骤与2x2示例的第一次和第二次迭代完全相同。所以，2x2稀疏菱形的和是：

 -1 25 15 10 -1    
 -1 27 18 18 -1    
 -1 15 24  6 -1    
 -1 -1 -1 -1 -1    
 -1 -1 -1 -1 -1    

当我们把它和第二次迭代的输出相加，我们得到：

 -1 -1 59 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 
 -1 -1 -1 -1 -1 

答案只有一个3x3菱形符合矩阵，所以矩阵中只剩下一个元素，这正是唯一符合的菱形的和：59。