查找距矩阵距离 k 以内的元素

Question

给定一个*n矩阵和一个值k，我们如何找到每个元素的所有邻居？ 例如：在 4*4 矩阵中，k=2 假设矩阵为：

[ 1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15 16]

其中这些值是位置的索引，1 的邻居是 1,2,3,5,6,9 。值 3,6 和 9 出现只是因为 k =2，如果 k = 1，则不会出现。

类似地，6 的邻居将是 1 2 3 5 6 7 8 9 10 11 14

你能帮我写一个c代码来用c++实现这个吗？

这是冯诺依曼邻域问题，请有人用c++实现它。谢谢

Answer 1

您的邻居将在您的目标元素周围形成菱形图案。菱形的点距目标元素有 k 跳。因此，顶部将向上 k 行，左侧将向上 k 列，依此类推。当您从一层到另一层时，菱形会均匀扩展。如果您从顶部点开始向下一行（更靠近目标节点），那么您将向每一侧输出 1。它在其他方向上是对称的。换句话说，邻居节点和目标节点之间的x坐标差加上y坐标差将≤k。

因此，只需创建两个嵌套的 for 循环来迭代此菱形即可。外循环遍历行，内循环遍历列。从顶部开始，然后在每次外循环迭代时将菱形扩展 1，直到到达与目标元素相同的行，然后收缩直到到达底部点。
显然，您需要测试离开矩阵的边界条件。

Answer 2

当 k=1 时，这应该可以解决问题。进行微小的更改以使其适用于所有 k

int width = 4;
int height = 4;
int k = 1;
int value = 2;

bool hasRight = (value % width != 0);
bool hasLeft = (value % width != 1);
bool hasTop = (value > 4);
bool hasBottom = (value < (height * width - width));

cout << value;  // Always itself
if(hasRight == true) {
 cout << value+1 << " ";  // Right
 if(hasTop == true) {
  cout << value-width << " " << value-width+1 << " "; // Top and Top-right
 }
 if(hasBottom == true) {
  cout << value+width << " " << value+width+1; // Bottom and Bottom-right
 }
}

if(hasLeft == true) {
 cout << value-1 << " ";  // Left
 if(hasTop == true) {
  cout << value-width-1 << " ";  // Top-left
 }
 if(hasBottom == true) {
  cout << value+width-1 << " ";  // Bottom-left
 }
}