Search for elements at a distance k from the matrix

Question

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

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

where these values ​​are location indices, the neighbors for 1 are 1,2,3,5,6,9 . The values 3,6 and 9 appear only because k = 2 and would not be there if k was = 1.

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

Could you help me write c code to implement this in C ++.

This is von Neumann's neighborhood problem, please, you can implement it in C ++. thank

Answer 1

This should do the trick for k = 1. Make small 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 } } 

Answer 2

Your neighbors form a diamond pattern around your target element. The diamond points will be k hops from the target element. Thus, the top will be k rows up, the left will be k columns, etc. A diamond expands evenly when you move from level to level. If you start at the top point and go one line down (closer to the target node), you exit 1 on each side. It is symmetrical in other directions. In other words, the difference in x coordinates between the neighboring and target node symbol plus the difference in y will be <= k.

So, just do two nested loops that iterate over this diamond. The outer loop iterates through the rows, the inner loop through the columns. Start at the top, then rotate the diamond by 1 at each iteration of the outer loop until you reach the same line as the target element, then squeeze until you reach the bottom point. Obviously, you will need to check the boundary conditions to go beyond the matrix.