Finding elements within distance k from a matrix

Given a n*n matrix and a value k, how do we find all the neighbors for each element? for example: in a 4*4 matrix, with k=2 say matrix is :

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

where these values are the indexes of the location, the neighbors for 1 are 1,2,3,5,6,9 . Th开发者_如何学Goe values 3,6 and 9 come only because k =2 and wouldnt be there if k was = 1.

similarly the neighbors of 6 will be 1 2 3 5 6 7 8 9 10 11 and 14

Can you please help me to write a c code to implement this in c++.

It is the problem of von Neumann neighborhood, please can some one implement it in c++. Thanks

Your neighbors will form a diamond pattern around your target element. The points of the diamond will be k hops away from the target element. So the top will be k rows up, the left will be k columns over, etc. The diamond expands uniformly as you go from level to level. If you start at the top point and go one row down (closer to the target node) then you go out 1 to each side. It's symmetric in the other directions. In other words, the difference in x coordinates between a neighbor and the target node plus the difference in y will be <= k.

So just make two nested for loops that iterate over this diamond. Outer loop iterates over the rows, inner loop over the columns. Start at the top then expand the diamond by 1 at each outer loop iteration until you reach the same row as the target element, then contract until you reach the bottom point. Obviously you'll need to test boundary conditions for going outside the matrix.

This should do the trick for k=1. Make minor changes to make it work for all 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
 }
}