Finding elements within distance k from a matrix

Question

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 . The 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

Sheehy

Is this homework? If yes, tag it as such. :) – Bad

Can you expand on your definition of distance? Is it k hops along the grid or a circle with radius k? – Sunglass

You need to define what kind of neighborhood you want to use. From your example I am guessing you mean van Neumann neighborhood, but this is not clear. – Lizalizabeth

P.s. the definiton of the van Neumann neighborhood can easily expanded into an algorithm if you just work with the inequality a little. So if you use this your algorithm will be dead simple. – Lizalizabeth

Answer 1

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
 }
}

Burnout

hey this code gives diagonal elements for k=1. I am able to get for k=2 but larger than that i am not able to get, please help – Sheehy

Answer 2

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.

Sunglass

Is it a diamond, or a circle? – Flowering

@rohit, I don't think stackoverflow.com is an implementation generation machine. The answer is so instructive, it should be really easy to implement now. If you cannot do it yet, learn it. – Contradiction