Поиск элементов на расстоянии k от матрицы

Учитывая матрицу n*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

Не могли бы вы помочь мне написать код C для реализации этого на C++.

Это проблема соседства фон Неймана, пожалуйста, кто-нибудь может реализовать ее на С++. Спасибо


c++ algorithm matrix nearest-neighbor
person koder    schedule 16.05.2011    source источник
comment
Это домашнее задание? Если да, отметьте его как таковой. :)   -  person Xeo    schedule 16.05.2011
comment
Можете ли вы расширить свое определение расстояния? Это k прыжков по сетке или круг радиуса k?   -  person Adam    schedule 16.05.2011
comment
Вам нужно определить, какое соседство вы хотите использовать. Из вашего примера я предполагаю, что вы имеете в виду район Ван Неймана, но это неясно.   -  person LiKao    schedule 16.05.2011
comment
P.S. определение окрестности Ван Неймана может быть легко расширено до алгоритма, если вы просто немного поработаете с неравенством. Так что, если вы используете это, ваш алгоритм будет очень простым.   -  person LiKao    schedule 16.05.2011

Ответы (2)


arrow_upward
0
arrow_downward

Это должно сработать для 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
 }
}
person Jordonias    schedule 16.05.2011
comment
эй, этот код дает диагональные элементы для k=1. Я могу получить k = 2, но больше этого я не могу получить, пожалуйста, помогите - person koder; 16.05.2011

arrow_upward
1
arrow_downward

Ваши соседи сформируют ромбовидный узор вокруг вашего целевого элемента. Точки ромба будут на расстоянии k прыжков от целевого элемента. Таким образом, верхняя часть будет на k строк вверх, левая — на k столбцов и т. д. При переходе от уровня к уровню ромб расширяется равномерно. Если вы начинаете с верхней точки и идете на одну строку вниз (ближе к целевому узлу), то вы выходите по 1 в каждую сторону. Он симметричен в других направлениях. Другими словами, разница в координатах x между соседним и целевым узлом плюс разница в y будет равна ‹= k.

Так что просто создайте два вложенных цикла for, которые перебирают этот ромб. Внешний цикл перебирает строки, внутренний цикл — столбцы. Начните сверху, затем расширяйте ромб на 1 на каждой итерации внешнего цикла, пока не достигнете той же строки, что и целевой элемент, затем сжимайте, пока не достигнете нижней точки. Очевидно, вам нужно проверить граничные условия для выхода за пределы матрицы.

person Adam    schedule 16.05.2011
comment
Это ромб или круг? - person James; 16.05.2011
comment
@rohit, я не думаю, что stackoverflow.com - это машина для создания реализаций. Ответ настолько поучителен, что его должно быть действительно легко реализовать сейчас. Если вы еще не можете этого сделать, научитесь. - person Tilman Vogel; 16.05.2011