c - 查找矩阵 NxN 中的所有峰值

Question

我正在尝试创建一种算法，使用直接的方法在 N x N 矩阵中查找所有峰。但是我在角落、第一行和最后一行以及第一列和最后一列方面遇到了一些问题。我正在考虑如下问题:

[ ][c][ ][ ] a is considered a 2d peak
[d][a][e][ ] or a hill iff a >= b,
[ ][b][ ][ ] a >= d, a >=c, a >=e
[ ][ ][ ][ ]

但是，当我需要评估角点时，c 和 d 不存在。我必须评估太多条件才能得到更通用的东西。即，对于下面的 a，如果 row-1 < 0，我需要检查位置 a 是否有效。 ，那么我就不需要检查 a 上面的任何东西，如果 col-1 < 0 任何东西都在 a 的左边。

[a][e][ ][ ] 
[b][ ][ ][ ] 
[ ][ ][ ][ ] 
[ ][ ][ ][ ]

但是当我们将a带到其他角甚至评估其他位置如上例中的e时，我需要证明自己是否e 处于 row-1 存在的有效位置，以防止评估该位置并出现错误(在上面的示例中，如果 e >= the element in row-1 我肯定会得到错误检查。我'我已经实现了一段考虑角点、第 0 行和第 n 行以及第 0 列和第 n 列的代码，但我停下来开始思考如何使其更具可读性和简单性。

void find_hill(){
    int i, j;
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            //check corners
            if(i-1 < 0){
                if(j-1 < 0){
                   //check if arr[i][j] >= arr at i,j+1 and i+1,j
                }
                if(j+1 > n-1){
                   //check if arr[i][j] >= arr at i,j-1 and i+1,j 
                }
            }                
        }
    }     
}

我想在这里讨论如何找到解决方案。我应该从哪里开始得到一些简单的东西？我曾想过以某种方式使用类似于洪水填充的方法，但它分别填充每个位置，可能行不通，因为我最终会遇到同样的问题!

Answer 1

我建议使用以下技巧:复制第一行和最后一行和列，如:

[ ][a][b][c][ ]
[a][a][b][c][c]
[d][d][e][f][f]
[g][g][h][i][i]
[ ][g][h][i][ ]

然后让你的循环从 1 开始到 n-1 结束。