1

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

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

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

同样 6 的邻居将是1 2 3 5 6 7 8 9 10 11 and 14

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

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

4

2 回答 2

1

您的邻居将在您的目标元素周围形成菱形图案。菱形的点将距离目标元素 k 跳。所以顶部将向上 k 行，左侧将超过 k 列，等等。随着您从一层到另一层，菱形会均匀地扩展。如果您从最高点开始向下走一排（靠近目标节点），那么您向每一侧走 1。它在其他方向上是对称的。换句话说，邻居和目标节点之间的 x 坐标差加上 y 的差将 <= k。

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

于 2011-05-16T07:27:47.233 回答
0

这应该可以解决 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
 }
}
于 2011-05-16T07:32:37.737 回答